Data Structures — Queue

Queue: • A queue is a linear data structure that follows the FIFO (First In, First Out) principle — the first element inserted is the first one to be removed. • Think of a line at a ticket counter: the person who arrives first is served first. • Elements are added at the REAR (back) and removed from the FRONT. Basic Operations: 1. enqueue(item): Add an item at the rear of the queue. 2. dequeue(): Remove and return the item from the front. Error if empty (underflow). 3. peek() / front(): Return the front item without removing it. 4. is_empty(): Check whether the queue is empty. 5. size(): Return the number of items in the queue. Queue Implementation Using Python List: queue = [] # empty queue # Enqueue — add to rear (end of list) def enqueue(queue, item): queue.append(item) # Dequeue — remove from front (index 0) def dequeue(queue): if is_empty(queue): print('Queue Underflow — queue is empty') return None return queue.pop(0) # removes from front # Peek — view front element def peek(queue): if is_empty(queue): return None return queue[0] def is_empty(queue): return len(queue) == 0 def size(queue): return len(queue) # Example usage: q = [] enqueue(q, 'A') enqueue(q, 'B') enqueue(q, 'C') print(q) # ['A', 'B', 'C'] print(peek(q)) # 'A' print(dequeue(q)) # 'A' print(q) # ['B', 'C'] Note: list.pop(0) is O(n) — all remaining elements shift. For better performance, Python's collections.deque with popleft() is O(1). Applications of Queue: • CPU scheduling (Round Robin) • Print spooling (print jobs processed in order) • BFS (Breadth-First Search) in graphs • Call centre systems • Keyboard input buffer

Problem with Linear Queue: • In a linear queue, even after dequeuing elements from the front, those positions cannot be reused. • The rear pointer moves forward with every enqueue. When rear reaches the end of the array, no more elements can be added — even if there is free space at the front. • This is called 'false overflow.' Circular Queue: • A circular queue treats the array as circular — after the last position, the next position wraps around to index 0. • The rear and front pointers wrap around using modulo arithmetic: rear = (rear + 1) % capacity. • This eliminates false overflow and reuses vacant positions. Conditions: • Queue is EMPTY: front == -1 (or front > rear in some implementations) • Queue is FULL: (rear + 1) % capacity == front Circular Queue Implementation in Python: class CircularQueue: def __init__(self, capacity): self.capacity = capacity self.queue = [None] * capacity self.front = -1 self.rear = -1 def is_empty(self): return self.front == -1 def is_full(self): return (self.rear + 1) % self.capacity == self.front def enqueue(self, item): if self.is_full(): print('Queue Overflow') return if self.is_empty(): self.front = 0 self.rear = (self.rear + 1) % self.capacity self.queue[self.rear] = item def dequeue(self): if self.is_empty(): print('Queue Underflow') return None item = self.queue[self.front] self.queue[self.front] = None if self.front == self.rear: # last element removed self.front = -1 self.rear = -1 else: self.front = (self.front + 1) % self.capacity return item def display(self): print(self.queue) cq = CircularQueue(5) cq.enqueue(10); cq.enqueue(20); cq.enqueue(30) cq.dequeue() # removes 10 cq.enqueue(40) # fills the vacated spot

Stack vs. Queue — Key Differences: 1. Principle of Operation: • Stack: LIFO (Last In, First Out) — last inserted is first removed. • Queue: FIFO (First In, First Out) — first inserted is first removed. 2. Insertion and Deletion Points: • Stack: Both insertion (push) and deletion (pop) happen at the SAME end — the TOP. • Queue: Insertion (enqueue) at the REAR; deletion (dequeue) at the FRONT — opposite ends. 3. Number of Pointers: • Stack: Needs only ONE pointer — the top. • Queue: Needs TWO pointers — front and rear. 4. Access Pattern: • Stack: Only the top element is accessible. • Queue: Only the front element is accessible for removal. 5. Analogy: • Stack: Stack of plates, books on a shelf (last placed is first taken). • Queue: Ticket counter line, hospital waiting list (first to arrive, first served). Real-World Applications of Stack: 1. Undo/Redo in text editors and applications — each action is pushed; undo pops the last action. 2. Browser back button — visited pages are pushed; back button pops the most recent page. 3. Function call stack — each function call is pushed; return pops it. 4. Expression evaluation and conversion (infix to postfix). 5. Backtracking algorithms (maze solving, depth-first search). 6. Syntax checking (balanced parentheses in compilers). Real-World Applications of Queue: 1. CPU process scheduling (Round Robin — each process gets equal CPU time in order). 2. Print queue / spooling — print jobs are processed in the order submitted. 3. Call centre systems — customers wait in a queue; answered in order of arrival. 4. Breadth-First Search (BFS) in graphs — explores nodes level by level. 5. Keyboard input buffer — keystrokes are queued and processed in order. 6. Message queues in networking — packets are queued for transmission. 7. Ticket booking systems — requests processed in order of arrival.