Chapter 3: STACK
1) What is a Data Structure?give examples.
A data structure is a way of organizing and storing data so that it can be used
efficiently.
Examples:Array,Linked List,Stack,Queue,Dictionary (Hash Table)
U
2) Define Stack.
R
A stack is a linear data structure in which elements are added and removed only from
one end called TOP, following the Last In, First Out (LIFO) principle.
U
3) What is another name for STACK?
R
LIFO (LAST IN FIRST OUT) or FILO (FIRST IN LAST OUT).
A
4) Mention some of the real life applications of STACK.
G
● Stack of plates in a canteen
● Books piled one over another
● Pile of clothes in an almirah
A
● Parking system (cars parked one behind another)
,N
5) Describe the applications of STACK in Computer Science.
C
● Function Call Stack: Stores function calls while a program runs (last called
function executes first).
U
● Expression Evaluation: Used to evaluate postfix and prefix expressions
● Syntax Checking: Checks balanced parentheses in programs ( ){ }[ ]
SP
● Undo/Redo Operations: Stores previous actions in editors to revert changes
● Backtracking Algorithms: Helps in solving problems like maze, recursion
● Memory Management: Manages execution of functions using stack memory
G
6) Describe the operations of STACK.
● Push: Adds an element to the top of the stack
B
● Pop: Removes the top element from the stack
● Peek (Top): Returns the top element without removing it
● isEmpty: Checks whether the stack is empty
● isFull: Checks whether the stack is full (in fixed-size stack)
● Size: Returns the number of elements in the stack
7) Write the implementation of all the operations of STACK.
● Create Empty STACK
stack = [ ]
Dept. of Computer Science Page 1
● PUSH
def push(stack, element):
[Link](element)
● POP
def pop(stack):
if len(stack) == 0:
return "Stack is empty"
U
return [Link]()
R
● PEEK/TOP
def peek(stack):
U
if len(stack) == 0:
return "Stack is empty"
R
return stack[-1]
A
● ISEMPTY
def is_empty(stack):
G
return len(stack) == 0
A
● SIZE
def size(stack):
,N
return len(stack)
● DISPLAY
C
def display(stack):
if len(stack) == 0:
U
print("Stack is empty")
else:
SP
print("Stack elements (Top to Bottom):")
for i in range(len(stack)-1, -1, -1):
print(stack[i])
G
8) What is an Arithmetic Expression ? mention its types.
B
An arithmetic expression is a combination of operands (numbers/variables) and
operators (+, −, ×, ÷) used to perform calculations.
Types of Arithmetic Expressions:
● Infix Expression (operator between operands) → A + B
● Prefix Expression (operator before operands) → + A B
● Postfix Expression (operator after operands) → A B +
Dept. of Computer Science Page 2
Note: Polish mathematician Jan Lukasiewicz in the 1920's introduced a
different way of representing arithmetic expression, called polish notation.
9) Some examples for INFIX to POSTFIX conversion.
1)Expression: A + B * C
Symbol Stack Postfix
U
A EMPTY A
R
+ + A
U
B + AB
R
* + * AB
A C + * ABC
G
END ABC * +
FINAL POSTFIX EXPRESSION IS ABC * +
A
10)Infix: A + B * ( C - D )
,N
Symbol Stack Postfix
C
A EMPTY A
U
+ + A
SP
B + AB
* +* AB
G
( +*( AB
C +*( ABC
B
- + * (- ABC
D + * (- ABCD
) +* ABCD-
END ABCD- * +
FINAL POSTFIX EXPRESSION IS ABCD- * +
Dept. of Computer Science Page 3
11)Some examples for Evaluation of POSTFIX Expressions.
23*5+
Symbol Operation Stack
2 Push 2 2
U
3 Push 3 23
R
* Pop 2,3→ 2 * 3=6 6
Push 6
U
5 Push 5 65
R
+ Pop 6 5→6 +5 =11 11
A Puh 11
G
Final output is 11
A
12)52+83-*
,N
C
Symbol Operation Stack
U
5 Push 5 5
2 Push 2 52
SP
+ Pop 5 ,2→5+2=7 7
Push 7
G
8 Push 8 78
3 Push 3 783
B
- Pop 8,3→8-3=5 75
Push 5
* Pop 7,5 → 7*5=35
Push 35
Final output is 35
Dept. of Computer Science Page 4
13)Write the algorithm to convert INFIX to POSTFIX.
1. Initialize an empty stack and an empty postfix expression.
2. Scan the infix expression from left to right.
3. If the symbol is an operand, add it to the postfix.
4. If the symbol is ‘(’, push it onto the stack.
5. If the symbol is ‘)’, pop from stack and add to postfix until ‘(’ is found (discard
both brackets).
6. If the symbol is an operator:
● While the stack is not empty and the top has higher or equal
U
precedence, pop and add to postfix.
● Push the current operator onto the stack
R
7. After scanning is complete, pop all remaining operators from the stack to
postfix.
U
8. The final postfix expression is obtained
R
14)Write the algorithm for the POSTFIX EVALUATION.
1. Initialize an empty stack.
A
2. Scan the postfix expression from left to right.
3. If the symbol is an operand, push it onto the stack.
G
4. If the symbol is an operator:
● Pop the top two elements from the stack.
A
● Apply the operator (second popped ⬅ first popped).
● Push the result back onto the stack
,N
5. Repeat until the expression is completely scanned.
6. The final result will be the only element left in the stack.
7. Return that value
C
U
SP
G
B
Dept. of Computer Science Page 5