Stacks

Question 1

What is a stack?

Answer 1

A linear data structure that follows the Last In, First Out (LIFO) principle.

Question 2

What is LIFO?

Answer 2

Last In, First Out — the most recently added item is the first to be removed.

Question 3

What are the primary operations on a stack?

Answer 3

Push, pop, peek (or top), and isEmpty.

Question 4

What does the push operation do?

Answer 4

Adds an item to the top of the stack.

Question 5

What does the pop operation do?

Answer 5

Removes and returns the top item from the stack.

Question 6

What does the peek (or top) operation do?

Answer 6

Returns the top item without removing it.

Question 7

What does the isEmpty operation do?

Answer 7

Checks if the stack has no elements.

Question 8

What is the time complexity of push and pop in a stack?

Answer 8

O(1)

Question 9

How can a stack be implemented?

Answer 9

Using arrays or linked lists.

Question 10

What is a stack overflow?

Answer 10

An error that occurs when trying to push onto a full stack (in a fixed-size implementation).

Question 11

What is a stack underflow?

Answer 11

An error that occurs when trying to pop from an empty stack.

Question 12

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

Answer 12

O(n)

Question 13

What is a real-world example of a stack?

Answer 13

Undo functionality in text editors.

Question 14

What is the role of a stack in recursion?

Answer 14

Stores function calls, return addresses, and local variables.

Question 15

How does a stack help evaluate expressions?

Answer 15

Used in parsing and evaluating postfix (Reverse Polish) notation.

Question 16

How is a stack used in Depth-First Search (DFS)?

Answer 16

DFS uses a stack to keep track of vertices to visit.

Question 17

What is the difference between peek and pop?

Answer 17

Peek returns the top element without removing it; pop removes and returns it.

Question 18

What is the difference between a dynamic and static stack?

Answer 18

A dynamic stack grows as needed; a static stack has a fixed size.

Question 19

What is a use case for stack in backtracking algorithms?

Answer 19

Stores previous states for undoing decisions.

Question 20

What data structure is typically used to implement a call stack?

Answer 20

A stack.

Question 21

Can a stack be implemented using a queue?

Answer 21

Yes, using two queues to simulate stack behavior.

Question 22

Can a queue be implemented using a stack?

Answer 22

Yes, using two stacks to simulate queue behavior.

Question 23

What is a minimum stack?

Answer 23

A stack that supports retrieving the minimum element in O(1) time.

Question 24

How do you implement a minimum stack?

Answer 24

Use an auxiliary stack to track minimum values.

Question 25

How is memory managed in a stack-based implementation?

Answer 25

Each push allocates memory; each pop deallocates it (in linked list).

Question 26

What is the role of the call stack in programming languages?

Answer 26

Tracks function calls, parameters, and local variables.

Question 27

What is tail recursion in the context of the call stack?

Answer 27

A recursion where the recursive call is the last operation, enabling optimizations.

Question 28

What causes a stack overflow in recursion?

Answer 28

Too many recursive calls without returning, exhausting stack memory.

Question 29

What is the maximum depth of the call stack?

Answer 29

Depends on the system and language implementation.

Question 30

How do you convert an infix expression to postfix using a stack?

Answer 30

Use the Shunting Yard algorithm developed by Edsger Dijkstra.

Question 31

What is the Shunting Yard algorithm?

Answer 31

An algorithm that converts infix expressions to postfix using a stack.

Question 32

How are function calls stored in memory?

Answer 32

Each function call is stored as a frame on the call stack.

Question 33

What happens when a function returns?

Answer 33

Its frame is removed from the call stack.

Question 34

What is a stack trace?

Answer 34

A report of active stack frames at a certain point during program execution, often shown during errors.

Question 35

What are balanced parentheses problems?

Answer 35

Problems where a stack is used to ensure every opening symbol has a matching closing symbol.

Question 36

What is a common algorithm that uses stacks for string processing?

Answer 36

Checking balanced parentheses, brackets, and braces.

Question 37

How do you reverse a string using a stack?

Answer 37

Push all characters to a stack, then pop them to form the reversed string.

Question 38

What is the time complexity of checking for balanced parentheses using a stack?

Answer 38

O(n)

Question 39

Can a stack be used to simulate a queue?

Answer 39

Yes, by using two stacks: one for enqueue, one for dequeue.

Question 40

What is a monotonic stack?

Answer 40

A stack that maintains its elements in a specific order (increasing or decreasing).

Question 41

What is a use case for a monotonic stack?

Answer 41

Finding the next greater or smaller element for each item in an array.

Question 42

What is a browser history example of a stack?

Answer 42

The back button uses a stack to navigate backward through visited pages.

Question 43

What is a postfix expression?

Answer 43

An expression where the operator comes after the operands (e.g., 2 3 +).

Question 44

How do you evaluate a postfix expression using a stack?

Answer 44

Scan tokens left to right, push operands, pop for operators.

Question 45

What is an expression tree and how is it evaluated?

Answer 45

A binary tree representing an expression, evaluated using post-order traversal with a stack.

Question 46

What is the difference between a stack and a queue?

Answer 46

Stack is LIFO; queue is FIFO.

Question 47

What are sentinel values in stacks?

Answer 47

Special values used to mark boundaries or invalid states.

Question 48

How do stacks support undo operations?

Answer 48

Each action is pushed to the stack; popping undoes the last action.

Question 49

What is the space complexity of recursive function calls?

Answer 49

O(d), where d is the recursion depth.

Question 50

What are stack frames?

Answer 50

Memory blocks storing function info during calls, such as parameters, return addresses, and local variables.