CLASS XII — COMPUTER SCIENCE

CHAPTER 4

Queue & Deque

Exam-Optimized Notes | Board + KCET Level

"We could say we want the Web to reflect a vision of the world where everything is done democratically." —
Tim Berners-Lee
1. CHAPTER OVERVIEW
Chapter Name
Queue & Deque (NCERT Class XII Computer Science — Chapter 4)

Key Themes
• Queue: FIFO/FCFS principle, FRONT (HEAD) and REAR (TAIL) ends
• Queue operations: ENQUEUE (insert at REAR), DEQUEUE (remove from FRONT), PEEK, IS
EMPTY, IS FULL
• Python implementation using list: append() for ENQUEUE, pop(0) for DEQUEUE
• Real-life and CS applications of Queue
• Deque (Double Ended Queue): insert+delete from BOTH ends
• Deque operations: insertFront, insertRear, deletionFront, deletionRear, getFront, getRear
• Algorithm 4.1: Palindrome check using Deque

Real-World Applications
• Queue: Bank queues, train waiting list (W/L), toll booth, IVRS call hold
• Queue (CS): OS job/CPU scheduling, web server request handling, printer spooling
• Deque: Browser history (URL storage with fixed limit), Undo/Redo, Palindrome check
2. CONCEPTUAL FOUNDATION (DEEP EXPLANATION)
2.1 Queue — First Principles
Stack: insert AND delete from the SAME end (TOP). Queue is different: insertions at one end, deletions at the
OTHER.
Intuition: A bank queue. Person joining goes to the BACK. Person being served leaves from the FRONT. No
cutting in line.

FIFO — The Core Law of Queue

FIFO = First-In-First-Out (= FCFS: First-Come-First-Served)

The FIRST element inserted is the FIRST removed. The element LONGEST in the queue leaves first.
REAR (TAIL): Insertion end. FRONT (HEAD): Deletion end.

2.2 Python List for Queue — Key Insight

Convention: RIGHT END (append()) = REAR. LEFT END (index 0, pop(0)) = FRONT.

STACK vs QUEUE in Python List

STACK: append() PUSH + pop() POP — SAME end (LIFO)

QUEUE: append() ENQUEUE + pop(0) DEQUEUE — DIFFERENT ends (FIFO)

2.3 Deque — Double Ended Queue

Deque (pronounced 'deck') allows insertion AND deletion from BOTH FRONT and REAR with NO restriction.
It can simulate both Stack and Queue.
Insert End Delete End Behaves Like

SAME end SAME end STACK (LIFO)

REAR FRONT QUEUE (FIFO)

Any end freely Any end freely Full DEQUE

2.4 Palindrome Using Deque — Intuition

A palindrome reads same forward and backward ('madam', 'racecar'). Load string into deque at REAR.
Simultaneously remove from FRONT and REAR, compare. All matches = palindrome.
3. DEFINITIONS & KEY TERMS

Term Precise Exam-Ready Definition

Queue Ordered linear data structure following FIFO where

elements are inserted at REAR and removed from
FRONT.

FIFO First-In-First-Out: element inserted first is removed first.

Also FCFS (First-Come-First-Served).

FRONT (HEAD) End of queue from which elements are REMOVED

(dequeue). Points to oldest element.

REAR (TAIL) End of queue where new elements are INSERTED

(enqueue). Points to most recent element.

ENQUEUE Insertion operation — adds element at REAR end of

queue.

DEQUEUE Deletion operation — removes element from FRONT

end of queue.

PEEK Reads FRONT element without removing it. Non-

destructive read.

IS EMPTY Returns True if queue has no elements. Prevents

UNDERFLOW.

IS FULL Returns True if queue is at maximum capacity.

Prevents OVERFLOW. Not needed in Python.

Overflow (Queue) Exception when ENQUEUE is attempted on a FULL

queue.

Underflow (Queue) Exception when DEQUEUE is attempted on an EMPTY

queue.

Deque Double Ended Queue — linear data structure where

insertion and deletion can happen from BOTH ends
(Front and Rear).

insertFront Deque: insert element at FRONT end.

insertRear Deque: insert element at REAR end (same as

enqueue).

deletionFront Deque: remove element from FRONT (same as

dequeue).

deletionRear Deque: remove element from REAR.

getFront Deque: peek at FRONT value without removing.

getRear Deque: peek at REAR value without removing.

4. COMPLETE PYTHON IMPLEMENTATION
4.1 Queue — All Functions
myQueue = list() # Empty queue

def enqueue(myQueue, element):

