Stacks, Queues and Deques Notes for GATE DA | Free Theory & Solved Questions

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.

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 (2 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:

A

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:

C

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

Stacks, Queues and Deques Notes for GATE DA: Concepts, Formulas, Worked Examples & Practice

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 (2 Problems)

Step-by-Step Solution

Step-by-Step Solution

More notes in this unit

A question from this chapter

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