LIFO

STACK ASSIGNMENT
A Comprehensive Study of Stack Data Structure

Data Structures and Algorithms

Computer Science and Engineering

Assignment Author: AI/ML Engineer Thomas Basyal

Email 1: [Link]@[Link]
Email 2: [Link]@[Link]

Submission Guidelines
Physical submission only • Neat and clean presentation
No copying allowed • Original work required
 Important Notes for Students

• No Copying: Any copied assignment will be disqualified immediately.

• Handwriting: Answers must be written in clear, legible handwriting.

• Accuracy: Ensure there are no mistakes in your response.

• Presentation: Provide answers in bullet points where applicable for clarity.

• Figures: Include diagrams or figures if necessary to clarify explanations.

• Code: Write C++ code only wherever required. Ensure proper indentation.

• Submission: Physical submission only. Submit neat and clean work.

• Deadline: Adhere strictly to the submission deadline.

Good Luck with Your Assignment!

Remember: Understanding concepts is more important than memorization
Data Structures Stack Assignment

1 Theoretical Questions
Question 1: Define Stack
Define stack, explain LIFO principle, and provide a diagram showing push and pop
operations. Give real-life examples of stack usage.

Question 2: Stack as an ADT

Explain Stack as Abstract Data Type (ADT). Include:

• Operations: Push, Pop, Peek, IsEmpty, IsFull

• Advantages of ADT representation

• Step-by-step example of stack operations

Question 3: Applications of Stack

Explain in detail:

• Computational Applications: function call management, recursion, un-

do/redo, expression evaluation, browser navigation

• Non-Computational Applications: plate stacking, puzzle backtracking, his-

torical events, undo actions in real life

Question 4: Stack Implementation with Illustrations

Explain and demonstrate stack implementation using arrays. Your answer must
include:

• A clearly labeled diagram showing how elements are stored in the array-based
stack.

• C++ code for Push and Pop operations with proper overflow and underflow han-
dling.

• A step-by-step example: Given the operations Push(10), Push(20), Push(30),

Pop(), Push(40), Push(50), show the stack content after each step using a
figure/table.

• Draw the final stack and indicate the position of TOP.

2
Data Structures Stack Assignment

Question 5: Advantages and Disadvantages of Stack

Explain with examples.

Question 6: Primitive Operations of Stack

Write algorithms and C++ code for:

• Push

• Pop

• Peek/Top

• Display

• Sum

• Print alternate numbers

Include examples of stack operations after each command.

Question 7: Advantages of Postfix Expression

Explain advantages of postfix expression over infix operations in 10 points.

3
Data Structures Stack Assignment

2 Conversion Problems
2.1 Infix to Postfix and Prefix (Without Stack)
Question 8: Conversion Set 1 - Without Using Stack
Convert the following infix expressions to postfix and prefix WITHOUT USING
STACK:

1. (A + B ∗ C) − (D/E + F )

2. (X − Y ) ∗ (Z + W/V )

3. (P + Q ∗ R)/(S − T )

4. (M ∗ N + O) − (P + Q/R)

5. (A + B) ∗ (C − D) + (E/F )

2.2 Infix to Postfix and Prefix (Using Stack)

Question 9: Conversion Set 2 - Using Stack with Algorithm
First write an algorithm for converting infix to postfix and prefix, then
solve:

1. (A + B ∗ C/D) + E ∗ F − (G ∗ H + I − J)

2. A + (B ∗ C − (D/E ∗ F ) ∗ G) ∗ H

3. (a − b/c$d) ∗ e/(f − g ∗ h)

4. A + (B ∗ C − (D/EˆF ) ∗ G) ∗ H

5. (A + B)ˆ(C ∗ D) − E/F

6. (A + B ∗ (C − D)/E)F − (G + H/(I − J ∗ K)) ∗ L

7. P ∗ (Q + R/S) − T )/(U + V ∗ (W − X/Y )) + (M − N ∗ O)(A + B)

8. (A + (B − C ∗ D)/(E + F ∗ (G − H))) ∗ (I(J − K/L) + M ∗ (N − O/P ))

9. ((W + X ∗ (Y − Z))(A − B/C) + (D ∗ E − F )/(G + H ∗ I)) − (JK − L ∗ (M + N/O))

10. (A ∗ (B + C ∗ (D − E/F )) − (G − H/I) ∗ J)(K + L/M − (N ∗ O − P/Q))

4
Data Structures Stack Assignment

3 Postfix Evaluation
Question 10: Postfix Evaluation Problems
Write algorithm and then write C++ code for evaluating the following
postfix expressions:

