Exploring Static Queue Operations and Complexity

[evinda]

Hi! (Wave)

I am looking at the operations of a static queue.

pointer MakeEmptyQueue(void)
          pointer Q; /* temporary pointer */
          Q = NewCell(Queue); /* malloc() */
          Q->Front = 0;
          Q->Length = 0;
          return Q;

I have to find the complexity of the above algorithm. Isn't it $\Theta(1)$? (Thinking)

void Enqueue(pointer Q, Type x)
       if (Q->Length == N) then error
       else {
              Q->Length = Q->Length+1;
              (Q->A)[(Q->Front + Q->Length –1)% N] = x;
       }

Could you explain me this command: [m](Q->A)[(Q->Front + Q->Length –1)% N] = x; [/m]? Also, the algorithm [m] Enqueue [/m] of the queue, as a linked list, is this:

void Enqueue(Type x, pointer Q)
       pointer P; /* temporary pointer */
       P = NewCell(Node);
       P->data = x;
       P->next = NULL;
       if (IsEmptyQueue(Q)) then Q->Front = P;
      else Q->Back->next = P;
      Q->Back = P;

Could you explain me why both pointers [m] Q->Back->next[/m] and [m] Q->Back[/m] have to point to [m]P[/m] ? (Thinking)At the algorithm [m] Dequeue[/m]:

Type Dequeue(pointer Q)
        if (IsEmptyQueue(Q)) then error;
        else {
               x = (Q->Front)->data;
               Q->Front = (Q->Front)->next;
               if (Q->Front == NULL) then
                  Q->Back = NULL;
               return x;
        }

why are these lines needed?

if (Q->Front == NULL) then
   Q->Back = NULL;

 

[I like Serena]

Hi! (Wave)

Hey! (Blush)

I am looking at the operations of a static queue.

pointer MakeEmptyQueue(void)
          pointer Q; /* temporary pointer */
          Q = NewCell(Queue); /* malloc() */
          Q->Front = 0;
          Q->Length = 0;
          return Q;

I have to find the complexity of the above algorithm. Isn't it $\Theta(1)$? (Thinking)

Yep! (Nod)

void Enqueue(pointer Q, Type x)
       if (Q->Length == N) then error
       else {
              Q->Length = Q->Length+1;
              (Q->A)[(Q->Front + Q->Length –1)% N] = x;
       }

Could you explain me this command: [m](Q->A)[(Q->Front + Q->Length –1)% N] = x; [/m]?

The queue is implemented as an array with N entries.
The Q->Front is an index in the array Q->A[0..N-1] that can be somewhere in the middle.
When we enqueue a new entry, we need to calculate where the new entry is, which is at the index Q->Front + Q->Length - 1, except that if the index is beyond the end of the array Q->A[0..N-1], we need to "wrap" around to the beginning.
We can wrap around with the modulo (%) operation. (Wasntme)

Also, the algorithm [m] Enqueue [/m] of the queue, as a linked list, is this:

void Enqueue(Type x, pointer Q)
       pointer P; /* temporary pointer */
       P = NewCell(Node);
       P->data = x;
       P->next = NULL;
       if (IsEmptyQueue(Q)) then Q->Front = P;
      else Q->Back->next = P;
      Q->Back = P;

Could you explain me why both pointers [m] Q->Back->next[/m] and [m] Q->Back[/m] have to point to [m]P[/m] ? (Thinking)

This is a different implementation for a queue using a bidirectional linked list instead of an array.
When we add an entry to it, the tail of the list, which is Q->Back, needs to be updated to point to it.
And if the list was empty to begin with, the head of the list, which is Q->Front, also needs to point to it. (Nerd)

At the algorithm [m] Dequeue[/m]:

Type Dequeue(pointer Q)
        if (IsEmptyQueue(Q)) then error;
        else {
               x = (Q->Front)->data;
               Q->Front = (Q->Front)->next;
               if (Q->Front == NULL) then
                  Q->Back = NULL;
               return x;
        }

why are these lines needed?

if (Q->Front == NULL) then
   Q->Back = NULL;

Q->Back tracks the tail of the list.
When the list turns out to be empty, it needs to be updated to indicate there is nothing to point to anymore. (Nerd)

 

[evinda]

Hey! (Blush)

Yep! (Nod)

(Smirk)

