Computer Science – Stack

Chapter – 3
STACK

1.1 Introduction To Data Structure:

A data structure defines a mechanism to store, organize and access data along with
operations (processing) that can be efficiently performed on the data. For example, string is a
data structure containing a sequence of elements where each element is a character. We can
apply different operations like reversal, slicing, counting of elements, etc. on list and string.

Classification Of Data Structure

Data structures are broadly divided into two :

1. Primitive data structures : These are the basic data structures and are
directly operated upon by the machine instructions, which is in a primitive level.
They are integers, floating point numbers, characters, Boolean constants, pointers etc.

2. Non-primitive data structures : It is a more sophisticated data structure emphasizing on

structuring of a group of homogeneous (same type) or heterogeneous (different type) data
items. Array, list, files, linked list, trees and graphs fall in this category

2.2 STACK Data Structure :

A stack is a non-primitive linear data structures, it is a order collection of elements in

which the elements are inserted at one end and deleted at the same end that end

1 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

referred as top of the stack. The order is referred to as "Last In, First Out" (LIFO). This means
that the last element added to the stack is the first one to be removed.

3.2.1 Applications Of Stack

Some examples of application of stack in programming are as follows:

1. Managing Function calls in modular programming

2. Stacks are used in parsing and evaluating arithmetic expressions.
3. Every text editor and word processor use stacks to implement undo mechanisms,
4. Web browsers use stacks to manage page navigation history. Each time you visit a
new page, the URL is pushed onto a stack.
5. Compilers use stacks to handle syntax checking, especially for balancing symbols
such as {, }, (, ), [, and ].
6. Memory management techniques use stacks to keep track of memory allocated to
programs during runtime.
7. Conversion of infix expression into prefix and postfix.

3.3 Operations On Stack

Three fundamental operations performed on the stack are

 PUSH Operation
 POP Operation
 PEEK Operation

PUSH Operation

2 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

PUSH adds a new element at the TOP of the stack. It is an insertion operation. We can
add elements to a stack until it is full. A stack is full when no more elements can be
added to it. Trying to add an element to a full stack results in an exception called ‘Stack
is overflow’.

POP Operation

POP operation is used to remove the top most element of the stack, that is, the element at
the TOP of the stack. It is a delete operation. We can delete elements from a stack until it
is empty i.e. there is no element in it. Trying to delete an element from an empty stack
results in an exception called ‘Stack is underflow’.

Visual representations of PUSH and POP operations on a stack are shown in Figure

Peek:

Refers to inspecting the value at the stack’s top without removing it; it is also sometimes
referred as inspection.

3.4 Implementation Of Stack In Python

The simple way to implement a stack in Python is using the data type list. We can fix
either of the sides of the list as TOP to insert/remove elements. It is to be noted that we
are using built-in methods append() and pop() of the list for implementation of the stack.

The program defines the following functions to perform these operations:

1. Create an empty stack named Stack. This is done by assigning an empty list to the
identifier named Stack:

3 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

Stack = list()
2. A function named isEmpty() to check whether the stack is empty or not. This
function returns True if the stack is empty, else returns False.
def isEmpty(Stack):
if len(Stack)==0:
return True
else:
return False
3. A function named stackPush() to insert (PUSH) a new element in stack. This function
has two parameters - the name of the stack in which the element is to be inserted
(Stack) and the element that needs to be inserted. The insertion of an element is
always done at the TOP of the stack. 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 stackPush(Stack, element):
[Link](element)

4. A function named size() to read the number of elements in the Stack. The len()
function of list in Python to find the number of elements in the Stack.
def size(Stack):
return len(Stack)

5. A function named peek() to read the most recent element (TOP) in the Stack.
def peek(Stack):
if isEmpty(Stack):
print('Stack is empty') return
None
else:
x =len(Stack)
element=Stack[x-1]
return element
6. A function named stackPop() to delete the topmost element from the stack. It takes
one parameter - the name of the stack (Stack) and 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.
We use the built in method pop() of Python list that removes the element from the end of
the list.
def stackPop(Stack):
if isEmpty(Stack):
print('!Stack is underflow')
return None
else:
4 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA
 Computer Science – Stack