1. A B C / − D E ∗ F − ∗ (Where A=6, B=5, C=2, D=3, E=4, F=1)

2. AB + C − BA + C$ − (AssumeA = 1, B = 2, C = 3)

2. A ∗ (B + C) − (D/E) (Assume A=5, B=6, C=2, D=12, E=4)

3. 8 2ˆ3 7 ∗ + 4 2 / 5 − 6 3ˆ + ∗ 9 −

4. 3 5 8 ∗ 7 + −2 ∗ 4 6 / + 2ˆ10 −

5. 2 4 ∗ 3 1 − 2ˆ + 7 2 / − 9 1 2 /ˆ + 6 3 − 2ˆ ∗ 5 /

6. 2 3ˆ4 5ˆ ∗ 6 7 + / 8 2ˆ + 9 −

7. −3 4 2 ∗ 5 + − 6 2ˆ3 / + 4 1 − ∗ 7 2ˆ−

8. 10 3 / 2 1 + ∗ 7 2ˆ − 4 2 / + 3 8ˆ−

9. 5 1 2 + 4ˆ + 3 − 2 2ˆ ∗ 7 2 / + 10ˆ6 3 − ∗

Question 11: Postfix to Infix Conversion

Convert the following postfix expressions to infix with algorithm and
C++ code:

1. Postfix 1: A B C D E / − ∗ + F G H ∗ + /

2. Postfix 2: P Q R S / + ∗ T − U V W X Y / − ∗ + / M N O ∗ − A B + ˆ+

3. Postfix 3: A B C D ∗ − E F G H − ∗ + / + I J K L / −ˆM N O P / − ∗ +

4. Postfix 4: W X Y Z − ∗ + A B C / − ˆ D E ∗ F − G H I ∗ + / +
J K ˆL M N O / + ∗ −

5. Postfix 5 (Hardest): A B C D E F / − ∗ + G H I / − J ∗ − K L M / +
N OP Q/ − ∗ −ˆ

5
Data Structures Stack Assignment

4 Prefix to Infix Conversion

Question 12: Prefix to Infix Conversion
Convert from prefix to infix operations:

1. Prefix 1: /ˆ + A ∗ B C − D / E F + G ∗ H I

2. Prefix 2: + / − ∗ P + Q / R S T + U ∗ V − W / X Y ˆ − M ∗ N O + A B

3. Prefix 3: ∗ + A / − B ∗ C D + E ∗ F − G H +ˆI − J / K L ∗ M − N / O P

4. Prefix 4: − + ˆ + W ∗ X − Y Z − A / B C / − ∗ D E F + G ∗ H I −
ˆJ K ∗ L + M / N O

5. Prefix 5: ˆ− ∗ A + B ∗ C − D / E F ∗ − G / H I J − + K / L M − ∗ N O / P Q

5 Combined Problem
Question 13: Combined Conversion and Evaluation
Convert infix to postfix expression using stack and then evaluate the
postfix expression:

((A + B) − C ∗ D/E)$ ∗ (H − I) ∗ F + G
Assume: A=4, B=2, C=4, D=3, E=8, F=2, G=3, H=5 and I=1
Note: First convert to postfix, then evaluate to get the final answer.

6
Data Structures Stack Assignment

6 Logical Stack Problems

Question 14: Extreme Logical Stack Problem
You have an empty stack S. Perform the following operations in order:
Push 5, Push 10, Push 15, Pop, Push 20, Push 25, Pop, Pop, Push 30, Push 35,
Pop, Push 40, Push 45, Push 50, Pop, Pop, Push 55, Push 60, Pop, Pop, Push 65,
Push 70, Pop, Push 75, Pop, Pop, Push 80
Questions:

a) What is the top element of the stack after all 27 operations?

b) List the elements remaining in the stack from top to bottom.

c) If you perform three more pop operations, what will be the new top element?

d) How many total push operations and total pop operations were performed?

e) If each push or pop operation takes 1 second, how much total time was spent?

f) Suppose after all the above, you push 85, 90, 95, and then pop twice. List the
final stack from top to bottom.

g) Explain step by step how the LIFO property is applied throughout this sequence.

h) Identify at which operations the stack was emptied completely (if any).

Question 15: Logical Stack Question 2 (Hardest Version)