[Link](element) # append = add at END (REAR)

def isEmpty(myQueue):
if len(myQueue) == 0:
return True
else:
return False

def dequeue(myQueue):
if not (isEmpty(myQueue)):
return [Link](0) # pop(0) = remove from START (FRONT)
else:
print('Queue is empty')

def size(myQueue):
return len(myQueue)

def peek(myQueue):
if isEmpty(myQueue):
print('Queue is empty')
return None
else:
return myQueue[0] # index 0 = FRONT

4.2 Queue Function Summary

Function Parameters Returns List Method Key Note

enqueue(q, e) queue, element None append(e) Adds at END

(REAR)

dequeue(q) queue Element/None pop(0) Removes from

START (FRONT)

isEmpty(q) queue True/False len(q)==0 Prevents underflow

size(q) queue Integer len(q) Count of elements

peek(q) queue Element/None q[0] Reads FRONT, no

removal

4.3 Deque — All Functions (Program 4-2)

myDeque = list() # Empty deque
 def insertFront(myDeque, element):
[Link](0, element) # insert at index 0 = FRONT

def insertRear(myDeque, element):

[Link](element) # append at END = REAR

def isEmpty(myDeque):
return len(myDeque) == 0

def deletionFront(myDeque): # same as dequeue

if isEmpty(myDeque):
print('Queue underflow')
else:
return [Link](0)

def deletionRear(myDeque):
if not isEmpty(myDeque):
return [Link]() # pop() removes from END = REAR
else:
print('Queue underflow')

def getFront(myDeque):
if not isEmpty(myDeque):
return myDeque[0]
else:
print('Queue empty')

def getRear(myDeque):
if not isEmpty(myDeque):
return myDeque[len(myDeque) - 1]
else:
print('Deque empty')

4.4 Deque Function Summary

Function List Method End Affected Key Note

insertFront(d, e) insert(0, e) FRONT Adds at beginning (index

0)

insertRear(d, e) append(e) REAR Same as enqueue()

deletionFront(d) pop(0) FRONT Same as dequeue()

deletionRear(d) pop() REAR pop() without argument =

from end

getFront(d) d[0] FRONT Peek front, no removal

getRear(d) d[len-1] REAR Peek rear, no removal

isEmpty(d) len(d)==0 N/A Same as queue isEmpty()

5. ALGORITHMS
5.1 Algorithm 4.1: Palindrome Check Using Deque
Step 1: Traverse string left to right, one character at a time.
Step 2: Insert each character at REAR using INSERTREAR.
Step 3: Repeat Steps 1-2 for ALL characters.
(deque now has entire string, front=first char, rear=last char)

Step 4: Remove from FRONT (DELETIONFRONT) and REAR (DELETIONREAR).

Step 5: Compare removed characters.
Step 6: IF equal: repeat Steps 4-5 until deque has 0 or 1 elements -> PALINDROME
ELSE: characters differ -> NOT a PALINDROME, stop.

Trace: 'madam'
Iteration Deque State Front Removed Rear Removed Match?

After loading m a d a m - - -

1 a d a m m YES

2 d a a YES

End (1 element) d - - PALINDROME

Python Code for Palindrome:

def isPalindrome(s):
dq = list()
for ch in s:
[Link](ch) # insertRear
while len(dq) > 1: # loop until 0 or 1 element
front = [Link](0) # deletionFront
rear = [Link]() # deletionRear
if front != rear:
return False
return True

word = input('Enter string: ')

print('Palindrome:', isPalindrome(word))

6. ILLUSTRATIVE EXAMPLES
Example 1: NCERT Figure 4.3 Queue Trace
Operation Queue (Front→Rear) Notes

Initial [] Empty
enqueue(Z) [Z] F→Z←R

enqueue(X) [Z X]

enqueue(C) [Z X C]

dequeue() [X C] Z removed (FRONT)

enqueue(V) [X C V]

dequeue() [C V] X removed (FRONT)

dequeue() [V] C removed (FRONT)

Example 2: NCERT Exercise Q6 — Queue Status Trace

Operation Queue State (Front→Rear) Notes

enqueue(34) [ 34 ]

enqueue(54) [ 34 54 ]

dequeue() [ 54 ] 34 removed

enqueue(12) [ 54 12 ]

dequeue() [ 12 ] 54 removed

enqueue(61) [ 12 61 ]

peek() [ 12 61 ] Returns 12 (FRONT), no change

dequeue() [ 61 ] 12 removed

dequeue() [] 61 removed

dequeue() UNDERFLOW Queue empty

