Queue

A queue is a linear structure where items are added at one end (the rear) and removed from the other (the front): FIFO, first in, first out. It models any fair waiting line.

Linear queue (array)

Keep front and rear. Initially front = 0, rear = −1. Enqueue: items[++rear] = x. Dequeue: items[front++]. Empty when front > rear; full when rear == MAX − 1.

The flaw. After 5 enqueues and 5 dequeues in a queue of size 5, rear == MAX − 1, so the queue reports full although every cell is free. The cells to the left of front are wasted forever. Shifting everything left after each dequeue works but costs O(n).

Circular queue

Treat the array as a ring: after index MAX − 1 comes index 0. Advance with modulo: rear = (rear + 1) % MAX, front = (front + 1) % MAX. To tell full from empty, keep a count of items (or sacrifice one cell).

3.2 Program: circular queue and priority queue

#include <stdio.h>
#define MAX 4

typedef struct { int a[MAX]; int front, rear, count; } CQ;

void cq_init(CQ *q) { q->front = 0; q->rear = MAX - 1; q->count = 0; }
int  cq_enq(CQ *q, int x) {
    if (q->count == MAX) { printf("Overflow: %d rejected\n", x); return 0; }
    q->rear = (q->rear + 1) % MAX;
    q->a[q->rear] = x; q->count++;
    return 1;
}
int cq_deq(CQ *q, int *x) {
    if (q->count == 0) return 0;
    *x = q->a[q->front]; q->front = (q->front + 1) % MAX; q->count--;
    return 1;
}

/* Priority queue: smaller number = higher priority; kept sorted on insertion */
typedef struct { int item[10], pri[10], n; } PQ;
void pq_insert(PQ *q, int item, int pri) {
    int i = q->n - 1;
    while (i >= 0 && q->pri[i] > pri) { q->item[i+1] = q->item[i]; q->pri[i+1] = q->pri[i]; i--; }
    q->item[i+1] = item; q->pri[i+1] = pri; q->n++;
}

int main(void) {
    CQ q; int x; cq_init(&q);
    cq_enq(&q, 1); cq_enq(&q, 2); cq_enq(&q, 3);
    cq_deq(&q, &x); printf("dequeued %d\n", x);
    cq_enq(&q, 4); cq_enq(&q, 5); cq_enq(&q, 6);      /* 6 overflows */
    printf("front=%d rear=%d count=%d; array = [%d %d %d %d]\n",
           q.front, q.rear, q.count, q.a[0], q.a[1], q.a[2], q.a[3]);
    printf("order:");
    while (cq_deq(&q, &x)) printf(" %d", x);
    printf("\n");

    PQ p = {{0},{0},0};
    pq_insert(&p, 100, 3); pq_insert(&p, 200, 1); pq_insert(&p, 300, 2); pq_insert(&p, 400, 1);
    printf("priority order:");
    for (int i = 0; i < p.n; i++) printf(" %d(p%d)", p.item[i], p.pri[i]);
    printf("\n");
    return 0;
}

dequeued 1
Overflow: 6 rejected
front=1 rear=0 count=4; array = [5 2 3 4]
order: 2 3 4 5
priority order: 200(p1) 400(p1) 300(p2) 100(p3)

3.3 Priority queue and deque

A priority queue serves the item with the highest priority first; items of equal priority are served in arrival order.

Implementations: an ordered array/list (insert O(n), remove O(1)), an unordered one (insert O(1), remove O(n)), or a heap (both O(\log n), Unit 8). Uses: CPU scheduling, hospital triage, Dijkstra's algorithm, event simulation.

A double-ended queue (deque) allows insertion and deletion at both ends. An input-restricted deque inserts at one end only; an output-restricted deque deletes at one end only. A deque can act as both a stack and a queue.

3.4 Applications of queues

• CPU scheduling (round robin), printer spooling, keyboard buffers.
• Breadth-first search of trees and graphs (Unit 10).
• Simulation of waiting lines (bank counters, traffic).
• Buffering in streaming and network packets: producers enqueue, consumers dequeue at their own speed.
• Level-order traversal of a binary tree (Unit 7).

3.5 Seeing the ideas: queues in life and in memory

Queues are so familiar that we hardly notice them: the line at a railway ticket counter, the cars waiting at a traffic light, the documents waiting for the printer. In each case the person who arrived first is served first.

The photograph shows such a queue at a ticket window, and the figures translate it into arrays, indices and priorities.

(a) A ticket queue: front is served first

(b) Circular queue of size 5 after wrap-around