return([Link]())
7. A function named display() to show the contents of the stack.
def display(Stack):
x=len(Stack)
print("Current elements in the stack are: ")
for i in range(x-1,-1,-1):
print(Stack[i])

#Python program to implement Stack operation

Stack = list()

def isEmpty():
if size()==0:
return True
else:
return False

def stackPush(element):
[Link](element)

def size():
return len(Stack)

def stackPeek():
if isEmpty():
print('!Stack is empty...')
return None
else:
x =len(Stack)
element=Stack[x-1]
return element

def stackPop():
if isEmpty():
print('!Stack is underflow')
return None
else:
return([Link]())

5 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

def display():
if isEmpty():
print('!Stack is Empty')
return None
else:
x=size()
print("Current elements in the stack are: ")
for i in range(x-1,-1,-1):
print(Stack[i])

while True:
print("1 -> PUSH")
print("2 -> POP")
print("3 -> PEEK")
print("4 -> DISPLAY")
print("5 -> EXIT")
choice=eval(input("Enter your choice…"))
match choice:
case 1:
n=eval(input("Enter the data to Push…."))
stackPush(n)
case 2:
n=stackPop()
print("Poped Element :",n);
case 3:
n=stackPeek()
print("Top Element :",n);
case 4:
display()
case 5:
break
case _ :
print("! Invalid choice")

print("*** End Of Stack Operation ****")

6 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

3.5 Notations For Arithmetic Expressions

 An expression is a combination of operands and operators that after evaluation results

in a single value.
 Operand consists of constants and variables.
 Operators consists of {, +, -, *, /, ), ] etc.
 Expression can be
o Infix Expression
o Postfix Expression
o Prefix Expression
 Infix Expression: If an operator is in between two operands, it is called infix
expression.
Example: a + b, where a and b are operands and + is an operator.
 Postfix Expression: If an operator follows the two operands, it is called postfix
expression.
Example: ab +
 Prefix Expression: an operator precedes the two operands, it is called prefix
expression.
Example: +ab

Consider the following examples of converting from infix to postfix

Sl No Infix Postfix
1 (A+B)*C = [AB+] * C AB+C*

2 A+B+C = [AB+]+C AB+C+

3 (A+B)/(X–Y) = [AB+]/[XY-] AB+XY-/

= [AB^] *C-D
4 A^B*C–D AB^C*D-
= AB^C*-D

= ([AB+]*C-[DE-])^[XY+]
5 ((A + B)*C–(D–E))^(X+Y) AB+C*DE--XY+^
=([AB+C*]-[DE-])^[XY+]
= (AB+C*DE--)^[XY+]

Consider the following examples of converting from infix to prefix.

Sl No
Infix Prefix
1 (A+B)*C = [+AB] * C *+ABC

2 A+B+C = [+AB]+C ++ABC

7 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

3 (A+B)/(X–Y) = [+AB]/[-XY] /+AB-XY

= [^AB] *C-D
4 A^B*C–D -*^ABCD
= [*^ABC]-D

= ([+AB]*C-[-
5 ((A + B)*C–(D–E))^(X+Y) DE])^[+XY] ^-*+ABC-DE^+XY

=([*+ABC]-[-
DE])^[+XY]
= (-*+ABC-
DE)^[+XY]

3.6 Conversion From Infix To Postfix Notation

During conversion, a stack is used to keep track of the operators encountered in the infix
expression. A variable of string type is used to store the equivalent postfix expression.

Algorithm to converts an expression in infix notation to postfix notation:

Step 1: Create an empty string named postExp to store the converted postfix expression.
Step 2: INPUT infix expression in a variable, say inExp
Step 3: For each character in inExp, REPEAT Step 4
Step 4: IF character is a left parenthesis THEN PUSH on the Stack
ELSE IF character is a right parenthesis
THEN POP the elements from the Stack and append to
postExp until the corresponding left parenthesis is popped
while discarding both left and right parentheses
ELSE IF character is an operator
THEN IF its precedence is lower than that of operator at the top of Stack
THEN POP elements from the Stack till an
operator with precedence less than the current
operator is encountered and append to string
postExp before pushing this operator on the
postStack
ELSE PUSH operator on the Stack
ELSE Append the character to postExp
Step 5: Pop elements from the Stack and append to postExp until Stack is empty
Step 6: OUTPUT postExp

