Queues

ACompressed recap

🧾

Queues are FIFO: enqueue at rear, dequeue at front. The linear array version wastes the slots before front. The circular version wraps indices with % N: empty when front == rear, full when (rear + 1) % N == front, capacity N − 1, count (rear − front + N) % N (a counter version uses all N slots). A deque works at both ends; a priority queue removes the highest priority (unsorted O(1)/O(n), sorted O(n)/O(1)). Two stacks make a queue with O(1) amortized operations; two queues make a stack with O(n) pops.

BMerged rule card

3.3.1 Queue ADT; linear array queue and its wasted-space problem

• Queue = FIFO: enqueue at rear, dequeue at front.
• Linear array: front = 0, rear = −1; q[++rear] = x; q[front++]; empty front > rear; full rear == MAX − 1.
• Items = rear − front + 1.
• Problem: slots before front are wasted; the next lesson bends the array into a ring.

3.3.2 Circular queue: full/empty conditions and index arithmetic

• Advance: i = (i + 1) % N.
• Standard: front = rear = 0 start; enqueue rear = (rear+1)%N; dequeue front = (front+1)%N.
• Empty: front == rear; full: (rear + 1) % N == front; capacity N − 1.
• Items: (rear − front + N) % N.
• Counter variant: full count == N, empty count == 0.

3.3.3 Deque; priority queue as a concept; queue from two stacks and stack from two queues (operation costs)

• Deque: insert/delete at both ends, O(1); input-/output-restricted variants.
• Priority queue: delete highest priority; unsorted O(1)/O(n), sorted O(n)/O(1); Phase 5 gives O(log n)/O(log n).
• Queue from 2 stacks: enqueue push(in); dequeue pop(out), pour in → out only when out empty; O(1) amortized.
• Stack from 2 queues: push O(1), pop O(n) (or the reverse).

CInterleaved GATE-style questions

Q1NAT1 markCircular

N = 7, front = 5, rear = 2 (standard convention). How many items?

Numerical answer: ________

Q2MCQ1 markEmpty

In the standard circular queue, which condition means empty?

• (A) (rear + 1) % N == front
• (B) rear == −1
• (C) front == rear
• (D) front == 0

Q3MCQ2 marksTrace

N = 4, front = rear = 0. enqueue A, B, C, D; dequeue; enqueue E; dequeue; enqueue F. Which enqueues fail?

• (A) D and F
• (B) none
• (C) D only
• (D) E and F

Q4MCQ1 markFIFO vs LIFO

Which structure serves a printer’s jobs in the order they were sent?

• (A) queue
• (B) priority queue
• (C) stack
• (D) deque used only at one end for both insert and delete

Q5NAT2 marksTwo stacks

Queue from two stacks (pour when out is empty): enqueue 1–4, dequeue, enqueue 5, 6, dequeue ×5. How many individual items are poured from in to out in total?

Numerical answer: ________

Q6MCQ2 marksPriority queue

A priority queue is kept in a sorted array (highest at the end) of n items. The cost of inserting a new item is:

• (A) O(n log n)
• (B) O(log n)
• (C) O(1)
• (D) O(n)

Q7MSQ1 markFacts

Which are true?

• (A) A circular queue with a counter can hold N items.
• (B) A deque can simulate a stack.
• (C) A linear array queue always uses every slot.
• (D) A deque can simulate a queue.

Q8MCQ2 marksOutput

What does this print?

#define N 5
int q[N];
int front = 0, rear = 0;   /* front: one slot BEFORE the first item; rear: last item */

int enqueue(int x)
{
    if ((rear + 1) % N == front) return 0;   /* full: N - 1 items */
    rear = (rear + 1) % N;
    q[rear] = x;
    return 1;
}

int dequeue(int *x)
{
    if (front == rear) return 0;             /* empty */
    front = (front + 1) % N;
    *x = q[front];
    return 1;
}

int main(void)
{
    int i, x, ok = 0;
    for (i = 1; i <= 5; i++) ok += enqueue(i * 10);
    printf("stored %d; ", ok);
    dequeue(&x); printf("%d ", x);
    dequeue(&x); printf("%d ", x);
    enqueue(60);
    enqueue(70);
    ok = enqueue(80);
    printf("; front=%d rear=%d; enqueue(80) -> %d\n", front, rear, ok);
    return 0;
}

• (A) stored 4; 10 20 ; front=2 rear=1; enqueue(80) -> 0
• (B) stored 4; 10 20 ; front=2 rear=1; enqueue(80) -> 1
• (C) stored 5; 10 20 ; front=2 rear=2; enqueue(80) -> 1
• (D) stored 4; 40 30 ; front=2 rear=1; enqueue(80) -> 0

DAnswer Vault