Self-checkedTier 1 15 min readpds.queue-adt

Queue (abstract data type)

A queue serves items in the order they arrived (first in, first out). Learn the circular array implementation with its two conventions for telling a full queue from an empty one, the formula for the number of items, linked and two-stack queues, and the deque.

Why it exists

Whenever things must be handled in the order they arrive, you need a queue: print jobs, packets waiting to be sent, processes waiting for the CPU, a breadth-first search. The rule is FIFO (first in, first out), the opposite of a stack. The interesting part is the implementation: a naive array queue wastes space, and the fix, a circular array, has several conventions that change every formula.

Prerequisites

Arrays and indexing

Precise definitions

Queue. A collection in which items are inserted at one end, the rear (or tail), and removed from the other end, the front (or head). The item removed is the one that has waited longest.
Operations.

Operation	What it does	Cost (good implementation)
`enqueue(x)`	add `x` at the rear	$O(1)$
`dequeue()`	remove and return the front item	$O(1)$
`front()` (peek)	read the front item	$O(1)$
`isEmpty()`, `isFull()`	state tests	$O(1)$

Overflow is enqueue on a full queue. Underflow is dequeue on an empty one.

Linear array queue and its flaw

Keep front and rear indices in q[0 .. N-1]. Enqueue moves rear forward, dequeue moves front forward, and neither ever moves back. After $N$ enqueues the queue reports "full" even if many items have been dequeued and the cells at the front are free. This false overflow wastes space.

Circular array queue

Let the indices wrap around with the remainder operator. Index $N - 1$ is followed by index 0. Now freed cells at the front are reused. There are two standard conventions. Know which one a question uses.

	Convention A: keep a `count`	Convention B: leave one slot unused
Start	`front = rear = 0`, `count = 0`	`front = rear = 0`
`rear` means	the index where the next item goes	same
Enqueue	`q[rear] = x; rear = (rear + 1) % N; count++`	`q[rear] = x; rear = (rear + 1) % N`
Dequeue	`x = q[front]; front = (front + 1) % N; count--`	`x = q[front]; front = (front + 1) % N`
Empty	`count == 0`	`front == rear`
Full	`count == N`	`(rear + 1) % N == front`
Capacity	$N$ items	$N - 1$ items
Number of items	`count`	`(rear - front + N) % N`

Why convention B wastes a cell. When the queue holds $N$ items, rear has come all the way round to meet front, so front == rear, which is exactly the test for empty. The two states cannot be told apart from the indices alone. Either keep a count (A) or never let the queue fill completely (B).

Linked queue

Keep two pointers, front and rear, to the first and last nodes of a singly linked list. Enqueue links a new node after rear. Dequeue removes the first node. Both are $O(1)$ . With only a head pointer, enqueue would need a walk to the end: $O(n)$ . When the last item is dequeued, rear must also be set to NULL, otherwise it dangles.

A circular linked list with a single pointer to the last node also works: the first node is last->next, so both ends are reachable in $O(1)$ .

Deque and priority queue

Deque (double-ended queue): insertion and deletion at both ends. An input-restricted deque allows insertion at one end only (deletion at both). An output-restricted deque allows deletion at one end only (insertion at both). A deque can behave as a stack or as a queue.
Priority queue: the item removed is the one with the highest priority, not the oldest. It is not FIFO and is normally built on a heap, covered later.

How it works

The animation is a real run of a circular queue (convention A) with $N = 5$ . Look at the three enqueues after the dequeues. The first of them (50, the fifth enqueue overall) fills the last cell q[4] and wraps rear from 4 to 0. The next (60) reuses the cell q[0] freed earlier, and the one after (70) fills q[1]. At the end the queue is full and front == rear again (both 2 now, both 0 at the start when it was empty). That is why count is needed.

A circular queue in an array

Real run, real addresses

C source

1#include <stdio.h>

3#define N 5