dequeue() UNDERFLOW Still empty

enqueue(1) [1]

Example 3: NCERT Exercise Q7 — Deque Status Trace

Operation Deque State (Front→Rear) Notes

Initial [] Empty

peek() [] Queue empty — None returned

insertFront(12) [ 12 ] 12 at FRONT

insertRear(67) [ 12 67 ] 67 at REAR

deletionFront() [ 67 ] 12 removed from FRONT

insertRear(43) [ 67 43 ] 43 at REAR

deletionRear() [ 67 ] 43 removed from REAR

deletionFront() [] 67 removed from FRONT

 deletionRear() UNDERFLOW Deque empty

Example 4: Palindrome Trace for 'racecar'

Iter Deque Front Rear Match?
(Front→Rear)

Load r a c e c a r - - -

1 a c e c a r r YES

2 c e c a a YES

3 e c c YES

End 1 element - - PALINDROME

Example 5: Non-palindrome 'hello'

Iter Deque Front Rear Match?

Load h e l l o - - -

1 e l l h o NO — STOP

Result: 'hello' is NOT a palindrome.

7. EDGE CASES & EXCEPTIONS
7.1 Stack vs Queue vs Deque — Master Comparison
Feature Stack Queue Deque

Principle LIFO FIFO No restriction

Insert at ONE end (TOP) REAR only FRONT or REAR

Delete from ONE end (TOP) FRONT only FRONT or REAR

Python insert append() append() append() OR insert(0,e)

Python delete pop() pop(0) pop() OR pop(0)

Overflow possible? No (Python) No (Python) No (Python)

Underflow possible? YES YES YES

7.2 pop() vs pop(0) — Critical Difference

Method Removes from Used in

[Link]() END = REAR = last element Stack POP, Deque deletionRear

[Link](0) START = FRONT = index 0 Queue dequeue, Deque

deletionFront

TRAP: Using pop() in dequeue removes from REAR (wrong). Must use pop(0) for FRONT removal.

7.3 insertFront() — Why insert(0, element)?

dq = [10, 20, 30]
[Link](0, 5) # -> [5, 10, 20, 30] (5 at FRONT)
[Link](40) # -> [5, 10, 20, 30, 40] (40 at REAR)

7.4 Palindrome: Odd vs Even Length

• ODD length ('madam'): After all comparisons, 1 element remains in deque (middle char). This is
STILL a palindrome.
• EVEN length ('abba'): After all comparisons, deque is EMPTY. Still palindrome.
• Loop condition: while len(deque) > 1 — handles BOTH cases correctly.

7.5 Activity Answers

Activity 4.3 Answer

If insertion AND deletion from SAME end in a deque → behaves as STACK (LIFO).
 Activity 4.4 Answer

If insertion and deletion from OPPOSITE ends in a deque → behaves as QUEUE (FIFO).

7.6 Exercise Q1g Answer — Deque Deletion Sequence

Initial deque: [z, x, c, v, b] (Front=z, Rear=b)
Deletions received: z, b, v, x, c
1. deletionFront() -> removes z -> [x, c, v, b]
2. deletionRear() -> removes b -> [x, c, v]
3. deletionRear() -> removes v -> [x, c]
4. deletionFront() -> removes x -> [c]
5. deletionFront() -> removes c -> []
Sequence: deletionFront, deletionRear, deletionRear, deletionFront, deletionFront

8. VISUALIZATION SUPPORT
8.1 Queue Diagram Format
FRONT -> [ A | B | C | D ] <- REAR
^ ^
(next dequeue) (last enqueued)

After enqueue(E): [ A | B | C | D | E ]
After dequeue(): [ B | C | D | E ] (A removed from FRONT)

8.2 Deque Diagram Format

insertFront/deletionFront <-> [ 10 | 20 | 30 | 40 | 50 ] <-> insertRear/deletionRear

insertFront(5): [ 5 | 10 | 20 | 30 | 40 | 50 ]
insertRear(60): [ 5 | 10 | 20 | 30 | 40 | 50 | 60 ]
deletionFront(): [ 10 | 20 | 30 | 40 | 50 | 60 ] (5 removed)
deletionRear(): [ 10 | 20 | 30 | 40 | 50 ] (60 removed)

8.3 Stack vs Queue vs Deque Visual

Structure Visual Access Pattern

Stack [ 1 | 2 | 3 ] <- TOP (both operations) One end only (LIFO)

Queue FRONT -> [ 1 | 2 | 3 ] <- REAR Front:delete; Rear:insert (FIFO)

