Chapter 3
Stack
• Data structure: Mechanism to store ,organize and access data along with operations.
• Stack and queue – popular data structures.
• These data structures directly not available in python- thus we implement it.
Stack:
• Arrangement of elements in an linear order is called as stack.
• Add new elements or remove existing elements from the same end.
• That end is known as Top of stack.
• Follows – LIFO (Last In First Out)principle.
i.e. The element that inserted last will be the first one to be removed
Applications of stack:
Real-Life applications(SHOULD EXPLAIN EACH AND EVERY APPPLICATION IN YOUR OWN
WORDS):
1) Pile of clothes in an almirah
2) Multiple chairs in a vertical pile
3) Bangles worn on wrist.
4) Pile of boxes of eatables in pantry or on a kitchen shelf .
Applications in programming(explain in your own words):
• Reversal of string: characters traversed in reverse order
• Usage of text/image editor where we have an options to redo and undo.
• Web browsing- recent history will be stored on the top .
• While writing arithmetic expression using the parenthesis , if there is a lack of pair of
parenthesis, the compiler throws an error.
Operations on stack:
we have 2 operations in stack:1) PUSH
2)POP
1. Push:
- To add a new element .
• It is an insertion operation.
• We can add an element to the stack until the stack is full.
• Trying to add an element to a full stack leads to an overflow.
2. Pop:
- To remove the top most element.
- It is an delete operation.
- We can delete the element from the stack until the stack is empty.
- Trying to delete an element from an empty stack leads to an underflow.
Implementation of stack:
- It can be done by using list data structure.
- We can fix either of the sides of the list as TOP(to add or remove element from the
same end).
- We use append() and pop() method of list for implementation of stack in python.
- These are built-in methods to insert and delete element from the rightmost end of the
list.
Program parameters to create a stack :
• Insert/ delete an element
• Check stack is empty.
• Find the number of elements.
• Read the topmost value.
Eg:(YOU CAN ALSO REFER NCERT)
glassStack = list()
def isEmpty(glassStack):
if len(glassStack)==0:
return True
else:
return False
def opPush(glassStack,element):
[Link](element)
def size(glassStack):
return len(glassStack)
def top(glassStack):
if isEmpty(glassStack):
print('Stack is empty')
return None
else:
x =len(glassStack)
element=glassStack[x-1]
return element
def opPop(glassStack):
if isEmpty(glassStack):
print('underflow')
return None
else:
return([Link]())
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)
OUTPUT:
Notations for Arithmatic Expressions:
• Arithmetic expressions are operators in between operands, like x + y, 2 - 3 * y, etc.
• Polish mathematician Jan Lukasiewicz in 1920 introduced a new way of representation
i.e. polish notation.
example
X+Y
+XY
XY+
Conversion from infix expression to postfix expression:
Example: refer your notes
Evaluation of postfix expression:
Example: refer your notes