patternMinor
Understanding basic queue and dequeue operations
Viewed 0 times
understandingoperationsdequeueandqueuebasic
Problem
CLRS gives the following implementation for a queue's enqueue and dequeue operations
but I'm having trouble understanding why both
and
are needed. What would be a conceptual (or possibly visual) explanation of these two if-statements?
head = 1
tail = 1
ENQUEUE(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1
DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head + 1
return xbut I'm having trouble understanding why both
if Q.tail == Q.length
Q.tail = 1and
if Q.head == Q.length
Q.head = 1are needed. What would be a conceptual (or possibly visual) explanation of these two if-statements?
Solution
CLRS defines a queue using an array which wraps around i.e when we no longer can insert/delete in the last position, we move to the first position.
From the book,
The elements in the queue are in locations head[Q], head [Q] + 1, . . . , tail [Q] - 1, where we "wrap around" in the sense that location 1 immediately follows location n in a circular order.
Thus,
if Q.tail == Q.length
This is for the condition when the tail points to the last element.
if Q.head == Q.length
This is for the condition when the head points to the last element.
In both cases, we move to the first element due to circular nature.
An example would be this:
From the book,
The elements in the queue are in locations head[Q], head [Q] + 1, . . . , tail [Q] - 1, where we "wrap around" in the sense that location 1 immediately follows location n in a circular order.
Thus,
if Q.tail == Q.length
This is for the condition when the tail points to the last element.
if Q.head == Q.length
This is for the condition when the head points to the last element.
In both cases, we move to the first element due to circular nature.
An example would be this:
Context
StackExchange Computer Science Q#99587, answer score: 3
Revisions (0)
No revisions yet.