5int main(void) {

6 int q[N] = {0};

7 int front = 0, rear = 0, count = 0, x;

8 q[rear] = 10; rear = (rear + 1) % N; count++;

9 q[rear] = 20; rear = (rear + 1) % N; count++;

10 q[rear] = 30; rear = (rear + 1) % N; count++;

11 q[rear] = 40; rear = (rear + 1) % N; count++;

12 x = q[front]; front = (front + 1) % N; count--;

13 x = q[front]; front = (front + 1) % N; count--;

14 q[rear] = 50; rear = (rear + 1) % N; count++;

15 q[rear] = 60; rear = (rear + 1) % N; count++;

16 q[rear] = 70; rear = (rear + 1) % N; count++;

17 return 0;

18}

Stack

qint

0…d5e0

[0]

0…d5e4

[1]

0…d5e8

[2]

0…d5ec

[3]

0…d5f0

[4]

frontint

0…d5dc

rearint

0…d5d8

countint

0…d5d4

Amber = changed in this step. Hover a cell for its full address. Arrows show where a pointer points; the small tag under a cell names the pointers aimed at it.

Step 1

front = rear = 0 and count = 0: the queue is empty. rear is the slot the next enqueue will write.

1 / 10

front is where the next dequeue reads, rear is where the next enqueue writes. Both wrap around with % N. count tells full from empty. Produced by: real execution: every address and value is read from memory by the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog (ASLR off so the numbers are stable)

Worked examples

EX 1Circular queue with a count

Easy

#include <stdio.h>
 
#define N 5
 
static int q[N], front, rear, count;
 
static int enq(int x) {
    if (count == N) return 0;
    q[rear] = x;
    rear = (rear + 1) % N;
    count++;
    return 1;
}
 
static int deq(int *x) {
    if (count == 0) return 0;
    *x = q[front];
    front = (front + 1) % N;
    count--;
    return 1;
}
 
int main(void) {
    int x;
    for (int v = 1; v <= 4; v++) enq(v * 10);
    deq(&x);
    printf("dequeued %d ", x);
    deq(&x);
    printf("%d\n", x);
    for (int v = 5; v <= 7; v++) enq(v * 10);
    printf("enqueue 80: %s\n", enq(80) ? "ok" : "full");
    while (deq(&x)) printf("%d ", x);
    printf("\n");
    return 0;
}

Output:

dequeued 10 20
enqueue 80: full
30 40 50 60 70

Reading it. Four enqueues and two dequeues leave 30 and 40. Three more enqueues (50, 60, 70) wrap around and fill the queue (5 items), so 80 is refused. The remaining items come out in arrival order: 30, 40, 50, 60, 70. A linear array queue of size 5 would have accepted 50 (rear was at 4) but refused 60 and 70, although two cells at the front had been freed.

EX 2One slot unused: capacity N - 1 and the size formula

Medium

#include <stdio.h>
 
#define N 5
 
static int q[N], front, rear;
 
static int enq(int x) {
    if ((rear + 1) % N == front) return 0;
    q[rear] = x;
    rear = (rear + 1) % N;
    return 1;
}
 
static int deq(int *x) {
    if (front == rear) return 0;
    *x = q[front];
    front = (front + 1) % N;
    return 1;
}
 
int main(void) {
    int x, r[5];
    for (int v = 1; v <= 5; v++) r[v - 1] = enq(v);
    printf("%d %d %d %d %d\n", r[0], r[1], r[2], r[3], r[4]);
    printf("%d\n", (rear - front + N) % N);
    deq(&x);
    deq(&x);
    enq(6);
    enq(7);
    printf("%d %d %d\n", (rear - front + N) % N, front, rear);
    return 0;
}

Output:

1 1 1 1 0
4
4 2 1

Reading it. An array of 5 cells holds only 4 items in this convention: the fifth enqueue is refused (r[4] is 0). The size formula gives 4. After two dequeues and two enqueues, front = 2 and rear has wrapped to 1, and the formula $(1 - 2 + 5) \bmod 5 = 4$ is the number of items. The + N is essential: in C, (rear - front) % N with rear < front is a negative remainder, not the size.

EX 3Counting items and checking full or empty from the indices

GATE level

A circular queue uses an array of size 8 (indices 0 to 7), convention B (one slot unused, front == rear means empty), with front = 5 and rear = 2.

Number of items. $(\text{rear} - \text{front} + N) \bmod N = (2 - 5 + 8) \bmod 8 = 5$ . Check by listing: the items are at indices 5, 6, 7, 0, 1 (the next free index is 2). That is 5 items.