You have an empty stack S. Perform the following operations in order:
Push 3, Push 6, Push 9, Pop, Push 12, Push 15, Pop, Push 18, Pop, Pop, Push 21,
Push 24, Push 27, Pop, Push 30, Push 33, Pop, Push 36, Pop, Pop, Push 39, Push
42, Push 45, Pop, Push 48, Pop, Pop, Push 51, Push 54, Pop
Questions:
a) What is the top element after all 30 operations?
b) List the elements remaining in the stack from top to bottom.
c) How many times was the stack emptied completely during this sequence?
d) If you perform four more pop operations, what will be the new top element?
e) How many push operations and how many pop operations have been performed?
f) Suppose each operation takes 2 seconds. How much total time is spent?
g) After all operations, you push 57, 60, 63, and then pop three times. List the
final stack.
h) Explain step by step how the LIFO property affects which elements are removed
first.

7
Data Structures Stack Assignment

7 Multiple Choice Questions

Question 16: 50 Easy Stack MCQs
1. Stack follows which principle?
A) FIFO B) LIFO C) Random D) Priority
2. Which operation adds an element to a stack?
A) Pop B) Push C) Enqueue D) Insert
3. Which operation removes the top element from a stack?
A) Push B) Pop C) Dequeue D) Delete
4. What does peek (or top) operation do?
A) Adds an element B) Removes top element
C) Returns the top element without removing it D) Clears the stack
5. What is stack overflow?
A) Popping from empty stack B) Pushing into full stack
C) Accessing top element D) Clearing stack
6. What is stack underflow?
A) Pushing into full stack B) Popping from empty stack
C) Peeking top element D) Reversing stack
7. Which data structure is used internally to implement recursion?
A) Queue B) Stack C) Tree D) Graph
8. Time complexity of push in a stack?
A) O(n) B) O(1) C) O(log n) D) O(n²)
9. Time complexity of pop in a stack?
A) O(n) B) O(1) C) O(log n) D) O(n²)
10. Which is not a stack operation?
A) Push B) Pop C) Peek D) Dequeue
11. Which of the following applications uses stack?
A) Expression evaluation B) Undo feature
C) Parenthesis matching D) All of the above
12. In infix to postfix conversion, which structure is used?
A) Queue B) Stack C) Array D) Tree
13. Which statement is correct for a stack?
A) FIFO B) LIFO C) Sorted access D) Random access
14. How can a stack be implemented?
A) Array B) Linked list C) Both A and B D) Graph
15. Purpose of isEmpty()?
A) Check if full B) Check if empty
C) Peek top element D) Pop element

8
Data Structures Stack Assignment

16. Purpose of isFull()?

A) Check if empty B) Check if full
C) Pop element D) Push element

17. Which is a use case of stack?

A) Function call management B) Undo/Redo in editors
C) Depth-first search D) All of the above

18. Which operation retrieves top element without removing it?

A) Push B) Pop C) Peek D) Enqueue

19. If stack has 5 elements and 2 pops are performed, followed by 3 pushes, how
many elements?
A) 5 B) 6 C) 7 D) 8

20. Which can implement a stack efficiently?

A) Queue B) Linked list C) Tree D) Hash table

21. For checking balanced parentheses, action on opening bracket?

A) Pop B) Push C) Peek D) Ignore

22. For closing bracket, action?

A) Push B) Pop and match top
C) Clear stack D) Ignore

23. For postfix evaluation, what to do with operand?

A) Push onto stack B) Pop from stack
C) Evaluate operator D) Ignore

24. For postfix evaluation, what to do with operator?

A) Push operator B) Pop operands, evaluate, push result
C) Ignore operator D) Clear stack

25. For min-stack, what extra info stored?

A) Maximum value B) Minimum value
C) Top element D) Size

26. In infix to postfix, operator push depends on?

A) Precedence B) Associativity
C) Parentheses D) All of the above

27. Which implementation allows push/pop O(1)?

A) Array only B) Linked list only
C) Both D) Tree

28. Dynamic stack using array, push sometimes?

A) Always O(1) B) Sometimes O(n), amortized O(1)
C) Pop O(n) D) Both O(n)

9
Data Structures Stack Assignment

29. Disadvantage using stack to reverse list?

A) Extra space O(n) B) Slow
C) Cannot preserve order D) None

30. Maximum number of elements in stack determined by?

A) Array size B) Memory
C) Both A & B D) None

31. How is stack used in browser back/forward?

A) Queue B) Stack push/pop
C) Tree D) Graph

32. Linked list stack, where push performed?

A) Head B) Tail C) Middle D) Either

33. Linked list stack, where pop performed?

A) Head B) Tail C) Middle D) Either

