Queues

Definition

A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. The element inserted first is removed first, like a line at a ticket counter.

Basic Operations

• enqueue(x) — insert x at the rear.
• dequeue() — remove and return the element at the front.
• front() — return the front element without removing.
• isEmpty() / isFull().

All operations are O(1) in a proper implementation.

Array Implementation (Linear Queue)

#define MAX 100
int queue[MAX]; int front = 0, rear = -1;
void enqueue(int x) { if (rear == MAX - 1) return; queue[++rear] = x; }
int dequeue() { if (front > rear) return -1; return queue[front++]; }

Problem: in a linear queue, dequeued positions cannot be reused, wasting space.

Circular Queue

Wrap the rear around using modular arithmetic so empty slots at the front can be reused.

void enqueue(int x) {
    if ((rear + 1) % MAX == front) return; // full
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX;
    queue[rear] = x;
}
int dequeue() {
    if (front == -1) return -1;
    int x = queue[front];
    if (front == rear) front = rear = -1;
    else front = (front + 1) % MAX;
    return x;
}

Linked List Implementation

Maintain front and rear pointers. Enqueue attaches a new node to rear; dequeue advances front. Both are O(1).

Deque (Double-Ended Queue)

A deque supports insertion and deletion at both ends: pushFront, pushBack, popFront, popBack. Implemented as a circular array or doubly linked list. Deques generalize both stacks and queues.

Priority Queue

A priority queue removes elements in priority order, not insertion order. Implemented efficiently with a binary heap, giving O(log n) insert and delete-min. Priority queues drive Dijkstra's algorithm and Huffman coding.

Applications

1. CPU scheduling (ready queue).
2. Print spooler — prints jobs in order received.
3. Breadth-first search (BFS) in graphs.
4. Network packet buffering.
5. Producer-consumer synchronization.
6. IO buffers in operating systems.

Queue vs Stack

Summary

Queues process data in arrival order, essential for fair scheduling, buffering, and BFS. Circular queues avoid wasted space; priority queues generalize the idea to importance rather than arrival time.

Important Questions

1. Define queue and FIFO with an example.
2. Explain operations on a queue with complexity.
3. Implement a linear queue using arrays.
4. What is the drawback of linear queues? How is it solved?
5. Implement a circular queue.
6. Implement a queue using a linked list.
7. Differentiate stack and queue.
8. Explain priority queue and list two applications.