Deque <-> [ 1 | 2 | 3 ] <-> Both ends for both operations

9. MEMORY OPTIMIZATION
9.1 FIFO Mnemonic
FIFO = First In, First Out

Bank queue: first person to ARRIVE is first SERVED. Rear=back of line, Front=cashier.

9.2 Quick Distinction Rule

One Rule to Remember

STACK: Same end (LIFO) | QUEUE: Different ends (FIFO) | DEQUE: Both ends (flexible)

9.3 Python Method Quick Map

Operation Stack Queue Deque (Front) Deque (Rear)

INSERT append(e) append(e) insert(0, e) append(e)

DELETE pop() pop(0) pop(0) pop()

PEEK list[-1] list[0] list[0] list[-1]

9.4 Operations Quick Card

Queue + Deque at a Glance

Queue: enqueue->append | dequeue->pop(0) | peek->q[0] | isEmpty->len==0

Deque extras: insertFront->insert(0,e) | deletionRear->pop() | getFront-
>d[0] | getRear->d[-1]
10. BOARD EXAM FOCUS
10.1 Most Frequently Asked Questions
1. Define Queue, FIFO, FRONT, REAR, ENQUEUE, DEQUEUE, Overflow, Underflow, Deque. (1-2
marks each)
2. Differentiate Stack vs Queue, Queue vs Deque. (2-3 marks)
3. Write Python functions: enqueue(), dequeue(), isEmpty(), peek(), size(). (2-3 marks each)
4. Show queue status after each operation — trace question. (5 marks — VERY COMMON)
5. Show deque status after each operation — trace question. (5 marks)
6. Write algorithm/program for palindrome check using deque. (5 marks)
7. Fill in blanks (NCERT Q1). (1 mark each)
8. Compare Stack with Queue. (3-5 marks)

10.2 NCERT Exercise Q1 Answers

• (a) QUEUE — linear list, different ends for insert+delete
• (b) FIFO order
• (c) Insertion = ENQUEUE; Deletion = DEQUEUE
• (d) FRONT end
• (e) A, S, D, F (same order — FIFO)
• (f) DEQUE
• (g) deletionFront, deletionRear, deletionRear, deletionFront, deletionFront

10.3 Stack vs Queue Comparison Table

Feature Stack Queue

Principle LIFO FIFO

Insert at TOP only REAR only

Delete from TOP only FRONT only

Ends used ONE TWO (different)

Insert name PUSH ENQUEUE

Delete name POP DEQUEUE

Python insert append() append()

Python delete pop() pop(0)

Real-life Stack of plates Bank queue

10.4 Queue vs Deque Comparison
Feature Queue Deque

Full name Queue Double Ended Queue

Insert at REAR only FRONT or REAR

Delete from FRONT only FRONT or REAR

Simulates FIFO only FIFO or LIFO

Palindrome check Not directly Yes

11. COMPETITIVE EDGE (KCET LEVEL)
11.1 Advanced Insights
• Time Complexity: ENQUEUE = O(1) (append). DEQUEUE (pop(0)) = O(n) due to shifting. Python's
[Link] gives O(1) for both ends.
• Python's [Link]: production-grade deque; append/appendleft for insert; pop/popleft for
delete.
• Circular Queue: REAR wraps to FRONT, eliminating wasted space in array-based queue. Not in
NCERT.
• Priority Queue: elements served by priority, not insertion order. Used in Dijkstra's algorithm, A*
search.
• isFull NEVER needed in Python — Python lists are dynamic.

11.2 Common MCQ Traps

9. Trap: 'Queue inserts at FRONT' → WRONG. Queue INSERTS at REAR, DELETES from FRONT.
10. Trap: 'dequeue uses pop()' → WRONG. dequeue uses pop(0). pop() = stack POP.
11. Trap: 'Stack and Queue differ only in name' → WRONG. Different insertion/deletion ends.
12. Trap: 'Deque can only simulate queue' → WRONG. Deque simulates BOTH stack and queue.
13. Trap: 'isFull needed in Python' → WRONG. Python lists are dynamic; isFull never triggered.
14. Trap: 'peek() removes FRONT element' → WRONG. peek() only READS, never removes.
15. Trap: 'insertFront uses append()' → WRONG. insertFront uses insert(0, element).

A. KCET-STYLE MCQ QUESTIONS

Q1. Which principle does Queue follow?
Option Answer

(a) LIFO

(b) FIFO CORRECT

(c) FILO

(d) Random

Explanation: FIFO = First-In-First-Out. First inserted element is first removed.

