Queue

A student at the front of a service line is usually served before someone who joins later. This everyday arrangement gives us the defining idea of a queue: elements enter at one end and leave at the other. In Python, queues help us organise requests, print jobs, simulations and sequences of tasks. This chapter also explores deques, which permit insertion and removal at both ends.

Curriculum scope. This is NCERT Class XII Computer Science, Chapter 4, from the uploaded 2026–27 reprint (printed pages 53–66). Your uploaded CBSE 2026–27 master curriculum specifies C12-DS-01 and C12-DS-02 for stacks but does not assign a permanent Queue or Deque lesson ID. Consequently, the C12-CH04-S01–S08 identifiers below are chapter reading anchors only, not fabricated curriculum lessons. This chapter is a supplementary NCERT textbook resource; the book's exercises are still solved in full. The official syllabus and the textbook are not assumed to have identical examinable boundaries.

Source coverage: NCERT §§4.1–4.5; Figure 4.3 operation trace (whose printed caption mistakenly says “Stack Operations”); Program 4-1 (bank cash counter); Program 4-2 (deque); Algorithm 4.1 (palindrome); Activity 4.1–4.4; and end exercises 1–8, including all 1(a)–1(g). Exercises are identified by original number, while the educational explanations and additional practice are original.

Learning objectives#

By the end of this chapter, you should be able to define FIFO, distinguish FRONT and REAR, trace enqueue()/dequeue() and underflow, implement a queue with a Python list, explain the cost of deleting index zero, implement the two-ended deque, test palindromes, work through both NCERT programs, solve all eight textbook exercises, and choose a suitable queue implementation for different tasks.

Chapter reading map#

Section C12-CH04-S01 — Introduction to Queue and FIFO#

1. What is a queue?#

A queue is a linear data structure whose ordinary insertion occurs at the rear and ordinary removal occurs at the front. If items arrive in order A, B, C, the next three removals return A, B, C in that order. This is First In, First Out (FIFO), also called First Come, First Served (FCFS).

The words front/head and rear/tail describe logical positions, not necessarily the left and right edges of a physical picture. Our chapter uses the conventional diagram:

DEQUEUE <— FRONT [A | B | C] REAR <— ENQUEUE
                     arrival order A, B, C

Enqueue D gives [A, B, C, D]. Dequeue returns A and leaves [B, C, D]. Unlike a stack, a queue does not remove the newest arrival first.

Key vocabulary#

Concept check: In [21, 34, 55], 21 is at FRONT and 55 is at REAR. A dequeue followed by enqueue(89) produces [34, 55, 89].

2. Queue versus stack#

Recall the previous chapter: a stack uses one top end for both push and pop (LIFO); a queue uses two ends for enqueue and dequeue (FIFO).

Exam trap: A list is not automatically a queue. A list becomes a queue when the program follows the FIFO operation rules consistently.

3. Applications and fairness#

NCERT uses bank cash counters, petrol-pump lanes, train ticket waiting lists, telephone support queues, print queues and web-server requests to motivate FIFO. In a school result portal, requests arriving faster than the server can process them can wait in a queue. In a print spooler, jobs can be serviced in arrival order.

Real services may use priorities, multiple servers or service policies in addition to FIFO. A priority arrangement is not identical to a single strict FIFO queue. The NCERT margin question about an urgent school administrator request suggests a priority queue or separate urgent lane; within each priority level, FIFO can still be maintained. This provides a practical trade-off: urgent work gets attention, but low-priority requests must not be starved indefinitely.

Try it: If P1, P2, P3 enter a FIFO service queue and two are served, which code remains? P3. If P4 then arrives, the queue becomes [P3, P4].

Section C12-CH04-S02 — Queue Operations, Overflow and Underflow#

1. ENQUEUE and DEQUEUE#

A bounded queue of capacity three initially contains nothing. We can trace operations precisely:

What happens at an empty queue?#

dequeue() is not valid when no element exists. It must not silently assume an item is there. You may report the condition with a message, return a deliberately documented sentinel, or raise an exception. A normal Python list.pop(0) raises IndexError on an empty list. The textbook calls the data-structure condition underflow; Python does not automatically raise a built-in exception class called UnderflowError.

What happens at a full queue?#

Fixed-capacity designs prevent insertion beyond capacity. A Python list, however, has no chosen fixed maximum size by default, so append() does not automatically report textbook “overflow” at some prescribed length. Memory is finite; it is inaccurate to promise an unlimited queue. If you want a bounded queue, enforce a capacity explicitly.

class BoundedQueue:
    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("Capacity must be positive")
        self.capacity = capacity
        self.items = []

    def enqueue(self, value):
        if len(self.items) >= self.capacity:
            raise OverflowError("Queue is full")
        self.items.append(value)

    def dequeue(self):
        if not self.items:
            raise IndexError("Queue underflow")
        return self.items.pop(0)


