1
CHAPTER -3
STACK
STACK:
➢ It is a linear data structure, in which elements are added or removed
from one end called TOP.
➢ STACK data structure works on Last in First out (LIFO) principle.
Real life Applications of stack:
➢ Pile of cloths in an almirah.
➢ Multiple chairs in vertical pile.
➢ Bangles worn on wrist.
➢ Pile of boxes kept one on one.
Programing Applications of stack
➢ Reversing a string.
➢ Undo mechanism.
➢ Reverse tracking method.
➢ Conversion of expressions from infix to prefix, postfix
➢ Used in recursion.
Operations on Stack:
S. No Operation Description
1. PUSH The process of adding a new data item in to the Stack.
2. POP The process of deleting a data item from the top end of
Stack.
3. SIZE Returns the number of elements present in the Stack
4. ISEMPTY Returns True when the Stack is empty.
5. PEEK Returns TOP element of the Stack
6. Traversal Traversing means accessing each element exactly once
7. ISFULL Returns True if TOP reaches max position
Implementation of Stack in python:
Stack are not built-in Python structures but can be implemented using lists.
# Create an empty stack
myStack = list ()
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGALORE -24
2
# PUSH operation
PUSH: The process of adding a new data item in to the Stack.
def SPush (myStack, element):
[Link](element)
# POP operation
POP: The process of deleting a data item from the top end of Stack.
def SPOP (myStack):
if len(myStack) == 0:
print (“Stack is Empty”)
return none
else:
element = pop(myStack)
# SIZE Operation
SIZE: Returns the number of elements present in the Stack
def size(myStack):
if len(myStack) == 0:
print (“Stack is Empty”)
return none
else:
return len(myStack)
# ISEMPTY Operation
ISEMPTY: Returns True when the Stack is empty.
def isEmpty(myStack):
if len(myStack) == 0:
return true
else:
return false
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGALORE -24
3
# PEEK Operation
PEEK: Returns TOP element of the Stack
def speek(myStack):
if len(myStack) == 0:
print(“Stack is Empty”)
else:
x = len(myStack)
return [Link](x)
# ISFULL Operation
In python, Stack is never been Full unless there is no more space in memory,
because there is no limit for the size of the list in python.
# TRAVERSAL Operation
Traversal: Traversing means accessing each element exactly once
def display(myStack):
print ("Current elements in the stack are:")
for i in range(len(myStack)-1, -1, -1):
print(myStack[i])
Expression Conversions using Stacks
What is an expression?
➢ An expression is a combination of Operands and Operators.
➢ After evaluation Expression gives single value result.
➢ Operands conations constants and variables.
➢ Operators consist of +,-,/,*,(,) etc.
An expression can be represented in three forms
1. Infix expression
2. Prefix expression
3. Postfix expression
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGALORE -24
4
Example For Conversion of Infix to Post and Prefix:
INFIX POSTFIX PREFIX
A+B AB+ +AB
(A+B) * (C+D) AB+CD+* *+AB+CD
A-B/(C*D^E) ABCDE^*/- -A/B*C^DE
Conversion from Infix to Postfix:
Algorithm: Infix to Postfix
1. Create empty string postExp and stack stack.
2. For each character in infix expression:
• If ( → PUSH to stack
• If ) → POP and add to postExp until ( is found
• If operator:
– POP higher or equal precedence operators and append to postExp
– PUSH current operator
• If operand → Append to postExp
3. POP remaining operators to postExp.
Example for infix to Postfix conversion:
Infix Expression: (m+n) *(k+p) Postfix expression : mn+kp+*
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGALORE -24
5
Evaluation of Postfix Expression:
A stack can be used to evaluate a postfix expression by following these steps:
Step 1: Create an empty stack.
Step 2: Iterate through the postfix expression from left to right.
Step 3: For each element in the postfix expression, do the following:
1. If the element is an operand (a number), push it onto the stack.
2. If the element is an operator (+, -, *, /, etc.), pop the top two elements
from the stack, apply the operator to these elements, and push the
result back onto the stack.
Step 4: After all elements have been processed, the result of the expression will
be the single element left on the stack.
Example for post fix evaluation using stacks:
Infix expression : 2 + 3 * 4
Post fix expression: 234*+
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGALORE -24