chapter

Stacks, Queues and Deques Notes for GATE DA

Stacks, Queues and Deques notes for GATE DA: 20 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

stacks queues and deques notes

Chapter Roadmap: Stacks, Queues, and Deques

Chapter Journey: Linear Data Structures 01 Stack Operations and Simulation Master Push, Pop, and Top. Learn to trace complex pseudocode executions manually. Weightage Hint: High frequency in simulation questions. 02 Queue and Deque Operations Understand F I F O behavior, circular queues, and double-ended insertion and removal. Weightage Hint: Essential for scheduling and buffering concepts. 03 ADT Properties: FIFO, LIFO, Lookup Formalize the abstract definitions. Match properties to real-world applications. Weightage Hint: Conceptual clarity for matching and theory questions.

The Stack Intuition: The Plate Pile

What is a Stack? A Stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). Real-World Analogy Imagine a stack of books on a table: You place Book A down. You place Book B on top of A. You place Book C on top of B. To access Book A, you must first remove Book C, then Book B. The last item added (C) is the first one removed. Book C Book B Book A Key Terminology Top: The only end where insertion and deletion occur. Push: The operation of adding an element to the top. Pop: The operation of removing the element from the top.

Core Operations: Push and Pop

Fundamental Operations A stack supports two main atomic operations. In exam simulations, tracking these step-by-step is crucial. Operation Description Pre-condition Check Time Complexity Push(x) Inserts element x at the top. Check for Overflow (Is stack full?) O (1) Pop() Removes and returns the top element. Check for Underflow (Is stack empty?) O (1) Peek/Top Returns the top element without removing it. Check for Underflow O (1) Visualizing the State Change Let S be a stack. Initially S = [] . Push(10) \to S = [10] (Top is 10) Push(20) \to S = [10, 20] (Top is 20) Pop() \to Returns 20, S = [10] (Top is 10) Note: In array-based implementations, a pointer top usually tracks the index of the current top element.

17 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

In a Stack data structure, the <code>Push</code> operation inserts a new element at which position?

Question 2

Level 1: Warm-up

Which stack operation removes and returns the topmost element?

Question 3

Level 1: Warm-up

Match the following stack concepts with their precise descriptions: Column I: P. LIFO Principle Q. Push Operation R. Pop Operation Column II: Restricted access to the Top element only Removes and returns the top element in O (1) time Inserts an element at the top after checking for overflow

Question 4

Level 1: Warm-up

Match the following double-ended queue operations with their precise descriptions: Column I: P. insertFirst(e) Q. removeLast() Column II: Removes the element from the rear end. Inserts the element at the front end.

Question 5

Level 1: Warm-up

The access principle followed by a Stack data structure is called LIFO. What does LIFO stand for?

Question 6

Level 1: Warm-up

A stack contains the elements [10, 20, 30] from bottom to top. Which element(s) can be directly accessed without removing any other element?

Question 7

Level 1: Warm-up

In a stack simulation, a variable x is initialized to 0 . The loop condition is while (x < 3) . Inside the loop, Push(x) is executed, followed by x = x + 1 . After the loop terminates, what is the minimum number of Pop() operations required to completely empty the stack?

Question 8

Level 1: Warm-up

An empty stack undergoes a sequence of operations. If the final stack contains exactly 3 elements, and the total number of Push operations performed was 5, how many Pop operations must have been successfully executed, assuming no underflow occurred?

Question 9

Level 1: Warm-up

In an array-based deque implementation of size N, when computing the new rear index after an insertLast operation, what is the minimum number of modulo ((mod N)) operations required in the index update formula to correctly handle the boundary wrap-around?

Question 10

Level 1: Warm-up

An initially empty standard queue undergoes a sequence of operations. If the final queue contains exactly 4 elements, and the total number of Enqueue operations performed was 7, how many successful Dequeue operations must have been executed?

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Stacks, Queues and Deques Notes for GATE DA

Stacks, Queues and Deques notes for GATE DA: 20 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Stacks, Queues, and Deques

Chapter Journey: Linear Data Structures

Stack Operations and Simulation

Master Push, Pop, and Top. Learn to trace complex pseudocode executions manually.

Weightage Hint: High frequency in simulation questions.

Queue and Deque Operations

Understand F I F O behavior, circular queues, and double-ended insertion and removal.

Weightage Hint: Essential for scheduling and buffering concepts.

ADT Properties: FIFO, LIFO, Lookup

Formalize the abstract definitions. Match properties to real-world applications.

Weightage Hint: Conceptual clarity for matching and theory questions.

The Stack Intuition: The Plate Pile

What is a Stack?

A Stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out).

Real-World Analogy

Imagine a stack of books on a table:

You place Book A down.
You place Book B on top of A.
You place Book C on top of B.

To access Book A, you must first remove Book C, then Book B. The last item added (C) is the first one removed.

Book C

Book B

Book A

Key Terminology

Top: The only end where insertion and deletion occur.
Push: The operation of adding an element to the top.
Pop: The operation of removing the element from the top.

Core Operations: Push and Pop

Fundamental Operations

A stack supports two main atomic operations. In exam simulations, tracking these step-by-step is crucial.

Operation	Description	Pre-condition Check	Time Complexity
`Push(x)`	Inserts element $x$ at the top.	Check for Overflow (Is stack full?)	$O (1)$
`Pop()`	Removes and returns the top element.	Check for Underflow (Is stack empty?)	$O (1)$
`Peek/Top`	Returns the top element without removing it.	Check for Underflow	$O (1)$

Visualizing the State Change

Let $S$ be a stack. Initially $S = []$ .

Push(10) $\to S = [10]$ (Top is 10)
Push(20) $\to S = [10, 20]$ (Top is 20)
Pop() $\to$ Returns 20, $S = [10]$ (Top is 10)

Note: In array-based implementations, a pointer top usually tracks the index of the current top element.

Simulating Pseudocode: Step-by-Step Execution

Problem Statement

Consider the following pseudocode:

Create empty stack S
    Set x=0, flag=0, sum=0
    Push x onto S       // S: [0]
    
    while (S is not empty){
        if (flag equals 0){
            Set x = x+1
            Push x onto S
        }
        if (x equals 8):
            Set flag=1
        if (flag equals 1){
            x = Pop(S)
            if (x is odd):
                Pop(S)      // Discard this value
                Set sum = sum + x
        }
    }
    Output sum

Step-by-Step Trace

Phase 1: Building the Stack (Flag = 0)

The loop runs, incrementing x and pushing it until x reaches 8.

Init: $S = [0]$ , $x = 0$ , $f l a g = 0$ , $s u m = 0$
Iteration 1: $x$ becomes 1, push 1. $S = [0, 1]$
...
Iteration 8: $x$ becomes 8, push 8. $S = [0, 1, 2, 3, 4, 5, 6, 7, 8]$
Condition check: $x == 8$ is true, so $f l a g$ becomes 1.
Since $f l a g == 1$ , we execute the pop block: $x = P o p (S) \to x = 8$ . $S = [0, 1, 2, 3, 4, 5, 6, 7]$ . $x$ is not odd, so nothing is added to $s u m$ .

Phase 2: Emptying the Stack (Flag = 1)

Now $f l a g = 1$ . The first if block is skipped. We only evaluate the $x == 8$ check and the $f l a g == 1$ block.

Iteration	Stack Before	`x = Pop(S)`	Is $x$ Odd?	Action	$s u m$	Stack After
1	$[0, \dots, 7]$	$x = 7$	Yes	Pop (discards 6), $s u m = s u m + 7$	7	$[0, \dots, 5]$
2	$[0, \dots, 5]$	$x = 5$	Yes	Pop (discards 4), $s u m = s u m + 5$	12	$[0, \dots, 3]$
3	$[0, \dots, 3]$	$x = 3$	Yes	Pop (discards 2), $s u m = s u m + 3$	15	$[0, 1]$
4	$[0, 1]$	$x = 1$	Yes	Pop (discards 0), $s u m = s u m + 1$	16	$[]$

Next iteration: $S$ is empty. Loop terminates.

Final Answer

The value of

s u m

is 16

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

Question 1 · Programming, Data Structures and Algorithms MCQ

In a Stack data structure, the <code>Push</code> operation inserts a new element at which position?

A.
At the top of the stack
B.
At the bottom of the stack
C.
At the middle of the stack
D.
At a random position

Correct Answer:

Step-by-Step Solution

Key idea: This is a definition recall question about the Push operation, recognizable because it asks where a new element is placed in a stack. Step 1: Recall that a stack follows the LIFO (Last In, First Out) principle. Step 2: To maintain LIFO order, new elements must be added at the same end from which they will be removed. This end is called the top. Step 3: Therefore, Push always inserts at the top of the stack. Answer: Option A

Question 2 · Programming, Data Structures and Algorithms MCQ

Which stack operation removes and returns the topmost element?

A.
Push
B.
Peek
C.
Pop
D.
IsEmpty

Correct Answer:

Step-by-Step Solution

Key idea: This is a definition recall question about stack operations, recognizable because it asks which operation both removes and returns the top element. Step 1: Review the four standard stack operations. - Push: Adds an element to the top. Does not remove. - Peek (or Top): Returns the top element without removing it. - Pop: Removes the top element and returns it. - IsEmpty: Checks whether the stack is empty. Returns a boolean. Step 2: The question asks for the operation that both removes and returns. Only Pop does both. Answer: Option C

Question 3 · Programming, Data Structures and Algorithms MCQ

Match the following stack concepts with their precise descriptions:

Column I:

P. LIFO Principle

Q. Push Operation

R. Pop Operation

Column II:

Restricted access to the Top element only
Removes and returns the top element in $O (1)$ time
Inserts an element at the top after checking for overflow

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

Correct Answer:

Step-by-Step Solution

Key idea: Direct matching of foundational stack terminology to their formal definitions.

Step 1: Analyze P (LIFO Principle). LIFO means Last-In-First-Out, which inherently restricts all access and modification to the "Top" element only. So, P matches with 1.

Step 2: Analyze Q (Push Operation). Push adds an element. The formal definition requires inserting at the top after verifying the stack is not full (checking for overflow). So, Q matches with 3.

Step 3: Analyze R (Pop Operation). Pop removes the top element. The formal definition is removing and returning the top element in $O (1)$ time complexity. So, R matches with 2.

Answer: P-1, Q-3, R-2.

Question 4 · Programming, Data Structures and Algorithms MCQ

Match the following double-ended queue operations with their precise descriptions:

Column I:

P. insertFirst(e)

Q. removeLast()

Column II:

Removes the element from the rear end.
Inserts the element at the front end.

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

Correct Answer:

Step-by-Step Solution

Key idea: Direct matching of deque operation names to their formal definitions.

Step 1: Analyze P (insertFirst(e)). The name explicitly states "insert" (add) and "First" (front end). This matches description 2.

Step 2: Analyze Q (removeLast()). The name explicitly states "remove" (delete) and "Last" (rear end). This matches description 1.

Step 3: Combine the matches: P matches 2, and Q matches 1.

Answer: P-2, Q-1

Question 5 · Programming, Data Structures and Algorithms MCQ

The access principle followed by a Stack data structure is called LIFO. What does LIFO stand for?

A.
Last In, Fast Out
B.
Last In, First Out
C.
Linear In, First Out
D.
Least In, First Out

Correct Answer:

Step-by-Step Solution

Key idea: This is a definition recall question, recognizable because it directly asks for the expansion of the acronym LIFO associated with stacks.

Step 1: Recall that a Stack follows the Last In, First Out principle. The most recently added element is the first one to be removed.

Step 2: Match this to the options. "Last In, First Out" is the correct expansion.

Answer: Option B

Question 6 · Programming, Data Structures and Algorithms MCQ

A stack contains the elements $[10, 20, 30]$ from bottom to top. Which element(s) can be directly accessed without removing any other element?

A.
10, 20, and 30
B.
10 only
C.
20 only
D.
30 only

Correct Answer:

Step-by-Step Solution

Key idea: This is a conceptual question about stack access restrictions, recognizable because it asks which elements are directly accessible in a stack. Step 1: Recall the LIFO principle. A stack restricts all access to one end: the top. Step 2: In the given stack

[10, 20, 30]

, the element 30 is at the top. Step 3: To access 20, you must first Pop 30. To access 10, you must first Pop 30 and 20. Step 4: Therefore, only the top element (30) can be directly accessed without removing anything else. Answer: Option D

Question 7 · Programming, Data Structures and Algorithms MCQ

In a stack simulation, a variable $x$ is initialized to $0$ . The loop condition is while (x < 3). Inside the loop, Push(x) is executed, followed by x = x + 1. After the loop terminates, what is the minimum number of Pop() operations required to completely empty the stack?

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

Correct Answer:

Step-by-Step Solution

Key idea: Simulate the loop to determine the final number of elements in the stack.

Step 1: Initial state: $x = 0$ , Stack is empty.

Step 2: Iteration 1: $x = 0 < 3$ (True). Push(0). Stack: $[0]$ . $x$ becomes $1$ .

Step 3: Iteration 2: $x = 1 < 3$ (True). Push(1). Stack: $[0, 1]$ . $x$ becomes $2$ .

Step 4: Iteration 3: $x = 2 < 3$ (True). Push(2). Stack: $[0, 1, 2]$ . $x$ becomes $3$ .

Step 5: Iteration 4: $x = 3 < 3$ (False). Loop terminates.

Step 6: The stack contains exactly 3 elements. To completely empty it, exactly 3 Pop() operations are required.

Answer: 3

Question 8 · Programming, Data Structures and Algorithms MCQ

An empty stack undergoes a sequence of operations. If the final stack contains exactly $3$ elements, and the total number of Push operations performed was $5$ , how many Pop operations must have been successfully executed, assuming no underflow occurred?

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

Correct Answer:

Step-by-Step Solution

Key idea: Reverse engineering the final stack size using the net change formula.

Step 1: The fundamental relationship for stack size is: Final Size = Total Pushes - Total Successful Pops.

Step 2: We are given: Final Size = $3$ , Total Pushes = $5$ .

Step 3: Substitute the values into the formula: $3 = 5 - Total Pops$ .

Step 4: Solve for Total Pops: $Total Pops = 5 - 3 = 2$ .

Answer: 2

Question 9 · Programming, Data Structures and Algorithms MCQ

In an array-based deque implementation of size $N$ , when computing the new rear index after an insertLast operation, what is the minimum number of modulo ( $(mod N)$ ) operations required in the index update formula to correctly handle the boundary wrap-around?

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

Correct Answer:

Step-by-Step Solution

Key idea: Understanding the circular array index update mechanism for deques.

Step 1: In an array-based deque, the rear index must wrap around to $0$ when it reaches the end of the array (index $N - 1$ ).

Step 2: The standard formula to achieve this wrap-around is $new_index = (current_index + 1) (mod N)$ .

Step 3: This formula explicitly uses exactly one modulo operation per index update to ensure the boundary is handled correctly.

Answer: 1

Question 10 · Programming, Data Structures and Algorithms MCQ

An initially empty standard queue undergoes a sequence of operations. If the final queue contains exactly $4$ elements, and the total number of Enqueue operations performed was $7$ , how many successful Dequeue operations must have been executed?

A.
3
B.
4
C.
7
D.
11

Correct Answer:

Step-by-Step Solution

Key idea: Reverse engineering the final queue size using the net change formula.

Step 1: The fundamental relationship for queue size is: Final Size = Total Enqueues - Total Successful Dequeues.

Step 2: We are given: Final Size = $4$ , Total Enqueues = $7$ .

Step 3: Substitute the values into the formula: $4 = 7 - Total Dequeues$ .

Step 4: Solve for Total Dequeues: $Total Dequeues = 7 - 4 = 3$ .

Answer: 3

stacks queues and deques notes

Chapter Roadmap: Stacks, Queues, and Deques

Chapter Journey: Linear Data Structures

The Stack Intuition: The Plate Pile

What is a Stack?

Real-World Analogy

Key Terminology

Core Operations: Push and Pop

Fundamental Operations

Visualizing the State Change

Try a question

Login to view the complete notes

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 Deques Notes for GATE DA

Chapter Roadmap: Stacks, Queues, and Deques

Chapter Journey: Linear Data Structures

The Stack Intuition: The Plate Pile

What is a Stack?

Real-World Analogy

Key Terminology

Core Operations: Push and Pop

Fundamental Operations

Visualizing the State Change

Simulating Pseudocode: Step-by-Step Execution

Problem Statement

Step-by-Step Trace

Phase 1: Building the Stack (Flag = 0)

Phase 2: Emptying the Stack (Flag = 1)

Final Answer

Stacks, Queues and Deques: 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 notes in this unit