q = BoundedQueue(2)
q.enqueue("P1")
q.enqueue("P2")
print(q.dequeue())   # P1
print(q.items)       # ['P2']

2. NCERT Figure 4.3 — Step-by-step trace#

The textbook's diagram enqueues Z, X, C; dequeues; enqueues V; then dequeues repeatedly. Its printed caption refers to “Stack Operations,” but the shown operations are queue operations, so interpret it as a queue trace.

The oldest surviving element remains at FRONT after each operation.

A trace-writing method for exams#

First draw the current queue with FRONT on the left. For every enqueue(x), append x on the right; for every successful dequeue(), cross out the leftmost value and record it as the return. For peek(), record the leftmost value without changing the queue. If the queue is empty, write UNDERFLOW and preserve the empty state. This method will be used again in Exercise 6.

Section C12-CH04-S03 — Implementing a Queue with a Python List#

1. The simple NCERT implementation#

NCERT §4.3 uses a regular Python list. append(element) inserts at the right (REAR), and pop(0) removes at the left (FRONT). Here is a complete working version with explicit empty-queue behavior:

def is_empty(queue):
    return len(queue) == 0


def enqueue(queue, element):
    queue.append(element)


def dequeue(queue):
    if is_empty(queue):
        raise IndexError("Queue underflow")
    return queue.pop(0)


def peek(queue):
    if is_empty(queue):
        raise IndexError("Queue underflow")
    return queue[0]


def size(queue):
    return len(queue)


my_queue = []
enqueue(my_queue, "P1")
enqueue(my_queue, "P2")
print(peek(my_queue))     # P1
print(dequeue(my_queue))  # P1
print(size(my_queue))     # 1
print(my_queue)           # ['P2']

You can adapt this implementation to return None for empty queues, as in the textbook, but remember: None could itself be a legitimate queue item. Throwing a clear exception is often less ambiguous; another alternative is a (success, value) pair.

2. Mutability and references#

When a list is passed to a function, append() and pop(0) modify that same list object. A function need not return a replacement queue.

def add_ticket(queue, ticket):
    queue.append(ticket)


tickets = ["T1"]
add_ticket(tickets, "T2")
print(tickets)  # ['T1', 'T2']

3. FRONT and REAR must remain consistent#

With this implementation:

Index      0        1        2
Items     [A,       B,       C]
          FRONT             REAR
pop(0) removes A; append(D) adds D at REAR.

Common misconception: A call to queue.pop() (with no index) removes the rightmost element and would make this representation behave like a stack, not a FIFO queue.

4. Complexity and implementation choices#

append() is normally amortised O(1). But removing the first item of a Python list with pop(0) is O(n), because subsequent items must be shifted left. For short classroom demonstrations the list model is clear; for long, frequently serviced queues Python's collections.deque is preferable. We will revisit this in S08.

5. Returning the whole queue#

Activity 4.2 asks how to list the full queue. Do not repeatedly dequeue items merely to display them unless consuming the queue is intended. A non-destructive traversal is enough:

def show_queue(queue):
    if not queue:
        print("Queue is empty")
    else:
        print("FRONT ->", " | ".join(map(str, queue)), "<- REAR")


sample = ["P2", "P3", "P4"]
show_queue(sample)
print(sample)  # Still unchanged

Section C12-CH04-S04 — NCERT Bank Cash-Counter Program#

1. Modelling arrival and service#

NCERT Program 4-1 describes a bank cash counter. Two people arrive; the cashier serves one; three more arrive; the remaining people are served in FIFO order. We can reproduce this deterministically before adding interactive input. Represent the queue of customers using P1–P5.

Complete classroom version of Program 4-1#

def enqueue(queue, code):
    queue.append(code)


def dequeue(queue):
    if not queue:
        raise IndexError("No customers are waiting")
    return queue.pop(0)


def is_empty(queue):
    return not queue


def size(queue):
    return len(queue)


bank_queue = []
for code in ("P1", "P2"):
    enqueue(bank_queue, code)

print("Served:", dequeue(bank_queue))
print("Waiting:", size(bank_queue))

for code in ("P3", "P4", "P5"):
    enqueue(bank_queue, code)

while not is_empty(bank_queue):
    print("Served:", dequeue(bank_queue))

if is_empty(bank_queue):
    print("No more customers")

Verified output:

Served: P1
Waiting: 1
Served: P2
Served: P3
Served: P4
Served: P5
No more customers

