Queue

Revision Summary: Queue (NCERT Class 12)

1. Chapter at a Glance

• Queue is an ordered linear list that follows the First-In-First-Out (FIFO) / First Come First Served (FCFS) principle.
• Elements are inserted at the REAR (also called TAIL) and removed from the FRONT (also called HEAD).
• Core operations: ENQUEUE (insert at rear), DEQUEUE (remove from front), supported by IS EMPTY, PEEK and IS FULL.
• Overflow occurs when attempting ENQUEUE on a full queue; Underflow occurs when attempting DEQUEUE on an empty queue.
• In Python, queues are implemented using lists (dynamic size, so IS FULL is not required); append() adds at rear and pop(0) removes from front.
• Deque (Double-ended queue) allows insertion and deletion at both ends and can behave as either a stack or a queue.
• Deque operations: INSERTFRONT, INSERTREAR, DELETIONFRONT, DELETIONREAR (plus IS EMPTY, getFront, getRear).
• Common real-life uses: print-job scheduling, web-server request handling, OS job queues, and palindrome checking via deque.

2. Key Terms and Definitions

• Queue: An ordered linear list of elements having different ends for adding and removing elements; works on FIFO principle.
• FIFO (First In First Out): The element that enters the queue first is the first one to be removed; also called FCFS.
• REAR (TAIL): The end of the queue where new elements are always inserted (ENQUEUE).
• FRONT (HEAD): The end of the queue from where elements are always removed (DEQUEUE).
• ENQUEUE: Operation to insert a new element at the rear end of the queue.
• DEQUEUE: Operation to remove one element at a time from the front of the queue.
• Overflow: Exception raised when trying to insert an element into a queue that is already full.
• Underflow: Exception raised when trying to delete an element from an empty queue.
• IS EMPTY: Operation to check whether the queue contains any element (avoids underflow).
• PEEK: Operation to view the element at the front without removing it.
• IS FULL: Operation to check whether more elements can be added (avoids overflow).
• Deque: A double-ended queue in which addition and removal of elements can occur from either end (front or rear).

3. Syntax and Constructs

python myQueue = list() # create empty queue python def enqueue(myQueue, element): myQueue.append(element) # insert at rear python def isEmpty(myQueue): if len(myQueue) == 0: return True else: return False python def dequeue(myQueue): if not isEmpty(myQueue): return myQueue.pop(0) # remove from front else: print("Queue is empty") python def size(myQueue): return len(myQueue) python def peek(myQueue): if isEmpty(myQueue): print("Queue is empty") return None else: return myQueue[0] Deque functions (NCERT forms) python def insertFront(myDeque, element): myDeque.insert(0, element) python def insertRear(myDeque, element): myDeque.append(element) python def deletionRear(myDeque): if not isEmpty(myDeque): return myDeque.pop() else: print("Deque empty") python def deletionFront(myDeque): if not isEmpty(myDeque): return myDeque.pop(0) else: print("Deque empty") python def getFront(myDeque): if not isEmpty(myDeque): return myDeque[0] else: print("Queue empty") python def getRear(myDeque): if not isEmpty(myDeque): return myDeque[len(myDeque)-1] else: print("Deque empty")

4. Algorithms and Worked Logic

Palindrome checking using Deque (Algorithm 4.1)
Step 1: Traverse the string character by character from left to right.
Step 2: Insert each character at the rear using INSERTREAR.
Step 3: Repeat until all characters are inserted.
Step 4: Remove one character from front (DELETIONFRONT) and one from rear (DELETIONREAR).
Step 5: Compare the two removed characters.
Step 6: If they match, repeat Steps 4–5 until deque is empty or has one character left → string is palindrome; else stop (not palindrome).

Basic queue operation sequence (from Fig. 4.3)
ENQUEUE → ENQUEUE → ENQUEUE → DEQUEUE → ENQUEUE → DEQUEUE → DEQUEUE (Front moves right, Rear moves right on insertion).

5. Common Errors and Exam Pitfalls

• Forgetting to check isEmpty() before DEQUEUE/DELETION → underflow not handled, marks lost.
• Using pop() instead of pop(0) for front deletion (removes from wrong end).
• Confusing which end is FRONT and which is REAR when both are implemented with a list.
• Printing None returned by peek/dequeue on empty structure without handling the message.
• Assuming fixed-size queue and writing IS FULL check (not required in Python lists).
• In deque questions, mixing INSERT/DELETE ends or failing to state that deque can act as both stack and queue.
• Not writing the exact NCERT function signatures (parameter order, return values) in code questions.