Is this pseudocode for implementation of a queue through an array valid?

Question

Write a pseudocode on implementing a queue through an array named Q of size n with 1-based indexing( i.e the index of Q starts from 1 instead of the usual 0).

The two functions below called Q.head and Q.tail must be utilized in the code which are described as follows:

Q.head : This function returns the index in the array Q where the next element is to be inserted.

Q.tail : This function returns the index in the array Q where the first element was stored in the beginning.

A precaution must be taken to address the Overflow and Underflow error in the code.

The code provided must have the 3 core functions named Enqueue,Dequeue which are described below:

Enqueue : This function takes two arguments and adds a new element in the queue,

Dequeue : This function takes no element argument and dequeues an element from the queue, following the usual FIFO (First In First Out) ordering.

The book from where I am studying is "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. The thing given in the book is as follows:

In our procedures ENQUEUE and DEQUEUE, we have omitted the error checking for underflow and overflow.

The pseudocode assumes that n=Q.length.

ENQUEUE(Q,x)
1 Q[Q.tail]=x
2 if Q:tail = = Q.length
3 Q:tail=1
4 else Q.tail = Q.tail + 1
DEQUEUE(Q)
1 x=Q[Q.head]
2 if Q.head == Q.length
3 Q.head=1
4 else Q.head = Q.head + 1
5 return x

---

As can be seen the above pseudocode uses a circular queue approach to implement the queue through the array Q.

But I think, this makes the question unnecessarily complicated and we can solve this "normally" as well, i.e without implementing a circular queue approach. Hence, I proceeded to write a pseudocode which does not uses the circular queue approach as follows:

Enqueue(Q,x)

   if (Q.tail==Q.length +1)

               error overflow

   else

           Q[Q.tail]=x
           Q.tail=Q.tail+1

  Dequeue(Q)

         int  fl=0, x=0

         If (Q.head<=Q.length )

              {

                x=Q[Q.head]

                 fl=1

              }

          If (Q.head<Q.length)

               Q.head=Q.head+1

                return x

          else 

                 print("Queue Empty")
                 error underflow

Is the above pseudocode a valid alternative to the approach as given in the book?

If there are any issues with the pseudocode I provided, please do let me know.

Answer 1

From the original example, with annotation:

ENQUEUE(Q,x)
    Q[Q.tail] = x
    if Q:tail == Q.length
        # not necessarily overflow -- this is just circular wrapping
        Q:tail = 1
    else
        Q.tail = Q.tail + 1

DEQUEUE(Q)
    x = Q[Q.head]
    if Q.head == Q.length
        # not necessarily underflow -- this is just circular wrapping
        Q.head = 1
    else
        Q.head = Q.head + 1
    return x

Note that this is already in contradiction to your statements:

Q.head : This function returns the index in the array Q where the next element is to be inserted.

Q.tail : This function returns the index in the array Q where the first element was stored in the beginning.

This is wrong. Q.head stores the index of the next element that will be returned when dequeuing. Q.tail stores the index of the next available position for an element when enqueuing.

Your task is to detect overflow and underflow. Consider the edge cases first...

Given the above, how do you know the queue is full? Well, Q.head must equal to Q.tail, because all other "available" positions were already used when you filled the queue. But then how do you know the queue is empty? Because surely that also would mean the two are equal.

How to distinguish between them? Use a sentinel value. You can do this however you want. A natural approach would be to consider: "if 'head' means the position of the next item to dequeue, and the queue is empty, then that value has no meaning".

That's a good candidate. You could instead have a special value to represent "pointing nowhere". If the queue is empty, then you set the head to zero. Now you have a real way to tell between full and empty, and you can adjust the algorithm as follows:

ENQUEUE(Q,x)
    # Raise error if queue has no available space
    if Q.tail == Q.head
        raise Q.overflow

    # Queue is no longer empty
    if Q.head == 0
        Q.head = Q.tail

    # Push data to queue
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
    else
        Q.tail = Q.tail + 1

DEQUEUE(Q)
    # Raise error if queue is empty
    if Q.head == 0
        raise Q.underflow

    # Pop data from queue
    x = Q[Q.head]
    if Q.head == Q.length
        Q.head = 1
    else
        Q.head = Q.head + 1

    # Mark queue empty if we just popped the last item
    if Q.head == Q.tail
        Q.head = 0

    return x