Textbook nuance: The printed Program 4-1 output ends with a “queue empty” line even though the program’s while not isEmpty loop does not call dequeue() on an empty queue. Thus the loop as printed cannot produce an underflow message on its own. We retain the intended FIFO result and show “No more customers” through an explicit final check instead of falsely attributing an extra call to the program. The printed sample also uses lower-case p1 for data input as P1; strings keep their case in Python.

2. Interactive menu for classroom practice#

Students often need to experiment with the operations, so here is a separate menu program. It handles invalid choices and queue emptiness without printing an unexplained None.

def run_cash_counter():
    customers = []
    while True:
        print("1 Add customer | 2 Serve next | 3 Peek | 4 List | 5 Exit")
        choice = input("Choice: ").strip()
        if choice == "1":
            code = input("Customer code: ").strip()
            if not code:
                print("Enter a non-empty code")
            else:
                customers.append(code)
        elif choice == "2":
            if customers:
                print("Served:", customers.pop(0))
            else:
                print("No customer to serve (underflow)")
        elif choice == "3":
            print("Next:", customers[0] if customers else "Nobody waiting")
        elif choice == "4":
            print("FRONT ->", customers, "<- REAR")
        elif choice == "5":
            break
        else:
            print("Choose 1–5")


if __name__ == "__main__":
    # Uncomment for an interactive session:
    # run_cash_counter()
    pass

Practical insight: An empty queue is a normal state. What is invalid is requesting an element from the empty queue without a defined response.

Section C12-CH04-S05 — Introduction to Deque#

1. What changes in a deque?#

A deque (pronounced “deck”) is a double-ended queue. Unlike an ordinary queue, it permits insertion and removal at both FRONT and REAR. Therefore, you can use it to simulate both FIFO and LIFO behavior by choosing operations deliberately.

Queue behavior using a deque#

If you always insert at REAR and delete at FRONT, you obtain FIFO. If you always insert and delete at the same end (for example, REAR), you obtain LIFO. Those are the exact ideas behind NCERT Activities 4.3 and 4.4.

Care with wording: A deque supports flexible ends. Merely possessing a deque does not guarantee FIFO or LIFO; the operation sequence determines the actual behavior.

2. Deque applications#

The book discusses special service arrangements, redistributing cars among queues, recent-history navigation and undo/redo, and palindrome checking. For applications with special front-priority service, adding a new arrival at FRONT changes normal arrival-order fairness. It should be an explicit policy rather than called strict FIFO.

3. A visual sequence#

Starting with [A, B]:

The two get operations do not consume items. The two deletion operations do.

Section C12-CH04-S06 — Implementing a Deque in Python#

1. A corrected implementation of NCERT §4.5#

A Python list supports both ends, but insert(0, ...) and pop(0) shift data and cost O(n). The following implementation uses explicit names matching the textbook and an unambiguous exception on underflow:

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


def insertFront(dq, item):
    dq.insert(0, item)


def insertRear(dq, item):
    dq.append(item)


def deletionFront(dq):
    if isEmpty(dq):
        raise IndexError("Deque underflow at front")
    return dq.pop(0)


def deletionRear(dq):
    if isEmpty(dq):
        raise IndexError("Deque underflow at rear")
    return dq.pop()


def getFront(dq):
    if isEmpty(dq):
        raise IndexError("Deque is empty")
    return dq[0]


def getRear(dq):
    if isEmpty(dq):
        raise IndexError("Deque is empty")
    return dq[-1]


d = []
insertFront(d, "A")
insertRear(d, "B")
print(d)                 # ['A', 'B']
print(getFront(d))       # A
print(getRear(d))        # B
print(deletionRear(d))   # B
print(deletionFront(d))  # A

What is wrong with some printed fragments?#

The NCERT chapter's explanatory fragments occasionally call isEmpty() without supplying the deque, and one fragment spells isempty differently. Those calls do not match the earlier function signature and need correction. Program 4-2 also contains lines that are ambiguous or truncated in the printed main routine relative to its displayed two-mode output. This chapter provides a separately verified, fully runnable demonstration rather than claiming those fragments execute verbatim.

2. Worked version of Program 4-2: two operating modes#

This version shows both normal queue mode (insertRear, deletionFront) and stack-like mode (insertFront, deletionFront). Each uses the deque but follows a different discipline.

def demo_two_deque_modes():
    normal = []
    normal.append("23")
    normal.append("45")
    print("Queue mode:", normal)
    print("Served:", normal.pop(0))
    print("Served:", normal.pop(0))

    stack_like = []
    stack_like.insert(0, "34")
    stack_like.insert(0, "56")
    print("Same-end mode:", stack_like)
    print("Removed:", stack_like.pop(0))
    print("Removed:", stack_like.pop(0))


demo_two_deque_modes()

Expected output:

Queue mode: ['23', '45']
Served: 23
Served: 45
Same-end mode: ['56', '34']
Removed: 56
Removed: 34

The optional user-input menu below keeps the choices closer to the textbook's program intent while avoiding repeated, unexplained None values:

def deque_menu():
    dq = []
    while True:
        print("1 Insert front | 2 Insert rear | 3 Delete front")
        print("4 Delete rear | 5 Peek ends | 6 Display | 7 Exit")
        choice = input("Choice: ").strip()
        if choice == "1":
            dq.insert(0, input("Value: "))
        elif choice == "2":
            dq.append(input("Value: "))
        elif choice == "3":
            print("Removed:", dq.pop(0) if dq else "UNDERFLOW")
        elif choice == "4":
            print("Removed:", dq.pop() if dq else "UNDERFLOW")
        elif choice == "5":
            print((dq[0], dq[-1]) if dq else "Deque empty")
        elif choice == "6":
            print("FRONT ->", dq, "<- REAR")
        elif choice == "7":
            break
        else:
            print("Choose 1–7")


if __name__ == "__main__":
    # Uncomment for an interactive practice session:
    # deque_menu()
    pass

3. Avoiding an underflow display of None#

If a textbook-style function returns None when empty, code such as print(deletionFront(dq)) prints None after the function's warning. That double message can confuse beginners. Either check for emptiness first, return a structured result, or raise and catch a clear exception. Never treat an empty successful return as a removed queue item.

Section C12-CH04-S07 — Palindromes Using Deque#

1. NCERT Algorithm 4.1 in plain language#

A palindrome reads the same forwards and backwards, for example madam. NCERT Algorithm 4.1 inserts characters at REAR, then repeatedly compares one character deleted from FRONT with one deleted from REAR. If every pair matches, the word is a palindrome. An odd-length palindrome leaves one unmatched central character, which is allowed.

Trace with madam:

2. Complete Python solution (also NCERT Exercise 8)#

def is_palindrome_deque(text):
    # Exact, case-sensitive, character-by-character comparison.
    dq = list(text)
    while len(dq) > 1:
        left = dq.pop(0)
        right = dq.pop()
        if left != right:
            return False
    return True


for word in ("madam", "level", "python", "abba", "a", ""):
    print(repr(word), is_palindrome_deque(word))

Output:

'madam' True
'level' True
'python' False
'abba' True
'a' True
'' True

This version implements literal strings and treats an empty string as a palindrome (vacuously symmetric). It is case-sensitive, and spaces/punctuation count unless removed explicitly. If an exercise asks for phrase palindromes, state a normalisation rule instead of silently changing the input.

Optional phrase normalisation#

from collections import deque


def is_phrase_palindrome(text):
    cleaned = deque(c.lower() for c in text if c.isalnum())
    while len(cleaned) > 1:
        if cleaned.popleft() != cleaned.pop():
            return False
    return True


print(is_phrase_palindrome("Never odd or even"))  # True

Complexity: With a Python list, repeated pop(0) shifts elements, so checking a length-n string can be O(n²). With collections.deque, end removals are O(1), so a comparable test is O(n).

Section C12-CH04-S08 — Choosing an Efficient Queue Implementation (Optional Enrichment)#

1. Python's standard-library deque#

collections.deque supports efficient appends and pops at both ends, making it a natural implementation for long-running queues. The word deque also appears in the NCERT chapter as a data-structure concept; Python's collections.deque is the built-in concrete container implementing it.

from collections import deque

requests = deque()
requests.append("R1")       # enqueue at rear
requests.append("R2")
requests.append("R3")
print(requests[0])            # R1, peek front
print(requests.popleft())     # R1, dequeue
print(list(requests))        # ['R2', 'R3']

Deque-based palindrome#

from collections import deque


def palindrome_fast(word):
    letters = deque(word)
    while len(letters) > 1:
        if letters.popleft() != letters.pop():
            return False
    return True


assert palindrome_fast("level")
assert not palindrome_fast("paper")

2. Complexity comparison#

For classroom tracing, either model is acceptable if operations are correct. For real processing systems with many front removals, a deque is usually more efficient. No solution is claimed “infinite-capacity”: data structures are limited by available memory and any explicit configured maximum.

3. Simple real-world request processor#

from collections import deque


def process_first_three(jobs):
    pending = deque(jobs)
    processed = []
    for _ in range(min(3, len(pending))):
        processed.append(pending.popleft())
    return processed, list(pending)


print(process_first_three(["J1", "J2", "J3", "J4"]))
# (['J1', 'J2', 'J3'], ['J4'])

An ordinary FIFO queue preserves the order of arrival, but it does not automatically solve job prioritisation, cancellation or resource scarcity. Those require additional explicit rules.