Is it full? Full means $(\text{rear} + 1) \bmod 8 = \text{front}$ , that is $3 = 5$ : false. So 2 more items fit before it becomes full (capacity is 7, and 7 - 5 = 2).

Where is the front item and what happens to rear after 2 more enqueues? The front item is at q[5]. After two enqueues, rear becomes 4, and now $(4 + 1) \bmod 8 = 5 = \text{front}$ : full.

EX 4A queue built from two stacks

Medium

#include <stdio.h>
 
static int in[16], out[16];
static int ti = -1, to = -1, moves;
 
static void enq(int x) {
    in[++ti] = x;
}
 
static int deq(void) {
    if (to < 0)
        while (ti >= 0) {
            out[++to] = in[ti--];
            moves++;
        }
    return out[to--];
}
 
int main(void) {
    enq(1);
    enq(2);
    enq(3);
    int a = deq();
    enq(4);
    int b = deq();
    int c = deq();
    int d = deq();
    printf("%d %d %d %d %d\n", a, b, c, d, moves);
    return 0;
}

Output:

1 2 3 4 4

Reading it. New items go onto the in stack. When a dequeue finds out empty, everything is moved from in to out, which reverses the order, so the oldest item ends up on top. Each item is moved at most once (here 4 moves for 4 items), so dequeue costs $O(1)$ amortised, although a single dequeue that triggers a transfer costs $O(n)$ . Note that enq(4) did not disturb the items already in out.

EX 5A linked queue and the empty-queue edge case

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *front, *rear;
 
static void enq(int x) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->data = x;
    n->next = NULL;
    if (rear == NULL) front = n;
    else rear->next = n;
    rear = n;
}
 
static int deq(void) {
    struct node *n = front;
    int x = n->data;
    front = n->next;
    if (front == NULL) rear = NULL;
    free(n);
    return x;
}
 
int main(void) {
    enq(1);
    enq(2);
    enq(3);
    int a = deq();
    int b = deq();
    int c = deq();
    printf("%d %d %d %d\n", a, b, c, front == NULL && rear == NULL);
    return 0;
}

Output:

1 2 3 1

Reading it. Enqueue appends after rear (and handles the empty case, where the new node is both front and rear). Dequeue removes the first node. (These sketches omit the empty-queue check on deq to stay short; real code must test for an empty queue first.) The line if (front == NULL) rear = NULL; is the one that is easy to forget: without it, after the last item is removed rear would still point at the freed node, and the next enq would write into freed memory.

EX 6Trace a deque

GATE level

A deque starts empty. The operations are: insertFront(1), insertRear(2), insertFront(3), deleteRear, insertRear(4), deleteFront. Write the content from front to rear after each step.

Operation	Content (front ... rear)	Removed
insertFront(1)	1
insertRear(2)	1 2
insertFront(3)	3 1 2
deleteRear	3 1	2
insertRear(4)	3 1 4
deleteFront	1 4	3

The final content is 1, 4. Insertion at the front pushes the new item before the old front. A common mistake is to treat insertFront as if it added at the rear.

Cheat box

FIFO. Enqueue at the rear, dequeue at the front. Both $O(1)$ in a circular array or a linked queue with two pointers.
Linear array queue: false overflow. Fix: circular, with % N.
Convention A (count): empty count == 0, full count == N, capacity $N$ .
Convention B (one slot unused): empty front == rear, full (rear + 1) % N == front, capacity $N - 1$ , items $= (\text{rear} - \text{front} + N) \bmod N$ .
With front == rear and no count, empty and full cannot be told apart.
In C, (rear - front) % N can be negative. Add N first.
Linked queue: set rear = NULL when the last item is removed.
Queue from two stacks: amortised $O(1)$ . Deque: insert and delete at both ends. Priority queue is not FIFO.

Traps and GATE patterns

Connections

Builds on

Arrays and indexing

Unlocks

Queue applications and queue using stacksPrerequisite ofplanned

BFS and DFSPrerequisite of BFS and DFSuses Stack (abstract data type)contrasts with Singly linked listsuses Binary tree traversalsuses Priority queues and building a heapcontrasts with

Across subjects

CPU scheduling: criteria, FCFS, SJF and SRTFuses BFS and DFSuses

Within this subject