34. Stack in recursion stores?

A) Variables only B) Activation records
C) Return values only D) None

35. Operation to check stack empty after parentheses check?

A) isEmpty() B) Peek C) Pop D) Push

36. Scenario naturally using stack?

A) DFS B) BFS
C) FIFO scheduling D) Hashing

37. Operation to add element at bottom?

A) Push B) Pop
C) InsertBottom (custom) D) Peek

38. Operation to remove element at bottom?

A) PopBottom (custom) B) Pop
C) Peek D) Push

39. Algorithm using stack for expression evaluation?

A) Infix to postfix B) Infix to prefix
C) Postfix evaluation D) All of the above

40. Max depth of recursion limited by?

A) Stack size B) Heap size
C) Memory allocation D) Queue size

41. Stack implemented with two queues can be?

A) Push-costly B) Pop-costly
C) Either D) Impossible

10
Data Structures Stack Assignment

42. In infix to postfix, which operator evaluated first?

A) Lower precedence B) Higher precedence
C) Leftmost D) Rightmost

43. Valid stack representation in array?

A) top = -1 B) top = 0
C) top = size D) top = NULL

44. Pop called on empty stack?

A) Returns last element B) Underflow
C) Overflow D) Nothing

45. Stack is a data structure.

A) Linear B) Non-linear
C) Hierarchical D) Graph

46. Reverse string using stack, how to retrieve characters?

A) Push B) Pop C) Peek D) Enqueue

47. Implement undo/redo feature, which DS used?

A) Queue B) Stack C) Tree D) Graph

48. Stack with 10 elements, all popped, is it empty?

A) Yes B) No C) Depends D) Cannot say

49. Which is not an application of stack?

A) DFS B) Parenthesis matching
C) Undo/Redo D) BFS

50. Stack memory in recursion stores?

A) Global variables B) Activation records
C) Heap memory D) Queue elements

11
Data Structures Stack Assignment

Question 17: 50 Competitive/Industry-Ready Stack MCQs

1. What is the main advantage of using a stack in a web browser’s back/forward
feature?
A) LIFO ensures correct navigation B) FIFO ensures correct navigation
C) Saves memory D) Improves speed

2. Which stack implementation is preferred for dynamic memory usage?

A) Array B) Linked list
C) Fixed-size array D) Heap

3. In postfix expression evaluation, operands are:

A) Ignored B) Pushed onto stack
C) Popped immediately D) Stored in array

4. In postfix evaluation, an operator:

A) Pushes itself B) Pops required operands, computes result, pushes result
C) Ignored D) Clears stack

5. In which scenario would you prefer stack over queue?

A) Undo operation B) Print job scheduling
C) Round-robin CPU scheduling D) BFS traversal

6. What is the best-case time complexity for push in a stack implemented via array?
A) O(1) B) O(n) C) O(log n) D) O(n²)

7. What happens when you pop from an empty stack in C/C++?

A) Returns zero B) Undefined behavior
C) Returns top element D) Throws exception

8. Which of these is a real-world application of stack?

A) Recursive function calls B) Undo feature
C) Expression evaluation D) All of the above

9. Which data structure is used to implement function call recursion?

A) Stack B) Queue C) Linked list D) Hash table

10. Which operation is performed first in a stack-based DFS traversal?

A) Push root B) Pop root
C) Visit left child D) Visit right child

11. Which is true for stack overflow?

A) Popping from empty stack B) Pushing to full stack
C) Peeking top element D) Both B and C

12. Which is true for stack underflow?

A) Popping from empty stack B) Pushing to full stack
C) Peeking top element D) Both B and C

13. What is the space complexity of a stack with n elements?

A) O(1) B) O(n) C) O(log n) D) O(n²)

12
Data Structures Stack Assignment

14. Which stack implementation allows dynamic resizing?

A) Array B) Linked list
C) Static array D) Heap

15. You are asked to reverse a string in place using a stack. Which approach is
correct?
A) Push all characters, then pop and overwrite string
B) Pop characters first
C) Use queue instead D) Use hash table

16. To check balanced parentheses using a stack, what should you do when encoun-
tering a closing bracket?
A) Push it B) Pop and match with top
C) Ignore D) Clear stack

17. If a stack is implemented using two queues, which is true?

A) Push-costly method pushes in O(n)
B) Pop-costly method pops in O(n)
C) Both methods are possible
D) All of the above

18. Which operation in stack is always O(1) in a linked list implementation?

A) Push B) Pop C) Peek D) All of the above