NCERT Chapter 4 — Complete Exercise Solutions (1–8)#

All answers below retain the original NCERT numbering and paraphrase the question prompts. The textbook source is the uploaded Class XII 2026–27 reprint, Chapter 4, printed pages 65–66. Whenever a program uses a convention not stated in the question, it is explained.

NCERT Exercise 1 — Fill in the blanks (a–g)#

Q1(a) — Linear collection inserting and deleting at different ends. Queue. A queue inserts at REAR and removes at FRONT, in contrast to a stack's shared TOP end.

Q1(b) — Processing order of a queue. FIFO (First In, First Out). The earliest outstanding element leaves first.

Q1(c) — Names of insertion and deletion operations. ENQUEUE and DEQUEUE, respectively.

Q1(d) — End from which queue deletion occurs. FRONT (HEAD). Removing at REAR instead would violate our defined FIFO queue behavior.

Q1(e) — Deletion order for A, S, D and F. A, S, D, F, assuming they are listed from FRONT to REAR (or were enqueued in that order). Without a different front orientation specified, we use the textbook queue convention.

Q1(f) — Structure allowing insertion/removal at either end, but not its middle. Deque (double-ended queue) in its basic abstract interface. Some concrete containers allow additional indexing, but the named deque operations act at ends.

Q1(g) — Deque initially z, x, c, v, b; deletion output z, b, v, x, c. A valid sequence is deletionFront, deletionRear, deletionRear, deletionFront, deletionFront. Step trace:

The final operation could equally be deletionRear, because only one item remains. Therefore the question permits at least two equally valid operation sequences unless it specifies a tie-break rule.

NCERT Exercise 2 — Compare stack and queue#

Both are ordered linear data structures. A stack uses a single TOP end for push() and pop(), giving LIFO order, whereas a queue uses separate REAR for enqueue and FRONT for dequeue, giving FIFO. If A, B, C arrive in this order, a stack pops C, B, A; a queue dequeues A, B, C. A Python list can implement either, depending on which end is removed.

NCERT Exercise 3 — Explain FIFO in a queue#

FIFO means the first item inserted is the first to be removed, unless it has already left. The next departure always happens at FRONT, and new arrivals enter at REAR. For example, arrivals 101, 102, 103 lead to service order 101, 102, 103 if no special priority policy intervenes. FIFO is about relative order, not elapsed time guarantees.

NCERT Exercise 4 — Menu-driven queue representing shuttlecocks in a box#

Interpretation: Each shuttlecock is assigned an identifier. New shuttlecocks are placed at the logical REAR of the storage queue and the oldest accessible shuttlecock is issued from FRONT. A queue model assumes two-ended logical access; a physical tube with just one open end could instead behave as a stack. We state the FIFO model explicitly.

def shuttlecock_queue():
    box = []
    while True:
        print("1 Add | 2 Issue oldest | 3 Peek | 4 Count | 5 Show | 6 Exit")
        choice = input("Select: ").strip()
        if choice == "1":
            code = input("Shuttlecock ID: ").strip()
            if code:
                box.append(code)
            else:
                print("An ID is required")
        elif choice == "2":
            print("Issued:", box.pop(0) if box else "UNDERFLOW — box empty")
        elif choice == "3":
            print("Next:", box[0] if box else "Box empty")
        elif choice == "4":
            print("Count:", len(box))
        elif choice == "5":
            print("FRONT ->", box, "<- REAR")
        elif choice == "6":
            print("Goodbye")
            break
        else:
            print("Please choose 1–6")


if __name__ == "__main__":
    # Call shuttlecock_queue() to run the interactive exercise.
    pass

Example test: Add S1, add S2, issue ⇒ S1; peek ⇒ S2; count ⇒ 1. Issuing again yields S2; an additional issue reports underflow and leaves the queue empty. No invalid deletion occurs.

NCERT Exercise 5 — Difference between queue and deque#

A queue permits insertion at REAR and deletion at FRONT only; the usual order is FIFO. A deque permits insertion and deletion at either FRONT or REAR, so it can act as a queue or stack depending on the chosen methods. In Python, using collections.deque, a normal queue calls append() and popleft(), while a more general deque may use appendleft(), append(), popleft() and pop().

NCERT Exercise 6 — Queue trace, operation by operation#

Start with an empty queue. peek() returns FRONT without changing it; dequeue() on empty reports underflow. Each enqueue joins at REAR.

Answer: Final queue is [1]. The two invalid dequeues do not create phantom items and do not alter the empty queue.

NCERT Exercise 7 — Deque trace, operation by operation#

Start with an empty deque. The initial peek() is invalid; it must not modify the deque. We use peek() as getFront() for this question; no element exists, so either end would be empty.

