Exercise
Question 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.
Answer
(a) True
Reason — A stack is a linear data structure following the Last In,
First Out (LIFO) principle, where elements are arranged sequentially.
(b) False
Reason — A stack follows the Last In, First Out (LIFO) rule. In a
stack, the last element added is the first one to be removed from the
stack.
(c) False
Reason — When attempting to remove an element (POP operation)
from an empty stack, it leads to an underflow condition, resulting in
an exception being raised.
(d) True
Reason — In POSTFIX notation for expression, operators are
placed after the corresponding operands.
Question 2(a)
Find the output of the following code:
result = 0
numberList = [10, 20, 30]
numberList.append(40)
result = result + numberList.pop()
result = result + numberList.pop()
print("Result=", result)
Answer
Output
Result= 70
Explanation
The code initializes result to 0 and creates a list [10, 20, 30]. It
appends 40 to the list and then performs two pop() operations on the
list, which removes and returns the last element (40 and 30). These
values are added to result, resulting in result being 70. Finally, the
code prints "Result=" followed by the value of result, which is 70.
Question 2(b)
Find the output of the following code:
answer = []; output = ''
answer.append('T')
answer.append('A')
answer.append('M')
ch = answer.pop()
output = output + ch
ch = answer.pop()
output = output + ch
ch = answer.pop()
output = output + ch
print("Result=", output)
Answer
Output
Result= MAT
Explanation
The code initializes an empty list answer and an empty string output. It
appends the characters 'T', 'A', and 'M' to the answer list. After
appending, answer list becomes ['T', 'A', 'M'].
After that, three pop() operations are performed on answer, removing
and returning the last element each time ('M', 'A', and 'T'
respectively). These characters are concatenated to
the output string. So, output string becomes MAT which is printed as
the final output.
Question 3
Write a program to reverse a string using stack.
Answer
def push(stack, item):
stack.append(item)
def pop(stack):
if stack == []:
return
return stack.pop()
def reverse(string):
n = len(string)
stack = []
for i in range(n):
push(stack, string[i])
string = ""
for i in range(n):
string += pop(stack)
return string
string = input("Enter a string: ")
print("String:", string)
reversedStr = reverse(string)
print("Reversed String:", reversedStr)
Output
Enter a string: Hello world
String: Hello world
Reversed String: dlrow olleH
Question 4
For the following arithmetic expression:
((2 + 3) * (4 / 2)) + 2
Show step-by-step process for matching parentheses using stack
data structure.
Answer
For matching parentheses, we can push in the stack for each
opening parenthesis of the expression and pop from the stack for
each closing parenthesis.
Scanning from left to right:
Symbol Stack Action
( ↑ — top
( Push
↑
((
( Push
↑
2 ..........
+ ..........
3 ..........
(
) Pop
↑
* ..........
((
( Push
↑
4 ..........
/ ..........
2 ..........
(
) Pop
↑
) #Empty Pop
+ ..........
2 #Empty ..........
Empty stack => Balanced Parentheses
Question 5(a)
Evaluate following postfix expression while showing status of stack
after each operation given A = 3, B = 5, C = 1, D = 4.
AB + C *
Answer
AB + C * = 35 + 1 *
Scanning from left to right :
Intermediate
Symbol Action Stack
output
3
3 Push
↑
53
5 Push
↑
#Empty
Pop twice and Evaluate
+ 8 3+5=8
and Push back
18
1 Push
↑
#Empty
Pop twice, Evaluate Push
* 8 1*8=8
back
Hence, AB + C * = 35 + 1 * = 8
Question 5(b)
Evaluate following postfix expression while showing status of stack
after each operation given A = 3, B = 5, C = 1, D = 4.
AB * C / D *
Answer
AB * C / D * = 35 * / 4 *
Scanning from left to right :
Intermediate
Symbol Action Stack
output
3 Push 3
5 Push 53
↑
#Empty
Pop twice, Evaluate and
* 15 3 * 5 = 15
Push back
1 15
1 Push
↑
#Empty
Pop twice, Evaluate and
/ 15 15/1 = 15
Push back
4 15
4 Push
↑
#Empty
Pop twice, Evaluate and
* 60 15 * 4 = 60
Push back
Hence, AB * C / D * = 35 * / 4 * = 60
Question 6(a)
Convert the following infix notation to postfix notation, showing stack
and string contents at each step.
A+B-C*D
Answer
Given,
A+B-C*D
Scanning from left to right :
Postfix
Symbol Action Stack
Expression
+ A
+ Push in stack
↑
B AB
Equal precedence to +. -
Pop from stack, add in
- AB+
expression then push this
operator(-) ↑
*- AB+C
Higher precedence than (-
*
), hence Push
↑
D AB+CD
End of Pop all and add to
#Empty AB+CD*-
expression expression
Postfix notation of A + B - C * D = AB+CD*-
Question 6(b)
Convert the following infix notation to postfix notation, showing stack
and string contents at each step.
A * (( C + D)/E)
Answer
Given,
A * (( C + D)/E)
Scanning from left to right:
Postfix
Symbol Action Stack
Expression
*
* Push
↑
(* A
( Push
↑
((*
( Push
↑
+((* AC
+ Push
↑
D ACD
) (* ACD+
Pop till one opening
bracket is popped and
↑
add popped operator to
expression
/(*
/ Push
↑
E ACD+E
Pop till one opening *
bracket is popped and
) ACD+E/
add popped operator to
expression ↑
End of Pop all and add to
#Empty ACD+E/*
expression expression
Postfix notation of A * (( C + D)/E) = ACD+E/*
Question 7
Write a program to create a Stack for storing only odd numbers out
of all the numbers entered by the user. Display the content of the
Stack along with the largest odd number in the Stack. (Hint. Keep
popping out the elements from stack and maintain the largest
element retrieved so far in a variable. Repeat till Stack is empty)
Answer
def push(stack, item):
stack.append(item)
def pop(stack):
if stack == []:
return
return stack.pop()
def oddStack(num):
if num % 2 == 1:
push(stack, num)
def GetLargest(stack):
elem = pop(stack)
large = elem
while elem != None:
if large < elem:
large = elem
elem = pop(stack)
return large
n = int(input("How many numbers?"))
stack = []
for i in range(n):
number = int(input("Enter number:"))
oddStack(number)
print("Stack created is", stack)
bigNum = GetLargest(stack)
print("Largest number in stack", bigNum)
Output
How many numbers?8
Enter number:1
Enter number:2
Enter number:3
Enter number:4
Enter number:5
Enter number:6
Enter number:7
Enter number:8
Stack created is [1, 3, 5, 7]
Largest number in stack 7
Compare and contrast queue with stack.
Answer
Stack Queue
Stack follows LIFO (Last in First Queue follows FIFO (First in
out) principle. First out) principle.
Stack Queue
In queue, insertion occurs at
In stack, insertion and deletion
the rear end and deletion
occurs at one end only.
occurs at the front end.
In stack, Push operation is used In queue, enqueue is used
for element insertion and Pop for element insertion and
operation is used for element dequeue is used for element
deletion. deletion.
A queue may be circular or
There are no variations of stack.
deque.
How is queue data type different from deque data type?
Answer
Queues only allow insertion in one end (rear end) and retrieval from
the other end (front end). A deque, on the other hand, is a double-
ended queue, which allows flexibility with insertion or deletion such
that one of these operations is allowed at both ends rather than
having a fixed end for the operations.
Write a python program to check whether the given string is
palindrome or not, using deque. (Hint : refer to algorithm 4.1)
Answer
def Deque():
return []
def addRear(deque, ch):
deque.append(ch)
def removeFront(deque):
if len(deque) == 0:
return None
return deque.pop(0)
def removeRear(deque):
if len(deque) == 0:
return None
return deque.pop()
def palchecker(aString):
chardeque = Deque()
for ch in aString:
addRear(chardeque, ch)
while len(chardeque) > 1:
first = removeFront(chardeque)
last = removeRear(chardeque)
if first != last:
return False
return True
string1 = input("Enter a string: ")
pal = palchecker(string1.lower())
if pal:
print(string1, "is a palindrome.")
else:
print(string1, "is not a palindrome.")
Output
Enter a string: anupama
anupama is not a palindrome.
Enter a string: malayalam
malayalam is a palindrome.
