What Are the Complexity and Operations of a Static Queue?

Click For Summary

Discussion Overview

The discussion revolves around the complexity and operations of a static queue, including its implementation using arrays and linked lists. Participants explore the algorithms for queue operations such as Enqueue and Dequeue, and the implications of using different data structures.

Discussion Character

  • Technical explanation
  • Conceptual clarification
  • Debate/contested

Main Points Raised

  • Some participants propose that the complexity of the MakeEmptyQueue function is $\Theta(1)$.
  • There is a discussion on the Enqueue operation for a static queue, specifically the calculation of the index using the formula (Q->Front + Q->Length - 1) % N, which is explained as necessary for wrapping around the array.
  • Participants question why both Q->Back->next and Q->Back need to point to the new element in the linked list implementation of Enqueue.
  • Clarifications are sought regarding the necessity of setting Q->Back to NULL when the queue becomes empty after a Dequeue operation.
  • Some participants express confusion about the modulo operation and its application in determining the queue's state.
  • There is a mention of the differences between implementing a queue with a doubly linked list versus a singly linked list, with some suggesting that a singly linked list could also be used.
  • Participants discuss the conditions under which the queue is considered full or empty, particularly in relation to the head and end indices.

Areas of Agreement / Disagreement

Participants express varying levels of understanding regarding the implementation details and the implications of using different data structures for queues. There is no consensus on all points, particularly regarding the conditions for fullness and emptiness of the queue.

Contextual Notes

Some participants highlight the need for examples to clarify the modulo operation and its relevance in queue operations. There are also discussions about the implications of using a doubly linked list, which may lead to confusion about the nature of the data structure being used.

evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hi! (Wave)

I am looking at the operations of a static queue.

Code: 
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)

Code: 
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]? :confused:Also, the algorithm [m] Enqueue [/m] of the queue, as a linked list, is this:
Code: 
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]:

Code: 
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? :confused:

Code: 
if (Q->Front == NULL) then
   Q->Back = NULL;
 
Last edited:
Technology news on Phys.org
evinda said:
Hi! (Wave)

Hey! (Blush)

I am looking at the operations of a static queue.

Code: 
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)
Code: 
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]? :confused:

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:
Code: 
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]:
Code: 
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? :confused:

Code: 
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)
 
I like Serena said:
Hey! (Blush)

Yep! (Nod)

(Smirk)
I like Serena said:
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?
I like Serena said:
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? :confused:

I like Serena said:
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)
 
evinda said:
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? :confused:

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)
 
I like Serena said:
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)
I like Serena said:
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)
 
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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)
 
I like Serena said:
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)
 
  • #10
evinda said:
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)
 

Similar threads

MHB In which case will the command be executed?
  • · Replies 7 ·
Replies
7
Views
3K
MHB How to Properly Implement the Delete() Algorithm for Linked Lists
  • · Replies 7 ·
Replies
7
Views
2K
Python Simple code example of transforming matrix into upper triangular form
  • · Replies 3 ·
Replies
3
Views
2K
MHB List that contains only the elements of the one of the two given lists
  • · Replies 6 ·
Replies
6
Views
2K
MHB Collision of Planets: FF & AS Destruction
  • · Replies 1 ·
Replies
1
Views
2K
MHB Algorithm for Ordering Odds & Evens in Linked List L
  • · Replies 2 ·
Replies
2
Views
2K
MHB What are the memory requirements for the Pop and Push algorithms in C?
  • · Replies 11 ·
Replies
11
Views
4K
C/C++ How to Implement Polynomial Operations in C++?
  • · Replies 5 ·
Replies
5
Views
3K
MHB Function Pop for a static stack
  • · Replies 7 ·
Replies
7
Views
2K
MHB What is the Time Complexity of These Binary Search Tree Functions?
  • · Replies 3 ·
Replies
3
Views
2K