Answer: The final deque is empty. Two operations encounter an empty deque: the first peek() and the last deletionRear().

NCERT Exercise 8 — Palindrome detection with a deque#

Algorithm 4.1 fills a deque with the word's characters and compares removals from opposite ends. Here is a complete runnable version using Python's purpose-built deque (the underlying algorithm is the same as the book's list-deque demonstration):

from collections import deque


def palindrome_with_deque(word):
    letters = deque(word)
    while len(letters) > 1:
        first = letters.popleft()
        last = letters.pop()
        if first != last:
            return False
    return True


word = "madam"
print("Palindrome" if palindrome_with_deque(word) else "Not palindrome")
print(palindrome_with_deque("level"))
print(palindrome_with_deque("queue"))

Output:

Palindrome
True
False

Explanation: For madam, m matches m, a matches a, and only the middle d remains, so the answer is True. For queue, the first letter q and last letter e differ, so the answer is False. The comparison is exact and case-sensitive. If you want to ignore spaces or case, normalise first and say so explicitly.

NCERT Activities 4.1–4.4 — Answers and Practical Guidance#

Activity 4.1 — Avoid printing None when the queue is empty#

The book's queue deletion and peek functions may print an empty warning and implicitly return None. Printing that return again adds an unwanted None line. Solution: Check isEmpty() before calling the operation, or design the function to raise IndexError and catch it.

queue = []
if queue:
    print("Served", queue.pop(0))
else:
    print("Queue is empty — nobody served")

Result: Exactly one helpful message, no misleading None value.

Activity 4.2 — List all current queue elements without removing them#

def display_queue(queue):
    if not queue:
        print("Empty queue")
    else:
        for position, item in enumerate(queue, start=1):
            print(position, item)


display_queue(["P2", "P3", "P4"])

Explanation: Traversal leaves [P2, P3, P4] unchanged. Consuming every item with dequeue would be inappropriate for a display-only feature.

Activity 4.3 — Insertion and deletion from the same end#

Correct option: 2) Stack. Same-end insertion and deletion make the most recently inserted item come out first (LIFO). For example, insertRear(A), insertRear(B), then deletionRear() returns B.

Activity 4.4 — Insertion and deletion from opposite ends#

Correct option: 1) Queue. Inserting at REAR and deleting at FRONT yields FIFO. Symmetrically, inserting at FRONT and deleting at REAR also yields FIFO if those rules are used consistently.

NCERT Textbook Programs and Algorithm — Fully Explained#

Program 4-1 — Bank cashier queue#

Book goal: Two people join, one is served, three others join, then the remaining people leave in arrival order. The complete runnable version appears in C12-CH04-S04, with step table and expected output. Its final line clarifies the printed source's underflow inconsistency.

Important statements: append() joins at REAR; pop(0) serves FRONT; while not is_empty(...) runs only while an item exists. When the condition becomes false, the loop ends without making a further dequeue call.

Suggested verification: Change arrival order to P4, P1, P3; the service order becomes P4, P1, P3, not sorted order.

Program 4-2 — Deque operations using Python#

Book goal: Demonstrate insertion, inspection and removal from either deque end, and use selected operations to model a normal queue or stack-like behavior. The corrected definitions and two-mode demonstration appear in C12-CH04-S06.

Original snippet cautions: Several calls to isEmpty need the deque argument, and one uses a different spelling. The printed main routine does not consistently match both sample output branches. Fix both before copying it into a runnable program; do not treat the printed sample transcript as executable code.

Algorithm 4.1 — Palindrome with two-ended removals#

Book goal: Place a word's characters into a deque, repeatedly delete one from FRONT and one from REAR, compare them, and stop if they disagree. For odd-length words, a single central character may remain. The madam trace and two complete implementations appear in S07 and Exercise 8.

Proof idea: At each successful comparison, the first and last remaining characters are equal. Removing them preserves the palindrome condition for the smaller middle substring. If a mismatch occurs, the entire word cannot be a palindrome. If no mismatch occurs before zero or one character remains, every symmetric pair matched.

Original Practice Questions — 30 Questions with Explained Answers#

These questions are newly written for this study book. They are not represented as official NCERT exercise questions or previous-year board questions. The formats include conceptual MCQs, output tracing, short answers and programming.

Foundation MCQs (Practice 1–10)#

Practice 1 — A queue normally removes from which end?#

Options: (A) REAR (B) FRONT (C) Both simultaneously (D) Middle.

Answer: B. FIFO dequeues at FRONT. The rear is used for ordinary insertion.

Practice 2 — Which list operation models dequeue with FRONT at index zero?#

Options: (A) pop() (B) append() (C) pop(0) (D) sort().

Answer: C. pop(0) removes and returns the first element. pop() without an index removes the last item instead.

