Page 88 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 4: Queues

Queue operations in pseudo-code: Notes

ENQUEUE(Q, x)
Q[tail[Q]] <- x
if tail[Q] = length[Q]
then tail[Q] <- 1
else tail[Q] <- tail[Q] + 1
DEQUEUE(Q)
x <- Q[head[Q]]
if head[Q] = length[Q]
then head[Q] <- 1
else head[Q] <- head[Q] + 1
return x
These are also O(1) time operations.
Figure 4.1 shows the operations on a queue.
Figure 4.1: Operations on a Queue

front, rear (a) Empty queue

A

front rear
(b) A inserted

A B C

front rear
(c) B, C inserted

B C

front rear
(d) A deleted

C

front rear
(e) B deleted
C D

front rear
(f) D inserted

LOVELY PROFESSIONAL UNIVERSITY 83