Stacks & Queues – Concepts & Operations | GATE 2026 CSE

Concept Notes

1. Stack

• Definition: Linear data structure following LIFO (Last In, First Out) principle.
• Operations:
  1. push(x) – Insert element x on top of the stack.
  2. pop() – Remove the topmost element.
  3. peek()/top() – Return the top element without removing.
  4. isEmpty() – Check if the stack is empty.
• Example:
  Stack: [ ] → push 5 → [5] → push 3 → [5,3] → pop() → [5]
• Applications:
  • Expression evaluation (infix, postfix, prefix)
  • Undo/Redo in editors
  • Function call stack in recursion
  • Balanced parentheses checking

---

2. Queue

• Definition: Linear data structure following FIFO (First In, First Out) principle.
• Types:
  1. Simple Queue – Normal enqueue & dequeue.
  2. Circular Queue – Reuses empty spaces after dequeues.
  3. Deque (Double-Ended Queue) – Insert & remove at both ends.
  4. Priority Queue – Dequeue based on priority.
• Operations:
  1. enqueue(x) – Add element to rear.
  2. dequeue() – Remove element from front.
  3. front()/peek() – Return front element.
  4. isEmpty() – Check if queue is empty.
• Example:
  Queue: [ ] → enqueue 2 → [2] → enqueue 4 → [2,4] → dequeue() → [4]
• Applications:
  • CPU scheduling
  • Print queue
  • BFS traversal in graphs
  • Data buffering (keyboard, IO devices)

---

⚙️ Formulas / Key Points

• Stack Size = Number of elements in stack
• Queue Size = Rear – Front + 1 (linear)
• Circular Queue Size = (Rear - Front + MAX) % MAX + 1

Time Complexity:

• Stack → push/pop/top: O(1)
• Queue → enqueue/dequeue/front: O(1)

---

🔟 10 MCQs – GATE 2026 CSE

Q1. A stack with elements [2,4,6] undergoes push(8), pop(), push(10). What is the top element?
A) 6
B) 8
C) 10
D) 4

Q2. Which operation in stack does not remove the element?
A) push()
B) pop()
C) peek()/top()
D) isEmpty()

Q3. Which of the following follows FIFO?
A) Stack
B) Queue
C) Tree
D) Graph

Q4. A circular queue of size 5 currently has front=2, rear=4. How many elements are present?
A) 2
B) 3
C) 4
D) 5

Q5. Which queue type allows insertion and deletion at both ends?
A) Simple Queue
B) Circular Queue
C) Priority Queue
D) Deque

Q6. Which of these is not an application of stack?
A) Undo feature
B) BFS traversal
C) Expression evaluation
D) Function call stack

Q7. Time complexity of enqueue in array-based circular queue?
A) O(1)
B) O(n)
C) O(log n)
D) O(n^2)

Q8. If a stack is implemented using an array of size 10, what happens if we push the 11th element?
A) Overflow
B) Underflow
C) Successful push
D) Error in pop()

Q9. A queue has elements [A,B,C]. After enqueue(D), dequeue(), dequeue(), what is the front?
A) A
B) B
C) C
D) D

Q10. Which data structure is suitable for backtracking problems?
A) Queue
B) Stack
C) Linked List
D) Tree

---

✅ Answer Key

Q.No	Answer
1	C
2	C
3	B
4	B
5	D
6	B
7	A
8	A
9	C
10	B

---

🧠 Explanations

1. [2,4,6] → push 8 → [2,4,6,8] → pop() → [2,4,6] → push 10 → [2,4,6,10] → top = 10
2. peek()/top() only returns element, does not remove it.
3. Queue follows FIFO, stack is LIFO.
4. Linear queue size = rear – front + 1 = 4 – 2 + 1 = 3
5. Deque supports insertion & deletion at both ends.
6. BFS uses queue, not stack.
7. Array-based circular queue uses direct index → O(1)
8. Array is full → Overflow occurs
9. [A,B,C] → enqueue(D) → [A,B,C,D] → dequeue() → [B,C,D] → dequeue() → [C,D] → front = C
10. Backtracking uses stack to remember previous states.

---

🎯 Motivation / Why Practice Matters

• Stacks & Queues are foundational for algorithms and system programming.
• GATE questions test conceptual clarity + numerical simulation.
• Useful in recursion, graph traversal, CPU scheduling, and expression evaluation.

---

📲 CTA

Join our GATE 2026 CSE Prep Community: @LearnNewThingsHub