A circular queue is easiest to see on a ring, and a priority queue is easiest to feel in an emergency room. Both plates below come from simulations whose numbers are asserted.

(a) Ring-shaped interchange seen from above

(b) Circular queue of size 5 after wrap-around

(a) Ambulance, Cleveland EMS

(b) Waiting time, FIFO vs priority (minutes)

3.5.1 Eight applications of queues

1. Printer and job spooling. When many users send documents to one printer in a college lab, the spooler places the jobs in a queue and prints them in arrival order. No job is lost and none jumps ahead. The same idea is used for batch jobs on a shared server.
2. CPU scheduling. An operating system keeps the ready processes in a queue. In round-robin scheduling the process at the front gets a short time slice and then goes to the rear. Every process receives a fair share of the processor.
3. Bank and ticket counters. A bank token display or an online ticket system serves customers strictly in the order of arrival. The counter staff call the front token and the token is removed. A queue gives the fairness people expect.
4. Payment and message handling. Servers behind ConnectIPS, Fonepay and eSewa receive thousands of requests per second on festival evenings such as Dashain shopping. They place the requests in a queue so that bursts are absorbed and each one is processed in order. This prevents overload and loss of transactions.
5. Buffers for input and output. Keyboard characters, network packets and streaming video are stored in a queue until the program or the screen is ready. The circular queue is the usual buffer because it reuses space. This makes video playing smooth even when the internet speed varies.
6. Breadth-first search. To explore a graph or a maze level by level, the algorithm keeps the discovered vertices in a queue (Unit 10). The vertex that was discovered first is expanded first. This guarantees the shortest path in an unweighted graph.
7. Priority servicing. A hospital emergency ward and an operating system serve urgent items first by using a priority queue (Figure 3.2). Equal priorities are served in arrival order. This protects critical work from long waits.
8. Simulation of waiting lines. Planners simulate bus stops, toll plazas and airport check-in with queues to estimate waiting time and the number of counters needed. The result helps them to decide how many counters to open at a place like the Tribhuvan International Airport. A queue is the model of any service system.

Formula and fact sheet

• Queue is FIFO; enqueue at rear, dequeue at front; both O(1).
• Linear queue full: rear == MAX − 1; empty: front > rear.
• Circular: rear = (rear + 1) % MAX; full when count == MAX.
• Priority queue by heap: insert and remove O(\log n).
• Deque: both ends; input- or output-restricted variants.

Chapter summary

• A queue gives first-come-first-served access with O(1) operations.
• The linear array queue wastes cells; the circular queue reuses them with modulo arithmetic.
• Priority queues break FIFO by priority; deques allow both ends.
• Queues drive scheduling, buffering and BFS.

Practice

1. Define queue and state the conditions for overflow and underflow in a linear and a circular queue.
2. A linear queue of size 5 has had 5 enqueues and 3 dequeues. Is it full? How many items does it hold? What is the drawback?
3. Trace a circular queue of size 4 under: enq 10, enq 20, enq 30, deq, enq 40, enq 50, enq 60. Give final front, rear, count.
4. Distinguish between a queue and a priority queue with an example.
5. What is a deque? Name its two restricted forms.
6. Why does a circular queue need a count (or a spare cell)?
7. Describe how a stack can be built from two queues.
8. List four applications of a queue.

Answers and worked solutions

1. Queue: FIFO list with enqueue at rear and dequeue at front. Linear: overflow if rear == MAX−1, underflow if front > rear. Circular: overflow if count == MAX, underflow if count == 0.

2. rear == MAX − 1, so it reports full, yet it holds 2 items (5 − 3). Three cells at the left are free but unusable: the wasted-space drawback.

3. Start front 0, rear 3, count 0. enq 10, 20, 30 → idx 0, 1, 2, count 3. deq → 10, front 1, count 2. enq 40 → idx 3, count 3. enq 50 → rear wraps to idx 0, count 4. enq 60 → overflow. Final: front = 1, rear = 0, count = 4; queue order 20, 30, 40, 50.

4. A queue serves by arrival time (a ticket line); a priority queue serves by priority (an emergency patient is treated before an earlier routine patient).

5. A double-ended queue supports insert and delete at both ends. Input-restricted and output-restricted.

6. With only front and rear, a full queue and an empty queue produce the same relation between them, so one extra piece of information is needed.

7. Push: enqueue into Q1. Pop: move all but the last item from Q1 to Q2, dequeue the last one from Q1 as the result, then swap the names of Q1 and Q2. (Pop is O(n).)

