Stacks - Practice MCQs for CCAT

Correct Answer: D - LIFO

Stack follows LIFO - Last In First Out principle.

Correct Answer: C - O(1)

Push and Pop are O(1) as they operate only on top of stack.

Correct Answer: C - CPU scheduling

CPU scheduling uses queues, not stacks.

Correct Answer: D - Stack

Stack is used to hold operators during infix to postfix conversion.

Correct Answer: C - One stack

Postfix evaluation needs one stack to hold operands.

Correct Answer: C - Stack

Stack matches opening brackets with closing brackets.

Correct Answer: A - Push to full stack

Stack overflow happens when pushing to a stack that is already full.

Correct Answer: B - Pop from empty stack

Stack underflow happens when trying to pop from an empty stack.

Correct Answer: B - Stack

Recursion uses call stack to store function calls and local variables.

Correct Answer: B - DFS/Inorder/Preorder/Postorder

DFS and tree traversals use stack for iterative implementation.

Correct Answer: B - Queue

Two stacks can simulate a queue - one for enqueue operations and one for dequeue.

Correct Answer: C - Returns top without removing

Peek returns the top element without removing it from the stack.

Correct Answer: D - Stack/Recursion

Tower of Hanoi is solved using recursion which internally uses stack.

Correct Answer: B - 2

Two stacks are sufficient to implement a queue efficiently.

Correct Answer: C - Quick sort (iterative)

Iterative quick sort uses explicit stack to store subarray boundaries.

Correct Answer: D - Stack

Stock span problem uses stack to find the span of stock prices efficiently.

Correct Answer: A - Stack

Next greater element is efficiently solved using stack in O(n) time.

Correct Answer: C - -1

Top is initialized to -1 indicating empty stack. First push makes top = 0.

Correct Answer: B - Both arrays and linked lists

Stack can be implemented using both arrays and linked lists with their respective trade-offs.

Correct Answer: A - Stack

Push all characters to stack, then pop them to get reversed string (LIFO property).

Correct Answer: B - LIFO (Last In First Out)

A stack follows LIFO — the last element pushed onto the stack is the first one to be popped. This is analogous to a stack of plates where you take from the top.

Correct Answer: B - O(1) each

In an array-based stack, push increments top and adds the element, while pop reads the element and decrements top. Both are single operations taking O(1) time.

Correct Answer: A - Stack underflow

Attempting to pop from an empty stack causes a stack underflow condition. This is an error that should be handled, as there are no elements to remove.

Correct Answer: A - A B C * +

Due to operator precedence, B * C is evaluated first: B C *. Then A is added: A B C * +. In postfix, operands appear before their operators.

Correct Answer: B - Stack

The call stack stores function return addresses, local variables, and parameters. When a function is called, a stack frame is pushed; when it returns, the frame is popped.

Correct Answer: A - 48

Step by step: 5 3 + gives 8; 8 2 - gives 6; 8 * 6 gives 48. We push operands and apply operators to the top two elements.

Correct Answer: D - top == MAX - 1

When top equals MAX - 1 (using 0-based indexing), the array is full. Any attempt to push another element causes a stack overflow.

Correct Answer: C - CPU scheduling

CPU scheduling typically uses queues (like ready queue, priority queue) to manage processes. Stacks are used for undo/redo, expression evaluation, and backtracking.

Correct Answer: D - * A + B C

In prefix notation, the operator comes before its operands. First, B + C becomes + B C. Then A * (result) becomes * A + B C.

Correct Answer: B - 2

A queue can be implemented using two stacks: one for enqueue operations and one for dequeue operations. Elements are transferred between stacks to reverse the LIFO order to FIFO.

Correct Answer: A - Pop and compare with the top of the stack

When a closing bracket is encountered, the top element is popped and checked if it matches the corresponding opening bracket. If not, the expression has unbalanced parentheses.

Correct Answer: B - 4, 3

Stack follows LIFO. After pushing 1, 2, 3, 4 (top = 4), the first pop returns 4 and the second pop returns 3.

Correct Answer: A - Both prefix and postfix

Both prefix and postfix notations are unambiguous and do not require parentheses. The order of operators and operands alone determines the evaluation order.

Correct Answer: D - Using recursion (implicit call stack)

Recursion uses the program's call stack implicitly. Each recursive call pushes a frame on the call stack, mimicking the behavior of an explicit stack in DFS.

Correct Answer: D - 2ⁿ - 1

The Tower of Hanoi requires 2ⁿ - 1 moves. Each additional disk doubles the moves and adds one. For n = 3: 2³ - 1 = 7 moves.

Correct Answer: D - O(n)

The Shunting Yard algorithm processes each token of the expression exactly once. Each token is pushed and popped from the stack at most once, giving O(n) overall.

Correct Answer: C - 29

Evaluating from right to left: + 3 4 = 7, then * 7 5 = 35, then - 35 6 = 29.

Correct Answer: A - top == -1

When top is initialized to -1, the stack is empty. Each push increments top, and each pop decrements it. When top returns to -1, the stack is empty again.

Correct Answer: A - Growing one stack from each end toward the middle

One stack grows from the left end (index 0 upward) and the other from the right end (index n-1 downward). They overflow only when they meet, maximizing space utilization.

Correct Answer: B - Any type of recursion

Any recursive function can be converted to an iterative one using an explicit stack. The stack simulates the call stack by storing the parameters and local variables for each recursive call.

Correct Answer: B - O(n)

Each element is pushed and popped from the stack at most once across the entire algorithm. Therefore, the total operations are O(n) despite the inner while loop.

Correct Answer: C - A B + C D - *

Convert each sub-expression: A + B becomes A B +, C - D becomes C D -. Then multiply: A B + C D - *. Operands appear before their operators.

Correct Answer: D - n + 1

factorial(n) calls factorial(n-1), which calls factorial(n-2), down to factorial(0). This creates n + 1 stack frames (from factorial(n) to factorial(0)).

Correct Answer: A - Both A and B are valid approaches

Both approaches work. Pushing all characters and popping gives the reverse; comparing with original checks palindrome. Pushing only the first half and comparing with the second half is more efficient.

Correct Answer: D - O(n)

In the worst case, all operands could be pushed before any operator is encountered. The stack can hold up to O(n) elements.

Correct Answer: C - Next greater element for each element in an array

The next greater element problem is solved efficiently using a stack in O(n) time. BFS, shortest path, and level-order traversal all use queues, not stacks.

Correct Answer: D - Pop the stack top and add to output, then compare again

When the scanned operator has lower or equal precedence, we pop the stack top to the output and repeat the comparison. We push the scanned operator only when the stack is empty or its precedence is higher than the top.

Correct Answer: A - 3, 1, 2, 4

After popping 3, the stack has 1, 2 (top). To pop 1 next, we must first pop 2. The sequence 3, 1, 2, 4 requires popping 1 before 2, which is impossible since 2 is on top of 1.

Correct Answer: C - Both inorder and preorder

Both inorder and preorder traversals can be implemented iteratively using a single stack. Preorder pushes and pops nodes while visiting them; inorder pushes left children, pops, visits, and goes right.

Correct Answer: A - Stack uses LIFO, queue uses FIFO

A stack uses LIFO (Last In, First Out) — the newest element is removed first. A queue uses FIFO (First In, First Out) — the oldest element is removed first.