19. In expression conversion, infix to postfix uses stack to:

A) Store operands B) Store operators temporarily
C) Reverse string D) Evaluate result

20. Which is better for large unknown size stack?

A) Array B) Linked list
C) Static array D) Queue

21. What is the role of stack in undo/redo feature?

A) Stores history of actions B) Sorts actions
C) Reverses actions automatically D) Stores queue

22. How many stacks are required to implement a queue?

A) One B) Two C) Three D) None

23. Stack is used in topological sorting because:

A) DFS requires LIFO B) BFS requires LIFO
C) Sorting is easier D) Queue cannot be used

24. Which stack type supports getMin() in O(1)?

A) Standard stack B) Min-stack with auxiliary stack
C) Queue-based stack D) Tree stack

25. What is peek operation used for?

A) Adds element B) Removes top
C) Returns top without removing D) Clears stack

13
Data Structures Stack Assignment

26. Which of these is not an application of stack?

A) DFS B) Expression evaluation
C) BFS D) Undo

27. Stack implemented with array, top index = -1. What does this signify?
A) Stack empty B) Stack full
C) Top element = 0 D) None

28. In postfix evaluation, stack stores:

A) Operators B) Operands
C) Both D) None

29. What is the worst-case time complexity to push in dynamic array stack?
A) O(1) amortized B) O(n) sometimes
C) O(log n) D) Both A & B

30. Which is true for stack in recursion?

A) Stores activation records B) Stores return addresses
C) Stores local variables D) All of the above

31. Stack can help evaluate prefix expression by:

A) Traversing right-to-left B) Traversing left-to-right
C) Using queue D) Using heap

32. What happens if peek is called on empty stack?

A) Returns zero B) Underflow
C) Throws exception D) B and C

33. Which is not correct about stack memory?

A) Stores function calls B) Stores heap memory
C) LIFO property D) Fixed size in most systems

34. Which stack operation takes longest in array when resizing?

A) Push B) Pop C) Peek D) All O(1) normally

35. You want to reverse a linked list using stack. Best steps:
A) Push all nodes onto stack, pop to rebuild
B) Reverse pointers directly
C) Use queue D) Use recursion only

36. Stack is used in DFS because:

A) Queue cannot be used
B) DFS requires last visited node access
C) Sorting D) BFS

37. Which statement is true for two-stack implementation of queue?

A) Push costly version uses stack1 for push
B) Pop costly version uses stack2 for pop
C) Both possible D) All above

14
Data Structures Stack Assignment

38. In compiler design, stack is used for:

A) Syntax checking B) Expression evaluation
C) Function calls D) All of the above
39. Which stack operation modifies the stack?
A) Push B) Pop C) Peek D) A and B
40. Stack underflow occurs when:
A) Pop on empty stack B) Push on full stack
C) Peek D) None
41. Stack overflow occurs when:
A) Pop empty B) Push full
C) Peek empty D) Clear stack
42. Minimum stack can be implemented using:
A) Extra stack storing min values B) Linked list only
C) Array only D) Queue
43. In expression evaluation, LIFO ensures:
A) Correct operator precedence B) Correct operand order
C) Both A & B D) None
44. Stack implemented using linked list: which is true?
A) No fixed size B) Push/pop O(1)
C) Memory allocated dynamically D) All above
45. In stack using array, top points to:
A) Last inserted element B) First element
C) Middle element D) NULL
46. Which operation is used for redo feature?
A) Stack push/pop B) Queue
C) Heap D) Linked list
47. Stack is essential in function call management because:
A) Tracks return addresses B) Handles recursion
C) Stores local variables D) All of the above
48. To evaluate nested expressions, stack helps in:
A) Maintaining operator precedence B) Matching parentheses
C) Both D) None
49. Which is true about stack memory in program execution?
A) Stores heap B) LIFO behavior
C) Global variables D) None
50. For stack with n elements, maximum elements after m push and k pop (m greater
than k)?
A) n + m - k B) n - m + k
C) n + k - m D) n

15
Data Structures Stack Assignment

— End of Assignment —
Best of Luck!

Important Notes for Students

Final Reminder:

• Complete all sections with proper diagrams and code

• Write legibly and maintain neat presentation

• Include step-by-step solutions for all conversion and evaluation problems

• Draw stack state diagrams for logical problems

• Circle your answers for MCQs clearly

• Submit on time - Physical submission only

• Double-check your work before submission

• Ensure no plagiarism - all work must be original

Questions? Contact your instructor

Remember: Practice makes perfect!

16