The queue is implemented as an array with N entries.
The Q->Front is an index in the array Q->A[0..N-1] that can be somewhere in the middle.
When we enqueue a new entry, we need to calculate where the new entry is, which is at the index Q->Front + Q->Length - 1, except that if the index is beyond the end of the array Q->A[0..N-1], we need to "wrap" around to the beginning.
We can wrap around with the modulo (%) operation. (Wasntme)

Could you explain me why we have to put the new element in the
[m]Q->Front + Q->Length - 1 (mod N)[/m] position?

When we add an entry to it, the tail of the list, which is Q->Back, needs to be updated to point to it.

This is done by this command: [m]else Q->Back->next = P;[/m], right? (Worried)

But, what does this command: [m]Q->Back = P;[/m] do?

Q->Back tracks the tail of the list.
When the list turns out to be empty, it needs to be updated to indicate there is nothing to point to anymore. (Nerd)

So, does it only need to be updated, when there are no more elements? (Thinking)

 

[I like Serena]

Could you explain me why we have to put the new element in the
[m]Q->Front + Q->Length - 1 (mod N)[/m] position?

What is it that you do not understand? (Wondering)

At index Q->Front we have the first entry in the queue.
Since there are Q->Length entries in the queue, we need to add that to the index.
And as always, there is some plus or minus 1 magic. (Nerd)

This is done by this command: [m]else Q->Back->next = P;[/m], right? (Worried)

Yes. (Smile)

But, what does this command: [m]Q->Back = P;[/m] do?

It sets the pointer to the back of the queue, to the new element that we have just added a the back of the queue. (Wasntme)

So, does it only need to be updated, when there are no more elements? (Thinking)

Yep! (Mmm)

 

[evinda]

What is it that you do not understand? (Wondering)

At index Q->Front we have the first entry in the queue.
Since there are Q->Length entries in the queue, we need to add that to the index.
And as always, there is some plus or minus 1 magic. (Nerd)

I haven't understood why we take $\mod N$.

Could you explain it maybe to me with an example? (Thinking)

Yes. (Smile)
It sets the pointer to the back of the queue, to the new element that we have just added a the back of the queue. (Wasntme)

Yep! (Mmm)

I see... (Smile)

This is a different implementation for a queue using a bidirectional linked list instead of an array.

So, do we not implement a queue with a singly linked list? (Thinking)

 

[I like Serena]

I haven't understood why we take $\mod N$.

Could you explain it maybe to me with an example? (Thinking)

Here's an example how a queue in an array works that I wrote for your friend. ;)
You should read [m]Front[/m] and [m]Back[/m] where is says $head$ respectively $end$.If there is 1 element in a queue, the queue looks like:
$$-\ \ - \ - \underset{\stackrel\uparrow{head}}o \underset{\stackrel\uparrow{end}}- \ \ -$$
That means that:
$$head+1 \equiv end\pmod{n}$$At some point in time the queue might look like:
$$o \underset{\stackrel\uparrow{end}}- - \underset{\stackrel\uparrow{head}}o o \ \ o$$

If we add one more element at the end, we get:
$$o\ \ o \underset{\stackrel\uparrow{end}}- \underset{\stackrel\uparrow{head}}o o\ \ o$$

At this point we cannot add any more elements, because if $head=end$, that means we consider this an empty queue. In other words, the queue is full or complete when:
$$end+1 \equiv head \pmod{n}$$

When $head=end$ we consider the queue empty.
(Mmm)

So, do we not implement a queue with a singly linked list? (Thinking)

We could, and actually we should. (Nod)

The fact that a doubly linked list was chosen makes it a deque rather than a queue, since it supports taking elements from both sides. (Nerd)

 

[evinda]

At some point in time the queue might look like:
$$o \underset{\stackrel\uparrow{end}}- - \underset{\stackrel\uparrow{head}}o o \ \ o$$

Why is it in this case $head+1 \equiv end \pmod{n}$ ? (Worried)

 

[I like Serena]

Why is it in this case $head+1 \equiv end \pmod{n}$ ? (Worried)

It isn't. (Shake)
That condition only applies if there is 1 element in the queue. (Nod)

 

[evinda]

It isn't. (Shake)
That condition only applies if there is 1 element in the queue. (Nod)

Which is then the general formula for the pointer tail? Or isn't there a general formula for the position it points to? (Thinking)

 

[I like Serena]

Which is then the general formula for the pointer tail? Or isn't there a general formula for the position it points to? (Thinking)

The formula, or rather relation, is:
$$end \equiv head + m \pmod n$$
where $m$ is the number of items in the queue, and $n$ is the total size of the array. (Thinking)