8. CPU scheduling, print spooling, BFS, keyboard/network buffering.

Model answers (5 and 10 marks)

Q1. Define a queue. Explain its operations and differentiate it from a stack. (5 marks)

A queue is a linear data structure in which items are inserted at one end, the rear, and deleted from the other end, the front. It follows the FIFO rule (first in, first out): the item that has waited longest is served first, as in the ticket line of Plate 3.1.

Operations

1. enqueue(x): insert x at the rear; fails with overflow if the queue is full.
2. dequeue(): remove and return the item at the front; fails with underflow if the queue is empty.
3. peek(): read the front item without removing it.
4. isEmpty() and isFull(): test the state.

Point	Stack	Queue
Rule	LIFO	FIFO
Insertion	at the top	at the rear
Deletion	from the top	from the front
Pointers	one (top)	two (front and rear)
Typical use	undo, recursion	scheduling, buffers

For example, after enqueue(A), enqueue(B) and enqueue(C), a call to dequeue() returns A, not C. The stack would return C. With two pointers, a queue needs a little more bookkeeping than a stack, but both operations are O(1).

Q2. What is the drawback of a linear queue? How does a circular queue solve it? (5 marks)

In a linear queue made from an array, rear moves right at every enqueue and front moves right at every dequeue, but neither moves back.

When rear reaches MAX - 1 the queue is declared full, even if many cells at the left have been freed by earlier dequeues.

For example, with MAX = 5, after five enqueues and three dequeues the items D and E occupy cells 3 and 4, rear is 4, and enqueue(F) is refused although three cells are empty. This wasted space is called false overflow (Figure 3.1).

A circular queue treats the array as a ring whose last cell is followed by the first. The indices wrap around by the modulus operator:

• rear = (rear + 1) % MAX on enqueue;
• front = (front + 1) % MAX on dequeue.

A counter count records the number of items, so the queue is full when count == MAX and empty when count == 0.

(Without the counter, the full and empty cases would look alike.) In Plate 3.1(b) the items F and G reuse cells 0 and 1 freed by A and B, so all five cells are in use.

The circular queue therefore uses the whole array with the same O(1) operations, which is why it is used for buffers and schedulers.

Q3. Explain the circular queue with algorithms and a worked trace, and describe the priority queue and the deque. (10 marks)

Introduction. A queue is a FIFO list. The array version needs a circular arrangement to avoid false overflow. Variants such as the priority queue and the deque relax the strict FIFO rule.

Circular queue. Data: int q[MAX]; int front = 0, rear = -1, count = 0;

Enqueue(x): (1) if count == MAX, report overflow and stop; (2) rear = (rear + 1) % MAX; (3) q[rear] = x; (4) count = count + 1.

Dequeue(): (1) if count == 0, report underflow and stop; (2) x = q[front]; (3) front = (front + 1) % MAX; (4) count = count - 1; (5) return x.

Trace (MAX = 5, Plate 3.1b). Enqueue A, B, C, D, E: the items go to cells 0 to 4, rear = 4, count = 5, the queue is full. Dequeue twice: A and B leave, front = 2, count = 3. Enqueue F: rear = (4 + 1) % 5 = 0, so F goes to cell 0.

Enqueue G: rear = 1, G goes to cell 1 and count = 5. The queue content from front to rear is C, D, E, F, G.

Priority queue. Each item carries a priority and the item with the highest priority is removed first; equal priorities follow FIFO order.

With patients Hari (3), Sita (1), Ram (2), Gita (1), where 1 is most urgent, the service order is Sita, Gita, Ram, Hari (Figure 3.2a).

It can be implemented by an ordered list (insertion O(n), removal O(1)) or by a heap (both O(\log n), Unit 8).

Deque. A double-ended queue allows insertion and deletion at both ends (Figure 3.2b). An input-restricted deque inserts at one end only; an output-restricted deque deletes at one end only. It can act as a stack or as a queue.

Type	Insert	Delete	Order served	Use
Linear queue	rear	front	arrival	simple buffers
Circular queue	rear (wraps)	front (wraps)	arrival	I/O buffers, scheduling
Priority queue	by priority	highest priority	urgency	hospital, OS tasks
Deque	both ends	both ends	flexible	undo/redo, sliding window

Conclusion. The queue models fair service.

The circular form removes the waste of the linear array, the priority queue serves urgent work first and the deque gives the flexibility of both a stack and a queue; all basic operations remain O(1) except the priority queue, which needs O(\log n) with a heap.