Practice 3 — Enqueue 10, 20, 30, then dequeue once. What remains?#

Options: (A) [10,20] (B) [20,30] (C) [30,10] (D) [].

Answer: B. The oldest element, 10, leaves first, preserving the order of 20 and 30.

Practice 4 — What is the abstract condition called when deleting from an empty queue?#

Options: (A) Overflow (B) Underflow (C) Collision (D) Sorting.

Answer: B. Underflow is the data-structure condition. In a direct list implementation, an invalid pop(0) raises IndexError.

Practice 5 — A normal queue differs from a deque because a normal queue ...#

Options: (A) accepts strings only (B) has no FRONT (C) restricts insertion and deletion ends (D) always stores two elements.

Answer: C. Normal queues use REAR insertion and FRONT deletion; deques allow both at both ends.

Practice 6 — Which combination on collections.deque represents FIFO?#

Options: (A) append() and pop() (B) append() and popleft() (C) appendleft() and popleft() (D) pop() twice.

Answer: B. A new item enters right/REAR while oldest leaves left/FRONT.

Practice 7 — Which is true about peek() on a non-empty queue?#

Options: (A) It removes FRONT (B) It clears REAR (C) It reads FRONT without removal (D) It appends an item.

Answer: C. The queue state must remain unchanged after peek.

Practice 8 — Which operation can be O(n) on a Python list-based queue?#

Options: (A) len(q) (B) q[0] (C) q.append(x) (D) q.pop(0).

Answer: D. Removing index zero shifts the remaining elements left.

Practice 9 — Same-end insertion and deletion on a deque can simulate ...#

Options: (A) Stack (B) Strict FIFO only (C) Binary search (D) A linked list without operations.

Answer: A. With insertRear and deletionRear, the last item added is the first removed.

Practice 10 — A bounded queue of capacity 2 currently has [A,B]. What should enqueue(C) do?#

Options: (A) Replace A silently (B) Reject/report overflow (C) Delete B automatically (D) Duplicate C.

Answer: B. When a fixed capacity has been explicitly set, inserting beyond it is an overflow condition.

Output-tracing questions (Practice 11–18)#

Practice 11 — List queue trace#

q = []
q.append(4)
q.append(8)
print(q.pop(0), q)

Answer: 4 [8]. Four was enqueued first and therefore leaves first; the list retains eight.

Practice 12 — Peek versus dequeue#

q = ["A", "B", "C"]
print(q[0])
print(q[0])
print(q)

Answer:

A
A
['A', 'B', 'C']

Reading q[0] does not delete anything, so both peeks return A.

Practice 13 — Pop with no index#

q = [3, 5, 7]
print(q.pop())
print(q)

Answer: 7 followed by [3, 5]. This removes REAR and therefore is not our ordinary FIFO dequeue operation.

Practice 14 — appendleft and popleft#

from collections import deque
q = deque([2, 4])
q.appendleft(1)
print(q.popleft(), list(q))

Answer: 1 [2, 4]. appendleft inserts at FRONT; popleft removes that newly inserted item.

Practice 15 — Deque both ends#

from collections import deque
d = deque(["X", "Y"])
d.appendleft("W")
d.append("Z")
print(d.pop(), d.popleft(), list(d))

Answer: Z W ['X', 'Y']. Rear Z leaves first, then FRONT W leaves, leaving X and Y in original order.

Practice 16 — Two dequeues and a new arrival#

q = [11, 22, 33]
a = q.pop(0)
q.append(44)
b = q.pop(0)
print(a, b, q)

Answer: 11 22 [33, 44]. FIFO is based on arrival order, not numeric magnitude.

Practice 17 — Non-destructive iteration#

q = ["P1", "P2"]
for item in q:
    print(item, end=" ")
print(len(q))

Answer: P1 P2 2 (on one line). Iteration prints the two codes but does not remove them; length stays two.

Practice 18 — Palindrome test#

from collections import deque
letters = deque("abba")
print(letters.popleft() == letters.pop())
print(list(letters))

Answer: True and ['b', 'b']. The first a and last a match; the two middle b values remain.

Short answers and reasoning (Practice 19–24)#

Practice 19 — Why is pop(0) inefficient for very large queues?#

Answer: Python lists store references in contiguous positions. Removing the first shifts subsequent references left, requiring work proportional to the queue's current length. For frequent FRONT removal, use collections.deque.popleft().

Practice 20 — Is a Python list literally unlimited in capacity?#

Answer: No. It grows dynamically without a predetermined fixed classroom capacity, but available memory and implementation limits still apply. “No bound specified” is not the same as infinite capacity.

Practice 21 — Does a deque always follow FIFO?#

