COMPUTER SCIENCE
Chapter 3
STACK
Data structure
Data structure defines a mechanism to store, organize and access data along with operations
(processing) that can be efficiently performed on the data.
Eg: String, List, set, tuple, stack, queue, Array, Linked List, Binary Trees, Heaps, Graph, Sparse
Matrix ….
A data structure in which elements are organised in a sequence is called linear data structure.
STACK
STACK is a linear data structure where elements are added/removed from only one end
called as TOP of the stack.
It follows LIFO(Last In First Out) / FILO(First In Last Out) principle.
APPLICATIONS OF STACK
Real life applications
• Pile of clothes in an almirah
• Multiple chairs in a vertical pile
• Bangles worn on wrist
• Pile of boxes of eatables in pantry or on a kitchen shelf
Programming applications
• Reverse a string
The string is traversed from the last character till the first character by putting the
characters of string in a stack
• redo/undo operations in text and image editor
when redo/undo icon is clicked in text/image editor, the most recent editing is
redone/undone. The stack is used by the system to keep track of the changes made.
• Usage of Back button in web browsing history
To go back to the last visited web page, BACK button of the web browser is used. The
history of the browsed pages are maintained in stack.
Webpage3 back to Webpage2 back to Webpage1 using BACK button
• Parentheses to order the evaluation of operators
Evaluation of expression needs balanced parathesis in an expression, which will be
checked by the compiler. If number of left parenthesis is not equal to number of right
parenthesis compiler throw an error. To handle matching of parenthesis stack is used.
1
COMPUTER SCIENCE
Operations on Stack
1. PUSH operation
• PUSH adds a new element at TOP of the stack
• It is an insertion operation
• Trying to add an element to a full stack results in an exception called ‘overflow’
2. POP operation
• POP operation is used to remove the top most element of the stack
• It is deletion operation
• Trying to delete an element from an empty stack results in an exception called
‘underflow’
Implementation of Stack in Python
STACK can be implemented using the datatype list
Any one sides of the list can be considered as TOP to insert/remove elements
STACK can be implemented using built-in methods append() and pop() of the list
Write an algorithm to
1. Create a STACK
2. Check if the STACK is empty
3. Insert an element into the STACK
4. Find the number of elements in the STACK
5. Read the value of the topmost/recent element in the STACK
6. Delete an element from the STACK
7. Show the content of the STACK
S - Name of the STACK
n - size of the STACK
n-1 – index of Top recent element in the STACK
1. Create a STACK
It creates an empty list.
S = list()
2. Check if the STACK is empty
isEmpty() returns True if the stack is empty, else returns False
def isEmpty(S):
if len(S)==0:
return True
else:
return False
2
COMPUTER SCIENCE
3. Insert an element into the STACK
opPush() inserts an element into the STACK
Insertion of an element is always done at the TOP of the stack
append() to add an element at the end of the STACK
def opPush(S,ele):
[Link](ele)
Note:There is no limit on size of list in Python. So the STACK will never be full unless
there is no space available in memory. So we will never face overflow condition for
stack.
4. Find the number of elements in the STACK
Size() returns the number of elements in the STACK
len() - To find the size of the list/STACK
def size(S):
return len(S)
5. Read the value of the topmost/recent element in the STACK
Recently added element is the element present at the TOP of the STACK
top() is used to return the recently added element in the STACK
def top(S):
if isEmpty(S):
print('Stack is empty’)
return None
else:
n =len(S)
ele=S[n-1]
return ele
6. Delete an element from the STACK
opPop() checks whether the stack is empty or not. If it is not empty, it removes the
topmost element from the STACK
pop() - Removes the element from the end of the STACK
def opPop(S):
if isEmpty(S):
print('underflow’)
return None
else:
return([Link]())
3
COMPUTER SCIENCE
7. Show the content of the STACK
display() prints all the elements of the STACK
def display(S):
n=len(S)
print("Current elements in the stack are: ")
for i in range(n-1,-1,-1):
print(S[i])
Notations for arithmetic expressions
Arithmetic Expression
An expression is a valid combination of arithmetic operators and operands, that after
evaluation results in a single value.
Infix expression
If an operator is in between two operands it is called infix representation. These are
evaluated using BODMAS rule
Eg: a+b, 2 - 3 * y
Polish notation
Polish mathematician Jan Lukasiewicz in the 1920's introduced a different way of
representing arithmetic expression, called polish notation.
Prefix expression/Polish notation
The process of writing the operators of an expression before their operands is called the
polish notation.
The order of operations and operands determines the result, making parentheses
unnecessary
Eg: +ab
Postfix expression/ reverse polish notation
The process of writing the operators of an expression after their operands is called the
Reverse polish notation..
Eg: ab+
4
COMPUTER SCIENCE
Type of Expression Description Example
Infix Operators are placed in between the operands x*y+z
3 * ( 4 + 5)
(x+y)/(z*5)
Prefix(Polish) Operators are placed before the corresponding the +*xyz
operands *3+45
/+xy*z5
Postfix(Reverse Polish) Operators are placed after the corresponding xy*z+
operands 345+*
xy+z5*/
Conversion from Infix to Postfix Notation
• Infix expression have to deal with BODMAS rule to evaluate the expression
Eg: 4 + 2 / 3
Left to right evaluation( but / is applied first,+ is applied next)
• prefix/postfix expressions do not have to deal with such precedence(BODMAS) because
the operators are already positioned according to their order of evaluation. Hence a single
traversal from left to right is sufficient to evaluate the expression.
Evaluation of postfix expression
Step 1: Input Postfix expression
Step 2: PostExp = Postfix expression
Step 3: for each character in PostExp repeat step 4
Step 4: if ch==operand then
PUSH ch to STACK
else
POP 2 elements(operands)
Apply operator on operands
PUSH Result to STACK
Step 5:if 1 element in STACK then
pop the element
print Result
else
print ”invalid expression”
Evaluate the expression using STACK while showing status of STACK after each operation.
Given A= 3 B =5 C =1 D=4
1. A B * C / D
2. A B * C / D *
5
COMPUTER SCIENCE
6
COMPUTER SCIENCE
Conversion of expression from infix to postfix notation
Step 1: PostExp=“ ”
Step 2: input infix expression
Step 3: InExp = infix expression
Step 4: for ch in InExp,repeat step 5
Step 5: if ch is operand then
append to postExp
else if ch == ‘(‘ then
push ‘(‘ into STACK
else if ch==‘)’ then
Repeatedly Pop ele from STACK append to PostExp, until ‘(‘ is popped
else if ch is operator then
Repeatedly Pop operator (on Top of STACK) from STACK and append to PostExp,
which has same or higher precedence than ch
push ch (current operator )
Step 6: Pop remaining elements and append to PostExp
Step 7: print PostExp
7
COMPUTER SCIENCE
Assignment
1. Mention the other names of the STACK. Give reason
2. Explain the different operations on STACK data structure
3. Mention the real life applications of STACK data structure
4. Explain the programming applications of STACK data structure
5. Define and give an example for infix expression
6. Define and give an example for postfix/reverse polish expression
7. Define and give an example for prefix/polish notation
8. Write an algorithm to evaluate the postfix expression
9. Write an algorithm to convert infix to postfix expression
10. Convert the infix expression to postfix expression
i. ((2+3)*(4/2))+2
ii. (x+y)/(z*8)
11. Evaluation of postfix expression using STACK
i. 7 8 2 * 4 /+
ii. 3 5 + 1 *
12. Evaluate the expression using STACK while showing status of STACK after each
[Link] A= 3,B =5,C =1,D=4
i. AB+C*
ii. AB*C/D*
iii. AB*C/D
13. Write a program to,
i. Create a STACK
ii. Check if the STACK is empty
iii. Insert an element into the STACK
iv. Find the number of elements in the STACK
v. Read the value of the topmost/recent element in the STACK
vi. Delete an element from the STACK
vii. Show the content of the STACK
[Link] a program to perform push and pop operation on Stack.
[Link] a program to delete all elements from stack
def isEmpty(S):
if len(S)==0:
return True
else:
return False
8
COMPUTER SCIENCE
def opPop(S):
if isEmpty(S):
print('underflow’)
return None
else:
return([Link]())
while True:
ele=opPop(S)
if ele == None:
print("Stack is empty")
break
else:
print("Popped element is",ele)