This algorithm to convert a given infix expression (x + y)/(z*8) into equivalent postfix
expression using a stack.

8 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

Figure shows the steps to be followed on encountering an operator or an operand in the

given infix expression.

9 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

3.7 Evaluation Of Postfix Expression

Stacks can be used to evaluate an expression in postfix notation. For simplification, we
are assuming that operators used in expressions are binary operators.

Algorithm: Evaluation of postfix expression

Step 1: INPUT postfix expression in a variable, say postExp

Step 2: For each character in postExp, REPEAT Step 3
Step 3: IF character is an operand
THEN PUSH character on the Stack
ELSE POP two elements from the Stack, apply the operator on
the popped elements and PUSH the computed value onto the Stack
Step 4: IF Stack has a single element
THEN POP the element and OUTPUT as the net result
ELSE OUTPUT “Invaild Postfix expression”

Figure shows the step-by-step process of evaluation of the postfix expression 7 8 2 * 4 / +

using Algorithm

10 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

EXERCISE
1. State TRUE or FALSE for the following cases:
a) Stack is a linear data structure b) Stack does not follow LIFO rule
c) PUSH operation may result into underflow condition
d) In POSTFIX notation for expression, operators are placed after operands
2. Find the output of the following code:
a) result=0
numberList=[10,20,30]
[Link](40)
result=result+[Link]()
result=result+[Link]()
print(“Result=”,result)
b) 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)
3. Write a program to reverse a string using stack.
4. For the following arithmetic expression: ((2+3)*(4/2))+2
Show step-by-step process for matching parentheses using stack data structure.
5. Evaluate following postfix expressions while showing status of stack after
each operation given A=3, B=5,C=1, D=4
a) A B + C * b) A B * C / D *
6. Convert the following infix notations to postfix notations, showing stack and string
contents at each step.
a) A + B - C * D b) A * (( C + D)/E

MCQ
1. Process of inserting an element in stack is called
a) Create b) Push c) Evaluation d) Pop
2. Process of removing an element from stack is called
a) Create b) Push c) Evaluation d) Pop

11 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

3. In a stack, if a user tries to remove an element from an empty stack it is called

a) Underflow b) Empty collection c) Overflow d) Garbage Collection
4. Pushing an element into stack already having five elements and stack size of 5, then
stack becomes
a) Overflow b) Crash c) Underflow d) User flow
5. Entries in a stack are “ordered”. What is the meaning of this statement?
a) A collection of stacks is sortable b) Stack entries may be compared with the „<„ operation
c) The entries are stored in a linked list d) There is a Sequential entry that is one by one

6. Which of the following is not the application of stack?

