📌 Snapshot
- Understand queues and deques: first in first out, enqueue and dequeue traces, and Python list code.
- FRONT and REAR, overflow and underflow, and a head to head table of queue against stack.
- The deque operations mapped to exact Python calls, including the pop and pop zero trap.
- Palindrome checking with a deque and step by step operation traces that CUET likes to ask.
📖 Detailed Notes
Written and reviewed by Rohit Singh, Computer Science & Commerce faculty at UniDrill (MCA, Osmania University · 6 years teaching). Based on NCERT Computer Science Class XII, Chapter 4.
Why does your print job wait its turn?
You send a 2-page assignment to the shared printer just after a classmate sends a 90-page file. Yours prints second. Nobody planned this. The printer simply serves jobs in the order they arrived. That fairness rule is called first in first out, and the structure that enforces it is the queue. The same rule runs the line at a bank counter, the railway waiting list and the order in which a web server answers requests.
What is a queue?
A queue is an ordered linear list with different ends for adding and removing. New elements join at the REAR (also called the TAIL). Elements leave from the FRONT (also called the HEAD). The rule is FIFO, First In First Out, also called FCFS, First Come First Served: the element that has waited longest leaves first.
A simple way to remember the ends: the REAR is where you join the line, and the FRONT is where you leave it.
| Where | Who waits | Served first |
|---|---|---|
| Bank cash counter | Customers | The one who arrived earliest |
| Petrol pump | Vehicles | The earliest vehicle |
| Railway waiting list | Passengers | W/L1 gets the next confirmed berth |
| Toll booth | Vehicles | The earliest vehicle in the lane |
| Web server | Requests | The earliest request |
| Operating system | Jobs waiting for the processor | The earliest job |
| Shared printer (spooling) | Print requests | The earliest request |
A queue and a stack are mirror images of each other in what they allow:
| Feature | Stack | Queue |
|---|---|---|
| Rule | LIFO | FIFO |
| Insertion at | TOP | REAR |
| Deletion from | TOP | FRONT |
| Number of open ends | One | Two |
| Insert operation | PUSH | ENQUEUE |
| Delete operation | POP | DEQUEUE |
| Python list calls | append() and pop() |
append() and pop(0) |
| Real example | Browser Back button | Bank counter line |
Queue operations
| Operation | Does what | Condition |
|---|---|---|
| ENQUEUE | Inserts a new element at the REAR | Overflow if the queue is full |
| DEQUEUE | Removes the element at the FRONT | Underflow if the queue is empty |
| IS EMPTY | Checks whether the queue has any element | Used before DEQUEUE to avoid underflow |
| IS FULL | Checks whether more elements can be added | Used before ENQUEUE to avoid overflow |
| PEEK | Reads the FRONT element without removing it | Nothing changes |
Worked example: tracing a queue. Start with an empty queue and perform these operations. The queue is written from FRONT on the left to REAR on the right.
| Step | Operation | Value returned | Queue after the step | FRONT | REAR |
|---|---|---|---|---|---|
| 1 | enqueue(z) | none | [z] |
z | z |
| 2 | enqueue(x) | none | [z, x] |
z | x |
| 3 | enqueue(c) | none | [z, x, c] |
z | c |
| 4 | dequeue() | z | [x, c] |
x | c |
| 5 | enqueue(v) | none | [x, c, v] |
x | v |
| 6 | dequeue() | x | [c, v] |
c | v |
| 7 | dequeue() | c | [v] |
v | v |
| 8 | dequeue() | v | [] |
none | none |
| 9 | dequeue() | underflow | [] |
none | none |
Each enqueue moves the REAR on, and each dequeue moves the FRONT on. Elements leave in the order z, x, c, v, exactly the order they came in. The common wrong step is to take the most recent element out first, which is a stack's behaviour.
Pause and predict: after enqueue(z), enqueue(x), enqueue(c), dequeue(), enqueue(v), dequeue(), which element is at the FRONT?
Check your answer: c. After the three enqueues the queue is [z, x, c]. The first dequeue removes z, giving [x, c]. Then v joins the REAR, giving [x, c, v]. The second dequeue removes x, leaving [c, v], and c is the FRONT.
A queue in Python
A Python list works as a queue if you add at the end and remove from the beginning. append() is ENQUEUE, because the end of the list is the REAR. pop(0) is DEQUEUE, because index 0 is the FRONT. IS FULL is not needed, since a Python list grows as needed and never becomes full.
| Code |
|---|
def enqueue(myQueue, element): |
myQueue.append(element) |
def isEmpty(myQueue): |
return len(myQueue) == 0 |
def size(myQueue): |
return len(myQueue) |
def dequeue(myQueue): |
if isEmpty(myQueue): |
print("Underflow") |
else: |
return myQueue.pop(0) |
def peek(myQueue): |
if isEmpty(myQueue): |
print("Queue is empty") |
else: |
return myQueue[0] |
Worked example: a bank counter. Customers arrive and are served in order.
| Code |
|---|
myQueue = list() |
enqueue(myQueue, "Customer1") |
enqueue(myQueue, "Customer2") |
print(dequeue(myQueue)) |
print(size(myQueue)) |
enqueue(myQueue, "Customer3") |
enqueue(myQueue, "Customer4") |
enqueue(myQueue, "Customer5") |
print(dequeue(myQueue)) |
while not isEmpty(myQueue): |
print(dequeue(myQueue)) |
dequeue(myQueue) |
| Output |
|---|
Customer1 |
1 |
Customer2 |
Customer3 |
Customer4 |
Customer5 |
Underflow |
| Statement | Queue afterwards | Printed |
|---|---|---|
| Two enqueues | [Customer1, Customer2] |
nothing |
print(dequeue(...)) |
[Customer2] |
Customer1 |
print(size(...)) |
[Customer2] |
1 |
| Three enqueues | [Customer2, Customer3, Customer4, Customer5] |
nothing |
print(dequeue(...)) |
[Customer3, Customer4, Customer5] |
Customer2 |
while loop |
Dequeues until empty | Customer3, Customer4, Customer5 |
Last dequeue(...) |
empty queue | Underflow |
Why pop(0) and not pop(). pop() with no argument removes the last element, which is the REAR. Using it would serve the newest customer first and make the structure a stack.
Beyond the textbook. For the exam: pop(0) is DEQUEUE. In reality: removing from the front of a Python list forces every remaining element to shift one place to the left, so the work grows with the length of the list, while append() stays quick. Professional code therefore uses collections.deque, which removes from the front just as quickly as from the back. The list version is perfect for learning and for the exam.
Beyond the textbook. For the exam: a queue built on a Python list never overflows. In reality: a queue stored in a fixed size array has a catch. As the FRONT moves right on each dequeue, the slots at the left stay empty and unusable, so the queue can look full while it is not. The fix is a circular queue, in which the REAR wraps around to reuse those slots.
Deque: a queue with two open ends
A deque (say "deck"), short for double ended queue, lets you add and remove at both ends. It has no restriction on the side, so it can behave like a stack or like a queue.
| Operation | Does what | Python call on a list myDeque |
|---|---|---|
| INSERTFRONT | Insert at the front | myDeque.insert(0, element) |
| INSERTREAR | Insert at the rear (same as ENQUEUE) | myDeque.append(element) |
| DELETIONFRONT | Remove from the front (same as DEQUEUE) | myDeque.pop(0) |
| DELETIONREAR | Remove from the rear | myDeque.pop() |
| Peek at front | Read the front | myDeque[0] |
| Peek at rear | Read the rear | myDeque[len(myDeque) - 1] |
The argument order of insert is a favourite trap. It is insert(index, value), so inserting at the front is insert(0, element), not insert(element, 0).
One deque, two behaviours. How you use the ends decides what you get.
| If you insert at | and delete from | You get |
|---|---|---|
| Rear | Front | A queue (FIFO) |
| Rear | Rear | A stack (LIFO) |
| Front | Front | A stack (LIFO) |
| Front | Rear | A queue (FIFO) |
Worked example: tracing a deque.
| Step | Operation | Value returned | Deque after the step (front to rear) |
|---|---|---|---|
| 1 | insertFront(1) | none | [1] |
| 2 | insertRear(2) | none | [1, 2] |
| 3 | insertFront(3) | none | [3, 1, 2] |
| 4 | insertRear(4) | none | [3, 1, 2, 4] |
| 5 | deletionRear() | 4 | [3, 1, 2] |
| 6 | deletionFront() | 3 | [1, 2] |
Where is a deque used? A passenger who has already bought a ticket and returns to ask something may rejoin from the front of the line. A vehicle at a toll plaza may move to the front of an empty adjacent booth's lane. Browser history, undo and redo in editors, and the palindrome test below are all deque jobs.
Palindrome checking with a deque
A palindrome reads the same forwards and backwards, such as madam. The algorithm inserts every character at the rear, then repeatedly removes one character from the front and one from the rear and compares them. If every pair matches until one or zero characters remain, the word is a palindrome.
| Code |
|---|
def isPalindrome(text): |
d = list() |
for ch in text: |
d.append(ch) |
while len(d) > 1: |
if d.pop(0) != d.pop(): |
return False |
return True |
| Round | Deque at the start | Front removed | Rear removed | Match? |
|---|---|---|---|---|
| 1 | [m, a, d, a, m] |
m | m | Yes |
| 2 | [a, d, a] |
a | a | Yes |
| End | [d] |
none | none | One element left, so palindrome |
For hello, round 1 removes h from the front and o from the rear. They differ, so the function returns False after a single comparison. For a word of n characters, at most n divided by 2 (rounded down) comparisons are made. An odd length word ends with one element left over, and an even length word ends with none.
Pause and predict: what does isPalindrome("noon") return, and how many rounds does it need?
Check your answer: True, in 2 rounds. Round 1 compares n with n, leaving [o, o]. Round 2 compares o with o, leaving an empty deque.
Exam traps
| Trap | Why it tempts | Truth |
|---|---|---|
| Insertion is at the FRONT | The front is where the "first" thing is | Insertion is at the REAR; deletion is at the FRONT |
pop() is DEQUEUE |
pop is the delete method |
DEQUEUE is pop(0); plain pop() removes from the rear |
| Overflow is on dequeue | Overflow sounds like "too many removed" | Overflow is enqueue into a full queue; underflow is dequeue from an empty one |
| A Python queue needs an IS FULL check | Fixed size queues do | A list never fills up, so IS FULL is not needed |
| A deque is just another name for a queue | The names look alike | A deque works at both ends and can act as a stack or a queue |
insert(element, 0) inserts at the front |
Reads naturally in English | The index comes first: insert(0, element) |
| Print spooling is LIFO | The latest document feels urgent | Print jobs are served first in first out |
| PEEK removes the front element | Reading and removing seem linked | PEEK only reads, and the queue is unchanged |
60-second revision
| Idea | Remember |
|---|---|
| Queue | Linear list, insert at REAR (tail), delete from FRONT (head), FIFO or FCFS |
| ENQUEUE, DEQUEUE | Insert at the rear, remove from the front |
| Overflow, underflow | Enqueue into full, dequeue from empty |
| Other operations | IS EMPTY, IS FULL, PEEK |
| Python queue | append(x) to enqueue, pop(0) to dequeue, IS FULL not needed |
| Examples | Bank line, petrol pump, toll booth, waiting list, print spooler, web server, CPU job queue |
| Deque | Double ended queue, insert and delete at both ends |
| Deque calls | insert(0, x), append(x), pop(0), pop() |
| One deque | Same end gives a stack, opposite ends give a queue |
| Palindrome | Insert at the rear, then compare front and rear removals |
Where this chapter connects
Queue is the partner of Stack: one is first in first out and the other last in first out, and exam questions love to swap them. Finding items in an ordered list is the subject of Searching, and arranging them is Sorting.
🎯 Practice MCQs
First 3 questions free · create a free account to unlock the rest — answers & explanations included, no payment needed
Q1. Which principle does a queue follow?
▸ Show answer & explanation
Answer: B
A queue serves the element that has waited longest, which is FIFO. Option A describes a stack, and option D also describes a stack. A queue does not provide random access.
Q2. In a queue, a new element is always inserted at the ________ and removed from the ________.
▸ Show answer & explanation
Answer: C
ENQUEUE adds at the REAR and DEQUEUE removes from the FRONT. Option A reverses the two ends, which is the commonest slip.
Q3. On an empty queue these operations are performed in order: enqueue(z), enqueue(x), enqueue(c), dequeue(), enqueue(v), dequeue(). Which element is now at the FRONT?
▸ Show answer & explanation
Answer: A
After three enqueues the queue is z, x, c. The first dequeue removes z, v joins at the rear to give x, c, v, and the second dequeue removes x. The queue is c, v with c at the FRONT.
🔒 12 more practice MCQs
Create a free account to unlock every MCQ in this chapter — answers and explanations included. No payment needed.
Already registered? Just log in and they'll all appear here.
Q4. A queue is stored in a Python list with index 0 as the FRONT. Which statement performs DEQUEUE?
▸ Show answer & explanation
Answer: D
pop(0) removes and returns the element at index 0, the FRONT. Plain pop() removes the last element, the REAR. Lists have no delete() method, and remove(0) searches for the value 0 rather than the index.
Q5. Which statement about IS FULL in a Python list implementation of a queue is correct?
▸ Show answer & explanation
Answer: A
A list grows as elements are appended, so overflow does not occur and IS FULL is unnecessary. Options B, C and D all describe a check that Python does not need or that does not exist.
Q6. Assertion (A): In a queue, insertion takes place at the FRONT. Reason (R): A queue follows the FIFO principle.
▸ Show answer & explanation
Answer: D
Insertion happens at the REAR, so the assertion is false. The reason is a true statement about queues, but it does not support the assertion.
Q7. Match the deque operations in List I with their meanings in List II. List I: (i) INSERTFRONT (ii) DELETIONREAR (iii) INSERTREAR (iv) DELETIONFRONT. List II: (p) Same as ENQUEUE of a queue (q) Insert at the front (r) Same as DEQUEUE of a queue (s) Remove from the rear
▸ Show answer & explanation
Answer: B
INSERTFRONT inserts at the front, DELETIONREAR removes from the rear, INSERTREAR is the same as ENQUEUE, and DELETIONFRONT is the same as DEQUEUE. Options A, C and D each swap pairs.
Q8. For a deque stored in a Python list myDeque, which statement is insertFront for the element e?
▸ Show answer & explanation
Answer: C
The method is insert(index, value), so the front is index 0 and the call is insert(0, e). Option B reverses the arguments, option A inserts at the rear, and option D deletes instead of inserting.
Q9. Consider: (1) q = [] (2) q.append(1) (3) q.append(2) (4) q.append(3) (5) print(q.pop(0), q.pop(0)). What is printed?
▸ Show answer & explanation
Answer: C
pop(0) removes from the front each time, so the elements come out in the order they were added: 1 and then 2. Option A would be the result of pop() without an argument.
Q10. Which of the following is NOT an operation normally allowed on a queue?
▸ Show answer & explanation
Answer: D
A queue gives access only at its FRONT and REAR. Enqueue, dequeue and peek are the standard operations, while middle elements are not reachable.
Q11. A deque can be made to behave as:
▸ Show answer & explanation
Answer: B
Inserting and deleting at the same end gives LIFO, a stack. Inserting at one end and deleting at the other gives FIFO, a queue.
Q12. Which is the best real life example of a queue?
▸ Show answer & explanation
Answer: A
The first person to arrive is served first, which is FIFO. A pile of plates, a pile of books and bangles on a wrist all allow access only to the most recent item, which is LIFO.
Q13. Starting with an empty deque, the operations insertFront(1), insertRear(2), insertFront(3), insertRear(4) are performed in order. What does the deque hold from front to rear?
▸ Show answer & explanation
Answer: C
The deque grows as 1, then 1 2, then 3 1 2, then 3 1 2 4. Each insertFront places the new element before everything else, and each insertRear places it after.
Q14. Assertion (A): In a Python list queue, pop(0) is used for DEQUEUE. Reason (R): The element at index 0 is the FRONT of the queue.
▸ Show answer & explanation
Answer: A
Elements are removed from the FRONT, and the FRONT sits at index 0, so pop(0) is the right call. The reason explains the assertion.
Q15. To test whether madam is a palindrome with a deque, all characters are first inserted at the rear. What is the next step?
▸ Show answer & explanation
Answer: B
The word is a palindrome if every front and rear pair matches until one or no characters remain. The other options do not compare characters.
📊 Previous-Year Questions
Practise with real CUET Computer Science previous-year papers — every question solved, with the correct answer and a step-by-step explanation.
View solved CUET PYQ papers →Ready to drill Computer Science?
Unlock all MCQs, chapter tests, mocks & PYQs for ₹199/year.
Get UniDrill Pro