Answer: No. A deque only provides access at both ends. It follows FIFO if the program inserts consistently at one end and removes from the opposite end; same-end operations produce stack-like LIFO.

Practice 22 — Explain overflow and underflow with an example each.#

Answer: Underflow is a deletion request on an empty queue, such as dequeue after every item has been served. Overflow applies to an explicitly bounded queue, for example an attempt to enqueue a fourth item into a full capacity-three queue. Both should leave the structure in a valid state.

Practice 23 — Why may strict FIFO be inappropriate for emergency requests?#

Answer: FIFO ignores urgency. A priority scheme or separate urgent lane may be needed, while preserving FIFO among requests of equal priority and avoiding indefinite delays for lower-priority work.

Practice 24 — What happens to an odd-length palindrome's centre character?#

Answer: After comparing and deleting matching pairs from both ends, one middle character remains. It has no distinct partner to compare and does not make the word non-palindromic.

Applied programming (Practice 25–30)#

Practice 25 — Write a safe dequeue function#

def safe_dequeue(items):
    if not items:
        return False, None
    return True, items.pop(0)


print(safe_dequeue([]))
print(safe_dequeue([9, 8]))

Answer/output: (False, None) and (True, 9). The boolean distinguishes failure even if None is a valid stored item.

Practice 26 — Show queue state without consuming items#

def show(queue):
    return [f"{i}:{value}" for i, value in enumerate(queue, 1)]


q = ["A", "B", "C"]
print(show(q))
print(q)

Answer: ['1:A', '2:B', '3:C'] followed by ['A', 'B', 'C']. No dequeue occurs; state stays unchanged.

Practice 27 — Build a bounded queue of three#

def enqueue_bounded(items, value, capacity=3):
    if len(items) >= capacity:
        return False
    items.append(value)
    return True


q = [1, 2, 3]
print(enqueue_bounded(q, 4), q)

Answer: False [1, 2, 3]. Overflow is signalled and nothing is overwritten or dropped.

Practice 28 — Transfer a queue without changing order#

from collections import deque
source = deque(["T1", "T2", "T3"])
target = deque()
while source:
    target.append(source.popleft())
print(list(target))

Answer: ['T1', 'T2', 'T3']. Every item leaves source FRONT and joins target REAR in the same order.

Practice 29 — Palindrome check for mixed-case input#

from collections import deque


def relaxed_palindrome(text):
    clean = deque(ch.lower() for ch in text if ch.isalnum())
    while len(clean) > 1:
        if clean.popleft() != clean.pop():
            return False
    return True


print(relaxed_palindrome("Was it a rat I saw?"))

Answer: True. Explicit normalisation removes spaces and punctuation and ignores case; this is a different comparison rule from the exact NCERT example.

Practice 30 — Process up to n print jobs fairly#

from collections import deque


def serve(queue, count):
    served = []
    while queue and len(served) < count:
        served.append(queue.popleft())
    return served


jobs = deque(["J1", "J2", "J3", "J4"])
print(serve(jobs, 2), list(jobs))

Answer: ['J1', 'J2'] ['J3', 'J4']. Exactly the first two arrived jobs are served; the remaining order is preserved.

Quick Revision — Queue and Deque#

High-value exam checks#

1. Always label FRONT and REAR before tracing; do not reverse the list direction midway.
2. Underflow does not remove anything from an empty queue or deque.
3. peek() does not modify the structure.
4. If only one deque item remains, removing it from either end gives the same value.
5. pop(0) and pop() remove different ends of a Python list.
6. The deque data structure supports both FIFO and LIFO, depending on the operation pattern.
7. A dynamically sized Python list has no preset classroom capacity, but is not literally infinite.
8. For palindrome checking, state whether case and punctuation matter.
9. Priority service is an explicit enhancement, not the same as strict FIFO.
10. The textbook's Program 4-1 does not call dequeue on an empty queue after its guarded loop; avoid manufacturing an underflow output.

Viva / oral review#

Q. What is FIFO? The first item inserted is the first one removed from the pending queue.

Q. What is stored at FRONT? The element next in line for service.

Q. Why does a queue need two logical ends? New entries join REAR while old entries leave FRONT.

Q. What is an underflow? A deletion attempt from an empty structure.

Q. What does peek do? Returns the front element without changing the queue.

Q. Can a deque act as a stack? Yes; insert and delete at the same end.

Q. What is a Python efficiency improvement? Use collections.deque.popleft() instead of repeated list.pop(0).

Q. Why is one unmatched middle palindrome character acceptable? Every outer pair has already matched; the centre is symmetric with itself.

Q. Does every real service use perfect FIFO? No; priorities and multiple service channels may be applied.

Q. How would you test Exercise 6? Execute the operations in order and check all twelve intermediate queue states and both underflow events.