a) A parentheses balancing program b) Tracking of local variables at run time
c) Compiler Syntax Analyzer d) Data Transfer between two asynchronous process
7. What is the value of the postfix expression 6 3 2 4 + – *?
a) 1 b) 40 c) 74 d) -18
8. The postfix form of the expression (A+ B)*(C*D- E)*F / G is?
a) AB+ CD*E – FG /** b) AB + CD* E – F **G /
c) AB + CD* E – *F *G / d) AB + CDE * – * F *G /
9. The data structure required to check whether an expression contains a
balanced parenthesis is?
a) Stack b) Queue c) Array d) Tree
10. What data structure would you most likely see in non recursive implementation of a
recursive algorithm?
a) Linked List b) Stack c) Queue d) Tree
11. The process of accessing data stored in a serial access memory is similar
to manipulating data on a
a) Heap b) Binary Tree c) Array d) Stack
12. The postfix form of A*B+C/D is?
a) *AB/CD+ b) AB*CD/+ c) A*BC+/D d) ABCD+/*
13. Which data structure is needed to convert infix notation to postfix notation?
a) Branch b) Tree c) Queue d) Stack
14. The prefix form of A-B/ (C * D ^ E) is?
a) -/*^ACBDE b) -ABCD*^DE c) -A/B*C^DE d) -A/BC*^DE
15. What is the result of the following operation? Top (Push (S, X))
a) X b) X+S c) S d) XS
16. The prefix form of an infix expression (p + q) – (r * t) is?
a) + pq – *rt b) – +pqr * t c) – +pq * rt d) – + * pqrt
17. Which data structure is used for implementing recursion?
a) Queue b) Stack c) Array d) List
18. The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
a) 600 b) 350 c) 650 d) 588

12 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

(A + B ⋀D)/(E – F)+G
19. Convert the following infix expressions into its equivalent postfix expressions.

a) (A B D ⋀ + E F – / G +) b) (A B D +⋀ E F – / G +)
c) (A B D ⋀ + E F/- G +) d) (A B D E F + ⋀ / – G +)
20. Convert the following Infix expression to Postfix form using a stack.
x + y * z + (p * q + r) * s,.
a) xyz*+pq*r+s*+ b) xyz*+pq*r+s+*
c) xyz+*pq*r+s*+ xyzp+**qr+s*+
21. Consider the following operation performed on a stack of size
5. Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
After the completion of all operation, the number of elements present in stack is?
a) 1 b) 2 c) 3 d) 4

22. Which of the following is not an inherent application of stack?

a) Reversing a string b) Evaluation of postfix expression
c) Implementation of recursion d) Job scheduling
23. The type of expression in which operator succeeds its operands is?
a) Infix Expression b) Prefix Expression
c) Postfix Expression d) Both Prefix and Postfix Expressions
24. The postfix expression for the infix expression a + b x c – d ^ e ^ f is?
a) a b c x + d e f ^ ^ – b) a b c x + d e ^ f ^ –
c) a b + c x d – e ^ f ^ d) – + a x b c ^ ^ d e f
25. If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at
a time, what is the order of removal?
a) ABCD b) DCBA c) DCAB d) ABDC
26. What is the other name for a postfix expression?
a) Normal polish Notation b) Reverse polish Notation
c) Warsaw notation d) Infix notation
27. Which of the following is an example for a postfix expression?
a) a*b(c+d) b) abc*+de-+ c) +ab d) a+b-c
28. Reverse Polish Notation is the reverse of a Polish Notation.

13 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA

 Computer Science – Stack

a) True b) False
29. In Postfix expressions, the operators come after the operands.
a) True b) False
30. Which of these operators have the highest order of precedence?
a) „(„ and „)‟ b) „*‟ and „/‟ c) „~‟ and „^‟ d) „+‟ and „-„
31. Which of the following is not an application of stack?
a) evaluation of postfix expression b) conversion of infix to postfix expression
c) balancing symbols d) line at ticket counter
32. While evaluating a postfix expression, when an operator is encountered, what is the
correct operation to be performed?
a) push it directly on to the stack
b) pop 2 operands, evaluate them and push the result on to the stack
c) pop the entire stack d) ignore the operator
33. Which of the following statement is incorrect?
a) Postfix operators use value to their right
b) Postfix operators use value to their left
c) Prefix operators use value to their right
d) In postfix expression, operands are followed by operators
34. What is the result of the given postfix expression? abc*+ where a=1, b=2, c=3.
a) 4 b) 5 c) 6 d) 7
35. What is the result of the following postfix expression? ab*cd*+ where
a=2,b=2,c=3,d=4.
a) 16 b) 12 c) 14 d) 10
36. Evaluate the postfix expression ab + cd/- where a=5, b=4, c=9, d=3.
a) 23 b) 15 c) 6 d) 10
37. Evaluate and write the result for the following postfix expression
abc*+de*f+g*+ where a=1, b=2, c=3, d=4, e=5, f=6, g=2.
a) 61 b) 59 c) 60 d) 55

14 SOWMYA RANI G S, LECTURER, DEPT OF COMPUTER SCIENCE, CHITRADURGA