Skip to main content

Linear and circular queue operations

Short answer

Linear queue moves front and rear forward; after dequeues free cells are unused, and overflow occurs when rear reaches N‑1. Circular queue wraps pointers modulo N, reusing free cells. Example: after two dequeues, a linear queue overflows on enqueue; circular wraps and succeeds.

Define linear and circular queue. Write down algorithms for basic operations that can be performed over linear and circular queues.

A queue is a linear data structure in which insertion takes place at one end, the rear, and deletion at the other end, the front. The element inserted first is removed first, so it follows FIFO (First In First Out).

  • A linear queue is stored in an array in a straight line; front and rear only move forward, so cells freed by deletion are not reused.
  • A circular queue treats the array as a ring (last cell connected to first); front and rear wrap around using % N, so freed cells are reused.

Linear queue (array Q[0..N-1], front = 0, rear = -1)

ENQUEUE(x)
1. if rear == N - 1:  print "Queue overflow"; return
2. rear = rear + 1
3. Q[rear] = x

DEQUEUE()
1. if front > rear:  print "Queue underflow"; return
2. x = Q[front]
3. front = front + 1
4. return x

Circular queue (array CQ[0..N-1], front = rear = -1)

ENQUEUE(x)
1. if (rear + 1) % N == front:  print "Queue overflow"; return
2. if front == -1:  front = rear = 0
   else             rear = (rear + 1) % N
3. CQ[rear] = x

DEQUEUE()
1. if front == -1:  print "Queue underflow"; return
2. x = CQ[front]
3. if front == rear:  front = rear = -1
   else               front = (front + 1) % N
4. return x

Example showing the difference (N = 5; insert 10..50, delete two, insert 60)

Linear queue:

OperationArray contents (index 0 → N-1)frontrear
enqueue(10)10 _ _ _ _00
enqueue(20)10 20 _ _ _01
enqueue(30)10 20 30 _ _02
enqueue(40)10 20 30 40 _03
enqueue(50)10 20 30 40 5004
dequeue() returns 10_ 20 30 40 5014
dequeue() returns 20_ _ 30 40 5024
enqueue(60): rear = 4 → Queue overflow_ _ 30 40 5024

Circular queue:

OperationArray contents (index 0 → N-1)frontrear
enqueue(10)10 _ _ _ _00
enqueue(20)10 20 _ _ _01
enqueue(30)10 20 30 _ _02
enqueue(40)10 20 30 40 _03
enqueue(50)10 20 30 40 5004
dequeue() returns 10_ 20 30 40 5014
dequeue() returns 20_ _ 30 40 5024
enqueue(60)60 _ 30 40 5020

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 2 questions →