Stacks, Queues and Linked Lists Practice Questions for GATE CS

Solve 60+ Stacks, Queues and Linked Lists practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Stacks, Queues, and Linked Lists

Chapter Journey

1. Stack Operations and Augmented Stacks

Current Topic

Focus: Mastering the Last-In-First-Out (LIFO) principle and step-by-step tracing.

Key Skill: Optimizing stacks for constant-time minimum queries.

2. Queue Operations, Reversal and Stack-Queue Interaction

Focus: First-In-First-Out (FIFO) principle and simulating queues with stacks.

Key Skill: Reversal algorithms and data structure interactions.

3. Linked List Manipulation, Recursion and Complexity

Focus: Pointer manipulation and recursive traversal.

Key Skill: Time-space tradeoffs in linear data structures.

Exam Weightage Hint: Stacks (0.41), Queues (0.41), Linked Lists (0.55). Linked lists carry the highest weight, but stack augmentation is a frequent, high-value target.

Hero Concept: The Stack and Its Core Operations

The Core Intuition

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The element added most recently is the first one to be removed.

push(x) Inserts element $x$ at the top.
pop() Removes and returns the top element.
peek() Returns the top element without removing it.
isEmpty() Checks if the stack contains no elements.

Complexity: All standard stack operations execute in $O (1)$ time complexity, regardless of the number of elements

n

. This makes stacks indispensable for function call management, expression evaluation, and backtracking.

Stacks, Queues and Linked Lists: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Programming and Data Structures MCQ

An empty stack and an empty queue undergo the following operations:

Stack: push(10), push(20), pop(), push(30)

Queue: enqueue(10), enqueue(20), dequeue(), enqueue(30)

Let $S$ be the sum of elements currently in the stack, and $Q$ be the sum of elements currently in the queue. Which of the following correctly describes the relationship between $S$ and $Q$ ?

A.
$S = Q$
B.
$S > Q$
C.
$S < Q$
D.
$S = 2 Q$

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the fundamental difference between LIFO (stack) and FIFO (queue) removal constraints.

Step 1: Trace the Stack (LIFO).

push(10) $\to$ [10]
push(20) $\to$ [10, 20]
pop() $\to$ removes 20 (top). Stack is [10]
push(30) $\to$ [10, 30]
Sum $S = 10 + 30 = 40$ .

Step 2: Trace the Queue (FIFO).

enqueue(10) $\to$ [10]
enqueue(20) $\to$ [10, 20]
dequeue() $\to$ removes 10 (front). Queue is [20]
enqueue(30) $\to$ [20, 30]
Sum $Q = 20 + 30 = 50$ .

Step 3: Compare $S$ and $Q$ . $40 < 50$ , so $S < Q$ .

Answer: $S < Q$

Question 2 · Programming and Data Structures MCQ

An augmented stack stores pairs of $(v a l u e, c u r r e n t_min)$ to achieve $O (1)$ minimum queries. The current top pair in the stack is $(9, 3)$ . If we push a new arbitrary integer element $x$ , the new top pair will be $(x, m)$ . What is the maximum possible value of $m$ ?

A.
$x$
B.
9
C.
3
D.
0

Correct Answer:

Step-by-Step Solution

Key idea: This is an observation question testing the boundary condition of the augmented stack's minimum tracking logic.

Step 1: Recall the rule for the pair approach: when pushing $x$ , the new minimum $m$ is calculated as $m = min (x, c u r r e n t_min)$ .

Step 2: The current minimum (the second element of the top pair) is 3.

Step 3: Therefore, $m = min (x, 3)$ .

Step 4: By the definition of the minimum function, $min (x, 3)$ can never exceed 3, regardless of how large $x$ is. The maximum possible value for $m$ is exactly 3.

Answer: 3

Question 3 · Programming and Data Structures MCQ

A stack is initially empty. The following operations are performed in sequence:

push(10), push(-5), pop(), push(-3), pop()

What is the sum of the values returned by the two pop operations?

A.
8
B.
-8
C.
2
D.
-2

Correct Answer:

Step-by-Step Solution

Key idea: This is a basic LIFO tracing question testing careful handling of negative numbers during sequential operations.

Step 1: push(10) $\to$ Stack: [10]

Step 2: push(-5) $\to$ Stack: [10, -5]

Step 3: pop() $\to$ Removes and returns -5. Stack: [10]

Step 4: push(-3) $\to$ Stack: [10, -3]

Step 5: pop() $\to$ Removes and returns -3. Stack: [10]

Step 6: Sum the returned values: $(- 5) + (- 3) = - 8$ .

Answer: -8

Question 4 · Programming and Data Structures MCQ

An augmented stack stores pairs of $(v a l u e, c u r r e n t_min)$ . The stack currently contains the following pairs from bottom to top:

$(10, 10), (5, 5), (8, 5)$

If we perform push(3), what is the new top pair?