Q2. In a queue, deletion is done from which end?

Option Answer

(a) REAR

(b) FRONT CORRECT

(c) Both
 (d) Middle

Explanation: DEQUEUE removes from FRONT. ENQUEUE inserts at REAR.

Q3. Which Python method implements DEQUEUE?

Option Answer

(a) pop()

(b) pop(0) CORRECT

(c) remove()

(d) delete()

Explanation: pop(0) removes from index 0 (FRONT). pop() removes from end (REAR) = stack POP.

Q4. FRONT of queue is also called:

Option Answer

(a) TAIL

(b) TOP

(c) HEAD CORRECT

(d) REAR

Explanation: FRONT = HEAD. REAR = TAIL.

Q5. Deque stands for:

Option Answer

(a) Deleting Queue

(b) Double Ended Queue CORRECT

(c) Dynamic Queue

(d) Dual Queue

Explanation: Deque = Double Ended Queue — insert/delete at BOTH ends.

Q6. Exception when DEQUEUE on empty queue:

Option Answer

(a) Overflow

(b) Underflow CORRECT

(c) IndexError

(d) TypeError
Explanation: Underflow = removing from empty. Overflow = inserting into full.

Q7. Which method adds element at FRONT in deque?

Option Answer

(a) append(e)

(b) insert(0, e) CORRECT

(c) push(e)

(d) addFront(e)

Explanation: insert(0, e) adds at index 0 (FRONT). append(e) adds at end (REAR).

Q8. peek() in a queue:

Option Answer

(a) Removes FRONT

(b) Returns FRONT without removing CORRECT

(c) Returns REAR

(d) Returns size

Explanation: peek() = read FRONT without removing. Non-destructive read.

Q9. In a deque, if insert and delete from SAME end, it behaves as:
Option Answer

(a) Queue

(b) Stack CORRECT

(c) List

(d) Tree

Explanation: Same end insert+delete = LIFO = Stack.

Q10. Queue [10, 20, 30] (Front=10). After dequeue():

Option Answer

(a) [10, 20]

(b) [20, 30] CORRECT

(c) [10, 30]

(d) no change

Explanation: dequeue removes from FRONT (index 0 = 10). Result: [20, 30].
C. FORMULA/SYNTAX BOOSTER
Queue + Deque Quick Reference

QUEUE:
enqueue(q,e): [Link](e) [add at REAR]
dequeue(q): [Link](0) [remove from FRONT]
peek(q): q[0] [read FRONT, no remove]
isEmpty(q): len(q)==0 [True if empty]
size(q): len(q) [count]

DEQUE EXTRAS:
insertFront(d,e): [Link](0,e) [add at FRONT]
deletionRear(d): [Link]() [remove from REAR]
getFront(d): d[0] [peek FRONT]
getRear(d): d[len(d)-1] [peek REAR]
12. RAPID REVISION SHEET

Quick Revision — Queue & Deque (Chapter 4)

QUEUE BASICS:
• Queue = linear; FIFO = FCFS (first inserted, first removed)
• REAR (TAIL) = insert end; FRONT (HEAD) = delete end
• ENQUEUE = add at REAR; DEQUEUE = remove from FRONT
• OVERFLOW = ENQUEUE on full; UNDERFLOW = DEQUEUE on empty
• isFull NEVER needed in Python (dynamic list); OVERFLOW never occurs

REAL-LIFE APPLICATIONS:
• Bank/train/toll queue, IVRS call hold, OS CPU scheduling, printer spooling, web server
requests

PYTHON QUEUE:
• enqueue: append(e) | dequeue: pop(0) | peek: q[0] | isEmpty: len==0 | size: len(q)

DEQUE:
• Double Ended Queue; insert+delete from BOTH ends; simulates Stack or Queue
• insertFront: insert(0,e) | insertRear: append(e)
• deletionFront: pop(0) | deletionRear: pop()
• getFront: d[0] | getRear: d[len-1]
• Same end insert+delete -> STACK | Opposite ends -> QUEUE

PALINDROME WITH DEQUE:

• Load string into deque via insertRear char by char
• Loop while len>1: deletionFront + deletionRear, compare
• All pairs match -> PALINDROME; any mismatch -> NOT palindrome
• Odd length: 1 element remains (middle char) -> still palindrome

KEY TRAPS:
• dequeue uses pop(0) NOT pop() — common mistake!
• insertFront uses insert(0,e) NOT append(e)
• peek() only READS — never removes element
• ENQUEUE causes overflow; DEQUEUE causes underflow
• Python queue never overflows — isFull not needed