MODULE 2: STACKS
BANGALORE AND QUEUES
INSTITUTE OF TECHNOLOGY
An Autonomous Institution Under VTU
K R ROAD, V V PURA, BENGALURU-04
Course Title: Data Structures and Applications Course Code: BCS304
Semester: III Academic Year: 2025-2026
Batch: 2024-2028
STACKS: Stacks, Stacks Using Dynamic Arrays, Evaluation and conversion of Expressions.
QUEUES: Queues, Circular Queues, Multiple Stacks
Text 1
Book
Chapter Chapter 3: 3.1-3.4, 3.6-3.7
RBT 2, 3, 4
[Link]. Question C RBT
O
1. Explain with an example how a stack can be used to reverse a string. 2 2
Write the algorithm and demonstrate the intermediate stack contents
for the input 'DATASTRUCTURE'
2. Define stack and write an ADT of stack. Implement push and pop 2 3
functions for stack using arrays with stackfull and stackempty
conditions.
3. Write a function to evaluate a postfix expression and trace the same 2 4
for the expression
i. ab/c - de*+ a c *- where a= 6, b = 3, c = l, d = 2, e = 4
ii. ab/c-de*+ac*- given a=2, b=2, c=3, d=4, e=2
4. List the disadvantage of linear queue and explain how it is solved in 2 3
circular queue. Give the algorithm to implement a circular queue
with the suitable example.
5. Convert the infix expression ((a/(b-c+d))*(e-a)*c) to postfix 2 3
expression. Write a function to evaluate the postfix expression and
trace for the given data a=6, b=3, c=1,d=2,e=4.
6. Explain multiple stacks with neat diagram and write algorithm for 2 2
push(), pop() & display().
7. What is the advantage of circular queue over ordinary queue? Write a 2 4
C program to simulate the working of circular queue of integers
using array. Provide the following operations: Insert, Delete, Display
8. Write an algorithm and function to convert a valid infix expression to 2 3
postfix expression. Demonstrate the same function with example.
(using stack)
i. ( a * b ) + c / d
ii. ( ( ( a / b ) – c ) + ( d * e ) ) - (a * c)
iii. a * ( b + c ) * d
iv. a $ b * c – d + e / f / ( g + h ) (a+ b) * d + e i (f+a* d) + c
v. ((a/(b- c + d))* (e - a)* c)
9. Define Queue and write an ADT of Queue. Explain the 2 3
implementation of the queue.
10. With suitable example explain infix,postfix and prefix expression. 2 2
11. Write a note on Dequeue and priority queue. 2 2
12. Implement the operations PUSH, POP, and DISPLAY using 2 3
dynamic arrays. Explain how stack overflow is avoided in this
implementation.
13. Convert the following infix expression to postfix using stack 2 3
operations and show each step: A + B * (C - D) / (E + F).
14. Evaluate the following postfix expression using stack operations. 2 3
Show the contents of the stack after every step: 5 6 2 + * 12 4 / -
15. Differentiate between stacks and queues with respect to their logical 2 2
structure and applications. Give one real-life analogy for each
16. Write an algorithm to evaluate an infix expression directly using two 2 3
stacks (one for operators and one for operands). Apply your
algorithm to evaluate: (7 + 3) * (5 - 2) / (6 - 4). Show intermediate
stack states
17. Analyze the following stack sequence and determine whether it can 2 4
occur from a valid sequence of push and pop operations: Push: 1, 2,
3, 4, 5; Pop sequence: 4, 5, 3, 2, 1. Justify your answer with proper
reasoning
18. Write a menu-driven program to implement a circular queue using 2 3
arrays. Show how front and rear pointers are updated for the
following sequence of operations: Insert(10), Insert(20), Insert(30),
Delete(), Insert(40), Insert(50). Assume queue size = 4.
19. You are required to simulate multiple stacks in a single array. If the 2 4
array size is 15 and there are 3 stacks, explain with algorithm and
diagram how space is divided and managed dynamically
20. A compiler uses stacks for expression evaluation and function call 2 4
management. Explain how operator precedence and parentheses are
handled using stack operations. Simulate stack contents for the
expression: ((a + b) * c) - (d / e)
21. Consider an online ticket booking system where customers are 2 4
served on a first-come-first-served basis. Identify which data
structure (stack/queue/circular queue) fits best and justify. Write the
algorithm for enqueue and dequeue operations for that structure.
Demonstrate the process for 5 customers with enqueue and dequeue
operations shown step-by-step.
22. A CPU scheduling system uses a circular queue to allocate processor 2 4
time to multiple processes in a round-robin manner. Write an
algorithm to simulate this process using a circular queue and
illustrate how the queue changes over 3 rounds for 4 processes P1,
P2, P3, P4.
23. Given an expression evaluator that converts infix to postfix and then 2 4
evaluates the result, write both algorithms (conversion and
evaluation). Demonstrate the working for: (8 + 4) * (3 - 2) / (2 + 2).
Include step-by-step stacks for both conversion and evaluation
phases.
24. A call center uses a circular queue to manage incoming customer 2 4
requests because the number of calls is limited to 10 at a time.
Explain how circular queue logic ensures that new calls are accepted
as soon as old ones are resolved.
25. In a bank, customers are served in the order they arrive. Model this 2 4
situation using a queue data structure. Describe how enqueue() and
dequeue() operations correspond to customer arrival and service
completion.
26. In a browser that supports multiple tabs, each tab maintains its own 2 4
browsing history. Explain how stacks using dynamic arrays can be
used to handle different tab histories efficiently.
27. A calculator app converts infix expressions to postfix before 2 4
evaluation. For the expression:
(8 + 4) * (6 - 2)
Explain step-by-step how stacks are used for both conversion and
evaluation.
28. Explain how stacks are used to perform Undo and Redo operations in 2 4
text-editing software like MS Word or Notepad.
29. An embedded microcontroller in a scientific instrument (like a 2 4
digital oscilloscope) needs to compute mathematical expressions
without parentheses, using limited memory. Given the expression 6 2
3 + - 3 8 2 / + * 2 ^ , trace its evaluation process.
30. In a multiplayer game, each player’s actions are stored in a separate 2 4
stack (like moves, health updates, etc.).Explain how using multiple
stacks allows independent undo/redo actions for each player.
Faculty-In charge
Course Co-ordinator Module Co-ordinator IQAC Programme Co-ordinator