A.
(3, 3)
B.
(3, 5)
C.
(3, 10)
D.
(8, 3)

Correct Answer:

Step-by-Step Solution

Key idea: This is an augmented stack question. When pushing a new value, the current_min is updated as min(new_value, previous_min).

Step 1: Identify the current state.

Stack from bottom to top: (10, 10), (5, 5), (8, 5)
Current top pair: (8, 5)
Current minimum: 5 (from the top pair's second element)

Step 2: Perform push(3).

New value: 3
Previous minimum: 5
New minimum: min(3, 5) = 3

Step 3: Form the new top pair.

New pair: (value, new_min) = (3, 3)

Step 4: Update the stack.

Stack from bottom to top: (10, 10), (5, 5), (8, 5), (3, 3)
New top pair: (3, 3)

Answer: A

Question 5 · Programming and Data Structures MCQ

Which of the following statements is TRUE regarding reversing a queue $Q_{1}$ of $N$ elements into $Q_{2}$ using ONLY Enqueue and Dequeue operations?

A.
The time complexity of the reversal is strictly bounded by $O (N)$ .
B.
Every element is dequeued from $Q_{1}$ exactly once.
C.
An auxiliary stack is used to temporarily store elements during rotation.
D.
The total number of enqueue operations on $Q_{2}$ is exactly $N$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the time complexity and operation constraints of two-queue reversal.

Step 1: Analyze the constraint. The problem specifies "using ONLY Enqueue and Dequeue operations". This explicitly forbids auxiliary data structures like stacks.

Step 2: Evaluate option A. Reversing a queue using two queues requires cycling elements, which strictly bounds the time complexity at $O (N^{2})$ , not $O (N)$ .

Step 3: Evaluate option B. $Q_{1}$ acts strictly as the source. To move all $N$ elements to $Q_{2}$ , every element must be dequeued from $Q_{1}$ exactly once. This is true.

Step 4: Evaluate option C. This violates the "ONLY Enqueue and Dequeue" constraint.

Step 5: Evaluate option D. $Q_{2}$ receives $N$ elements from $Q_{1}$ , plus additional enqueues during rotation. The total enqueues on $Q_{2}$ is $\frac{N ( N + 1 )}{2}$ , not $N$ .

Answer: B

Question 6 · Programming and Data Structures MCQ

Consider the following Assertion (A) and Reason (R):

Assertion (A): In the two-queue reversal algorithm for $N$ elements, the total number of Enqueue operations performed on $Q_{2}$ is $\frac{N ( N + 1 )}{2}$ .

Reason (R): $Q_{2}$ acts as both the destination for the $N$ elements from $Q_{1}$ and the buffer for rotating the already placed elements.

Select the correct option:

A.
Both A and R are true, and R is the correct explanation of A.
B.
Both A and R are true, but R is NOT the correct explanation of A.
C.
A is true, but R is false.
D.
A is false, but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is a construction question validating the logical relationship between the roles of $Q_{1}$ and $Q_{2}$ .

Step 1: Construct the mental model of the two-queue reversal algorithm. $Q_{1}$ is the source, $Q_{2}$ is the destination and rotation buffer.

Step 2: Evaluate Assertion (A). For each of the $N$ elements moved from $Q_{1}$ , the elements already in $Q_{2}$ must be cycled (dequeued and enqueued back to $Q_{2}$ ) to maintain the reversed order. The total enqueues on $Q_{2}$ sum to $1 + 2 + \dots + N = \frac{N ( N + 1 )}{2}$ . Assertion (A) is true.

Step 3: Evaluate Reason (R). $Q_{2}$ indeed absorbs all elements from $Q_{1}$ and also handles the rotation enqueues. Reason (R) is true.

Step 4: Check the explanatory link. Reason (R) perfectly describes the mechanical roles that cause the mathematical sum in Assertion (A). Therefore, R is the correct explanation of A.

Answer: A

Question 7 · Programming and Data Structures MCQ

Which of the following statements is TRUE regarding the reversal of a queue $Q_{1}$ of $N$ elements into an empty queue $Q_{2}$ using ONLY Enqueue and Dequeue operations on $Q_{1}$ and $Q_{2}$ ?

A.
The time complexity is $O (N)$ because each element is transferred directly from $Q_{1}$ to $Q_{2}$ .
B.
The algorithm requires an auxiliary stack to temporarily hold elements during cycling.
C.
The total number of Dequeue operations performed on $Q_{1}$ is exactly $N$ .
D.
The total number of Enqueue operations performed on $Q_{1}$ is $N$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the constraints and mechanics of two-queue reversal.

Step 1: Analyze the constraint. The problem specifies "using ONLY Enqueue and Dequeue operations on $Q_{1}$ and $Q_{2}$ ". This explicitly forbids auxiliary data structures like stacks or arrays.

Step 2: Evaluate the roles. $Q_{1}$ starts with $N$ elements and acts strictly as the source. It only loses elements via Dequeue operations. It never receives elements back.

Step 3: Bound the operations. To empty $Q_{1}$ completely, exactly $N$ Dequeue operations must be performed on it. Therefore, the statement "The total number of Dequeue operations performed on $Q_{1}$ is exactly $N$ " is true.

Step 4: Evaluate other options. Option A is false because cycling requires $O (N^{2})$ time. Option B is false because it violates the "ONLY Enqueue and Dequeue" constraint. Option D is false because $Q_{1}$ receives 0 Enqueue operations.

Answer: C

Question 8 · Programming and Data Structures MCQ

Consider the following Assertion (A) and Reason (R):

Assertion (A): In the two-queue reversal algorithm for $N$ elements, the total number of Dequeue operations performed on the destination queue $Q_{2}$ is $\frac{N ( N - 1 )}{2}$ .

Reason (R): For each of the $N$ elements moved from $Q_{1}$ to $Q_{2}$ , it must be cycled past the elements already in $Q_{2}$ , requiring a number of Dequeue operations on $Q_{2}$ equal to the current size of $Q_{2}$ .

Select the correct option:

A.
Both A and R are true, and R is the correct explanation of A.
B.
Both A and R are true, but R is NOT the correct explanation of A.
C.
A is true, but R is false.
D.
A is false, but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is a construction question validating the logical relationship between the cycling mechanics and operation counts.

Step 1: Construct the mental model of the two-queue reversal algorithm.

$Q_{1}$ starts with $N$ elements. It acts strictly as the source.
$Q_{2}$ starts empty. It acts as the destination and the rotation buffer.

Step 2: Evaluate Reason (R). When the $k$ -th element is moved from $Q_{1}$ to $Q_{2}$ , there are already $k - 1$ elements in $Q_{2}$ . To place the new element at the front (relative to the final reversed order), the existing $k - 1$ elements must be cycled. Cycling $k - 1$ elements requires exactly $k - 1$ Dequeue operations on $Q_{2}$ . Reason (R) is true.

Step 3: Evaluate Assertion (A). The total number of Dequeue operations on $Q_{2}$ is the sum of Dequeues for each of the $N$ elements: $0 + 1 + 2 + \dots + (N - 1) = \frac{N ( N - 1 )}{2}$ . Assertion (A) is true.

Step 4: Check the explanatory link. Reason (R) perfectly describes the mechanical cause that directly results in the mathematical sum stated in Assertion (A). Therefore, R is the correct explanation of A.

Answer: A

Question 9 · Programming and Data Structures MCQ

Match the operation with its minimum count when reversing an $N$ -element queue $Q_{1}$ into an empty queue $Q_{2}$ using ONLY Enqueue and Dequeue operations on $Q_{1}$ and $Q_{2}$ .

List-I (Operation)

P. Enqueue operations on $Q_{1}$

Q. Dequeue operations on $Q_{1}$

List-II (Count)

$0$
$N$
$\frac{N ( N + 1 )}{2}$

A.
P-1, Q-2
B.
P-2, Q-1
C.
P-1, Q-3
D.
P-3, Q-2

Correct Answer:

Step-by-Step Solution

Key idea: In the standard two-queue reversal algorithm, $Q_{1}$ acts strictly as the source and $Q_{2}$ as the destination.

Step 1: Since $Q_{1}$ is only the source, elements are only removed from it. Thus, it undergoes exactly $N$ Dequeue operations.

Step 2: No elements are ever added back to $Q_{1}$ . Therefore, the number of Enqueue operations on $Q_{1}$ is exactly $0$ .

Answer: P matches with 1, and Q matches with 2.

Question 10 · Programming and Data Structures MCQ

Consider the following sequence of operations performed on an initially empty stack:

push, push, pop, push, pop, pop

A student claims that the stack becomes empty exactly 3 times during this sequence. What is the actual minimum number of times the stack becomes empty?

A.
3
B.
2
C.
1
D.
0

Correct Answer:

Step-by-Step Solution

Key idea: This is a contradiction question testing precise step-by-step tracing against a flawed mental model of stack emptiness.

Step 1: Trace the stack size step-by-step.

push $\to$ size 1
push $\to$ size 2
pop $\to$ size 1
push $\to$ size 2
pop $\to$ size 1
pop $\to$ size 0 (Stack is empty. Count = 1)

Step 2: Evaluate the student's claim. The student likely counted every pop operation as an event that makes the stack empty.

Step 3: The stack only reaches size 0 once, at the very end.

Answer: 1

Try a question

Login to view the complete practice questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Stacks, Queues and Linked Lists Practice Questions for GATE CS

Chapter Roadmap: Stacks, Queues, and Linked Lists

Chapter Journey

Hero Concept: The Stack and Its Core Operations

The Core Intuition

Stacks, Queues and Linked Lists: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit