DATA STRUCTURES- STACK
DATA STRUCTURES
A data structure is a way how the data is organised and stored in a computer.
A data structure is like a container that holds a group of data which can be processed as a
single unit.
Data structures make it simple to organise, search and work with data quickly and
efficiently.
STACK
A stack is a linear data structure which allows adding and removing elements in a Last In,
First Out order.
This means that the recently added elements will be removed first.
For example, with multiple books on the table in stack position, you can add or remove a
books from the top, which is known as Last In, First Out.
APPLICATIONS
Function calls: Stacks are used to keep track of the return addresses of function calls,
allowing the program to return to the correct location after a function has finished
executing.
Recursion: Stacks are used to store the local variables and return addresses of recursive
function calls, allowing the program to keep track of the current state of the recursion.
Expression evaluation: Stacks are used to evaluate expressions in postfix notation
(Reverse Polish Notation).
Syntax parsing: Stacks are used to check the validity of syntax in programming
languages and other formal languages.
Memory management: Stacks are used to allocate and manage memory in some
operating systems and programming languages.
STACK OPERATIONS
A stack is a mechanism that implements LIFO arrangement
Hence elements are added and deleted from the stack at one end only.
The end from which elements are added or deleted is called TOP of the stack.
Two fundamental operations performed on the stack are PUSH and POP.
PUSH & POP OPERATION
PUSH POP
POP operation is used to remove the
PUSH operation is used to add a new
topmost element of the stack.
element at the TOP of the stack.
It is an insertion operation It is a delete operation
We can delete elements from a stack
We can add elements to a stack until it
until it is empty i.e. there is no element
is full
in it.
A stack is full when no more elements
Trying to delete an element from an
can be added to it and is known as
empty stack is known as ‘underflow’
‘overflow’.
STACK IMPLEMENTATION
Insert/delete elements
Check if the STACK is empty
Find the number of elements in the STACK
Read the value of the topmost element in the STACK
Let us create an empty stack named glassStack.
We will do so by assigning an empty list to the identifier named glassStack:
glassStack = list[]
A function named isEmpty to check whether the stack glassStack is empty or not.
This function returns True if the stack is empty, else returns False.
def isEmpty(glassStack):
if len(glassStack)==0:
return True
else:
return False
A function named opPush to insert (PUSH) a new element in stack
Two parameters : 1. name of stack
2. Element to be added
use the built-in method append() of list to add an element to the stack that always adds
at the end of the list
def opPush(glassStack,element):
[Link](element)
A function named size to read the number of elements in the glassStack. We will use the
len() function of list def size(glassStack):
return len(glassStack)
A function named opPop to delete the topmost element from the stack.
It takes one parameter – the name of the stack (glassStack)
Returns the value of the deleted element.
The function first checks whether the stack is empty or not.
If it is not empty, it removes the topmost element from it.
Use the builtin method pop() of Python list that removes the element from the end of the
list.
def opPop(glassStack):
if isEmpty(glassStack):
print('underflow’)
return None
else:
A function named display to show the contents of the stack.
def display(glassStack):
x=len(glassStack)
print("Current elements in the stack are: ")
for i in range(x-1,-1,-1):
print(glassStack[i])
glassStack = list[] # create empty stack
#add elements to stack
element='glass1‘
print("Pushing element ",element)
opPush(glassStack,element)
element='glass2'
print("Pushing element ",element)
opPush(glassStack,element)
#display number of elements in stack
print("Current number of elements in stack is",size(glassStack))
#delete an element from the stack
element=opPop(glassStack)
print("Popped element is",element)
#add new element to stack
element='glass3'
print("Pushing element ",element)
opPush(glassStack,element)
#display the last element added to the stack
print("top element is",top(glassStack))
#display all elements in the stack
display(glassStack)
#delete all elements from stack
while True:
item=opPop(glassStack)
if item == None:
print("Stack is empty now")
break
else:
print("Popped element is",item)
The output of the above program will be as
follows:
Pushing element glass1
Pushing element glass2
Current number of elements in stack is 2
Popped element is glass2
Pushing element glass3
top element is glass3
Current elements in the stack are:
glass3
glass1
Popped element is glass3
Popped element is glass1
Underflow
Find the output of the following code:
result = 0
numberList = [10, 20, 30]
[Link](40)
result = result + [Link]()
result = result + [Link]()
print("Result=", result)
Output
Result= 70
Find the output of the following code:
answer = [];
output = ''
[Link]('T')
[Link]('A')
[Link]('M')
ch = [Link]()
output = output + ch
ch = [Link]()
output = output + ch
ch = [Link]()
output = output + ch
print("Result=", output)
Output
Result= MAT