Stack (abstract data type)contrasts-with

Queue applications and queue using stacksusesplanned

Singly linked listsuses

The queue is the mirror image of the stack. Its main uses are in queue applications: breadth-first search, scheduling and buffering. Operating systems keep ready queues of processes (CPU scheduling), and breadth-first search uses a queue (graph traversals). The linked version uses the nodes of singly linked lists.

PYQs

9 previous year questions from your book. I re-solved each one myself (6 by running or simulating, 3 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2018 · MCQQ7 · page 56 of the book

A queue is implemented using a non-circular singly
linked list. The queue has a head pointer and a tail
pointer, as shown in the figure. Let n denote the
number of nodes in the queue. Let 'enqueue' be
implemented by inserting a new node at the head, and
'dequeue' be implemented by deletion of a node from
the tail.

Which one of the following is the time complexity of
the most time-efficient implementation of 'enqueue'
and 'dequeue, respectively, for this data structure?

(a)θ(1), θ(1)
(b)θ(1), θ(n)
(c)θ(n), θ(1)
(d)θ(n), θ(n) } for (index = 0; index <= 3; index++) { printf("Value at index %d is %d\n", index, head- >value); head = head→next; printf("Value at index %d is %d\n", index+1, head→value); } } DATA STRUCTURE

GATE 2026 · Set 2 · MSQ · 2 marksQ1 · page 61 of the book

Consider a stack S and a queue Q. Both of them are
initially empty and have the capacity to store ten
elements each. The elements 1,2,3,4, and 5 arrive
one by one, in that order. When an element arrives,
it is assigned either to S (pushed on S ) or to Q
(enqueued to Q ). Once all the five elements are
stored, the output is generated in two steps. First,
stack S is emptied by popping all elements. Then
queue Q is emptied by dequeueing all elements.
The output obtained by following this process is
43125 .
Given the output, the objective is to predict whether
an element was assigned to S or Q.
Which of the following options is/are possible valid
assignment(s) of the elements?
Note: In the options, the notation xS denotes that
element x was assigned to S and yQ denotes that
element y was assigned to Q.

(a)1S,2Q,3S,4S,5Q
(b)1Q,2Q,3S,4S,5Q
(c)1Q,2Q,3Q,4S,5S
(d)1S,2S,3S,4Q,5Q

GATE 2021 · NAT · 1 markQ2 · page 61 of the book

Consider the following sequence of operations on
an empty stack.
push(54); push(52); pop(); push(55); push(62); s =
pop();
Consider the following sequence of operations on
an empty queue.
enqueue (21); enqueue (24); dequeue (); enqueue
(28); enqueue (32); q = dequeue();
The value of s +q is
.
We maintain exactly two external pointers FRONT
and REAR pointing to the front node and the rear
node of the queue, respectively. Which of the
following statements is/are CORRECT for such a
circular queue, so that insertion and deletion
operations can be performed in O(1) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

(a)I only
(b)II only
(c)Both I and II
(d)Neither I nor II

GATE 2017 · Set 2 · MCQ · 1 markQ3 · page 61 of the book

A circular queue has been implemented using a
singly linked list where each node consists of a
value and a single pointer pointing to the next node.
DATA STRUCTURE

The maximum possible number of iterations of the
while loop in the algorithm is
.

GATE 2016 · Set 1 · MCQ · 1 markQ4 · page 61 of the book

A queue is implemented using an array such that
ENQUEUE
and
DEQUEUE
operations
are
performed efficiently. Which one of the following
statements is CORRECT (n refers to the number of
items in the queue)?
Both operations can be performed in O(1) time.

(a)Both operations can be performed in O(1) time
(b)At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
(c)The worst case time complexity for both operations will be Ω(n)
(d)Worst case time complexity for both operations will be Ω(logn)

GATE 2016 · Set 1 · NAT · 2 marksQ5 · page 61 of the book

Let Q denote a queue containing sixteen numbers and
S be an empty stack. Head(Q) returns the element at
the head of the queue Q without removing it from Q.
Similarly Top(S) returns the element at the top of S
without removing it from S. Consider the algorithm
given below.

GATE 2013 · MCQ · 2 marksQ8 · page 62 of the book

