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

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

Quick Revision: Stack Simulation

Key Takeaways

LIFO Principle

Last In, First Out. Access is restricted to the Top.

Operations

Push:

O (1)

| Pop:

O (1)

Simulation Technique

Use a table. Track external variables (

x

f l a g

s u m

) separately. Update state line-by-line.

Example Insight

Sequence pushed:

0, 1, \dots, 8

. Processing started from 8 (even, ignored). Odds encountered:

7, 5, 3, 1

. Each odd pop triggered a discard of the next even number below it. Sum:

7 + 5 + 3 + 1 = 16

Quick Revision: Queue and Deque

Key Takeaways

1. Queue Principle

FIFO (First In, First Out).
• Add at Rear (Enqueue).
• Remove from Front (Dequeue).

2. Deque Principle

Double-Ended flexibility.
• insertFirst, insertLast
• removeFirst, removeLast
• All four are $O (1)$ time.

3. Simulation Discipline

• Explicitly label Front and Rear.
• Cross out removed elements; do not erase.
• Track external variables independently.

4. Implementation Note

Circular arrays require modulo arithmetic $(index \pm 1) (mod N)$ to wrap around correctly without shifting all elements.

Quick Revision: ADT Properties

Key Takeaways

1. Abstract Data Types (ADT)

Defined purely by behavior (operations and properties).
Implementation (array vs. linked list) does not change the ADT.

2. LIFO (Last In, First Out)

Structure: Stack.
Core Idea: Most recently added element is removed first.
Use Case: Backtracking, undo mechanisms, function calls.

3. FIFO (First In, First Out)

Structure: Queue.
Core Idea: Oldest element is removed first.
Use Case: Scheduling, preserving chronological order, BFS.

4. Lookup (Key-Based Retrieval)

Structure: Hash Table / Dictionary.
Core Idea: Retrieve data directly via a unique key.
Complexity: $O (1)$ average for Hash Tables; do not assume $O (1)$ for Trees or Arrays.

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:

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

More short notes in this unit

chapter

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

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

A question from this chapter

Question 1

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

Question 2

Which stack operation removes and returns the topmost element?

Free preview ends here

Login to view the complete short 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