Suppose a stack implementation supports an
instruction REVERSE, which reverses the order of
elements on the stack, in addition to the PUSH and
POP instructions. Which one of the following
statements is TRUE (with respect to this modified
stack)?

(a)A queue cannot be implemented using this stack.
(b)A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
(c)A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
(d)A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

GATE 2012 · MCQ · 2 marksQ10 · page 62 of the book

Suppose a circular queue of capacity (n - 1) elements
is implemented with an array of n elements. Assume
that the insertion and deletion operations are carried
out using REAR and FRONT as array index
variables, respectively. Initially, REAR = FRONT =
0. The conditions to detect queue full and queue
empty are

(a)full: (REAR+1)mod n == FRONT, empty: REAR == FRONT
(b)full: (REAR+1)mod n == FRONT, empty: (FRONT+1) mod n == REAR
(c)full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
(d)full: (FRONT+1)mod n == REAR empty: REAR == FRONT DATA STRUCTURE

GATE 2006 · MCQQ12 · page 63 of the book

An implementation of a queue Q, using two stacks
S1 and S2, is given below:
void insert (Q, x) {
push(S1, x);

Self-check

Question 1

A circular queue (convention A, with a count) has $N = 6$ cells. It starts empty. Operations: enqueue 5 items, dequeue 4, enqueue 3. What are front, rear and count?

Show answer

After 5 enqueues: front = 0, rear = 5, count = 5. After 4 dequeues: front = 4, count = 1. After 3 more enqueues: rear goes $5 \to 0 \to 1 \to 2$ (wrapping once), count = 4. So front = 4, rear = 2, count = 4. Check the cells: items are at indices 4, 5, 0, 1, which is 4 items.

Question 2

Convention B, $N = 7$ , front = 3, rear = 1. How many items are in the queue, and is it full?

Show answer

Items $= (1 - 3 + 7) \bmod 7 = 5$ (at indices 3, 4, 5, 6, 0). Full would need $(1 + 1) \bmod 7 = 3$ , but $2 \ne 3$ , so it is not full. One more item fits (capacity is $N - 1 = 6$ ).

Question 3

Two stacks implement a queue as in example 4. Items 1, 2, 3 are enqueued, then 2 dequeues happen, then 4 and 5 are enqueued, then 1 dequeue. Which item does the last dequeue return?

Show answer

The first dequeue moves 1, 2, 3 to the output stack and returns 1; the second returns 2. Items 4 and 5 go onto the input stack. The output stack still holds 3, so the last dequeue returns 3, preserving first-in, first-out order.

Question 4

A linear (non-circular) array queue of size 5 has had 5 enqueues and 3 dequeues. Can it accept another enqueue? Can a circular queue in the same state?

Show answer

The linear queue's rear is already at the end of the array, so it reports overflow although 3 cells at the front are free (false overflow). The circular queue (with a count, or one slot unused) wraps around and accepts the item.

Question 5

Which structure is natural for breadth-first search, and which for depth-first search?

Show answer

Breadth-first search explores the oldest discovered vertex first, so it uses a queue. Depth-first search explores the most recently discovered vertex first, so it uses a stack (or recursion, which is the call stack).

Revision card

One-screen revision

Queue = FIFO. Enqueue at rear, dequeue at front, both $O(1)$ .
Circular array: indices wrap with % N. Linear array wastes space (false overflow).
Convention A: count; capacity $N$ . Convention B: one slot unused; capacity $N-1$ ; empty front == rear; full (rear + 1) % N == front; items (rear - front + N) % N.
Always check the convention given in the question.
Linked queue: front and rear; set rear = NULL when emptied.
Two stacks make a queue with amortised $O(1)$ operations.
Deque: both ends. Priority queue: not FIFO.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Section 10.1 Stacks and queues
·Kernighan and Ritchie, The C Programming Language, 2nd ed., Section 6.5 Self-referential Structures (the struct-with-pointer idea behind linked queues)

Verification

The animation replays a real run of an instrumented C program: every cell and index is read from memory at each step, and the test suite checks the wrap-around of rear and that the full and the empty queue have front == rear. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c, also under AddressSanitizer and UBSan. The textbook section numbers were written from memory and have NOT been checked against the books. The prose, the formulas for the one-slot-unused convention and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Stack (abstract data type)

Singly linked lists