Stacked Queues, An Advance in Data Structures

This article is about stacked queues to provide combined configuration of both structures to help us to access data in a fine way for proper memory allocation of the data.

Introduction

There are various types of structures to store date that can play important roles. But why do we have many structures to form more effective storage? With the same thought I play with some date structures and choose the queue and stack to renovate this advanced capability in data structures. Of course I am curious to have a tour with this. So let us proceed.

The Stacked Queue

This structure contains the basic logic of a queue and a stack. Well stacks play a major role here with the operations of push and pop with the additional operation of a queue, in other words, enqueue and dequeue. Here the stack has enqueue and dequeue methods.

Stacked Queue Operation

Operation                      Description
Push Insert an item into the stack with queue
Pop Pop all items in the current Stack item
Enqueue Insert an item into the current stack queue item
Dequeue Get an item from the current stack queue item
 

Algorithms

Pop Operation

  • Create a new queue
  • If Space.Count is less than one then
  • Assign a NewQueue as the last queue
  • Remove the last item
  • Set the current item
  • Else
  • Through an empty message

Push Operation

  • Create a new queue
  • Enter a value in the new queue
  • Add a new queue in the stack

Enqueue Operation

  • Call the current queue enqueue

Dequeue Operation

  • Call the current queue dequeue
  • If the last queue value then
  • Remove the current queue from the stack

C# code

  1. namespace QueuedStackApplication  
  2. {  
  3.     public class QueueStack  
  4.     {  
  5.         List<Queue> Space = new List<Queue>();  
  6.   
  7.         Queue CurrentQueue = new Queue();  
  8.   
  9.         // Push operation on Stack  
  10.         public void Push(int value)  
  11.         {  
  12.             CurrentQueue = new Queue();  
  13.             CurrentQueue.EnQueue(value);  
  14.             Space.Add(CurrentQueue);  
  15.         }  
  16.   
  17.         // Pop operation on stack  
  18.         public List<int> Pop()  
  19.         {  
  20.             Queue q = new Queue();  
  21.             if (Space.Count > 1)  
  22.             {  
  23.                 q = Space[Space.Count - 1];  
  24.                 Space.RemoveAt(Space.Count - 1);  
  25.                 CurrentQueue = Space[Space.Count - 1];  
  26.             }  
  27.             else  
  28.             {  
  29.                 MessageDisplay("Stack Empty");  
  30.                 return null;  
  31.             }  
  32.             return q.Space;  
  33.         }  
  34.   
  35.         //Enqueue operation on stack  
  36.   
  37.         public void EnQueue(int value)  
  38.         {  
  39.             CurrentQueue.EnQueue(value);  
  40.         }  
  41.   
  42.         // DeQueue operation on stack  
  43.         public int DeQueue()  
  44.         {  
  45.             var value = CurrentQueue.DeQueue();  
  46.             if (value == -1)  
  47.             {  
  48.                 Pop();  
  49.                 MessageDisplay("Queue empty for this Stack Item");  
  50.             }  
  51.             else  
  52.                 MessageDisplay(string.Empty);  
  53.   
  54.             return value;  
  55.         }  
  56.   
  57.         public string MessageDetails = string.Empty;  
  58.         public void MessageDisplay(String message)  
  59.         {  
  60.             MessageDetails = message;  
  61.         }  
  62.   
  63.         public void DisplayItem(Panel mainPanel)  
  64.         {  
  65.             mainPanel.Controls.Clear();  
  66.   
  67.             int top = 10;  
  68.             int left = 10;  
  69.   
  70.             Random r = new Random();  
  71.             foreach (var queue in Space)  
  72.             {  
  73.                 left = 10;  
  74.                 foreach (var item in (queue as Queue).Space)  
  75.                 {  
  76.                     Button panel = new Button();  
  77.                     panel.Width = 50;  
  78.                     panel.Height = 50;  
  79.                     panel.Top = top;  
  80.                     panel.Left = left;  
  81.                     panel.Font = new System.Drawing.Font("Microsoft Sans Serif",    12F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0)));  
  82.                     panel.Text = item.ToString();  
  83.                     panel.BackColor = (item % 2 == 0) ? Color.LightPink : Color.LightSkyBlue;  
  84.                     panel.Click += panel_Click;  
  85.                     mainPanel.Controls.Add(panel);  
  86.                     left = left + panel.Width + 10;  
  87.                 }  
  88.                 top = top + 60;  
  89.             }  
  90.         }  
  91.   
  92.         void panel_Click(object sender, EventArgs e)  
  93.         {  
  94.             MessageBox.Show(" Hi, I am " + (sender as Button).Text);  
  95.         }  
  96.     }  
  97.   
  98.     public class Queue  
  99.     {  
  100.         public List<int> Space = new List<int>();  
  101.   
  102.         // Enqueue Operation for Queue item  
  103.         public void EnQueue(int value)  
  104.         {  
  105.             Space.Add(value);  
  106.         }  
  107.   
  108.         // Dequeue Operation for Queue item  
  109.         public int DeQueue()  
  110.         {  
  111.             if (Space.Count > 0)  
  112.             {  
  113.                 var value = Space[0];  
  114.   
  115.                 for (int i = 0; i < Space.Count - 1; i++)  
  116.                 {  
  117.                     Space[i] = Space[i + 1];  
  118.                 }  
  119.   
  120.                 Space.RemoveAt(Space.Count - 1);  
  121.                 return value;  
  122.             }  
  123.             else  
  124.             {  
  125.   
  126.                 return -1;  
  127.             }  
  128.         }  
  129.     }  
  130. }  
Operations Example

Push an item onto the stack, for example “11”; it will be stacked as the very first element in the stack.

push 11 item

Now insert the next item onto the stack. For example 12 is pushed onto the stack.

push 12 item

Now insert an item with the same element. For example when inserting an item “13” it will create a queue and provide you the support of the Queue operations.

Enqueue item 13

Now push another element onto the stack, for example an item 14 is pushed onto the stack as a new stack element.

push item 15

Now “15” is a new stack element.

push item 15

And “16” is pushed onto the stack.

push item 16

Now try to insert “17”, “18”, “19”, “20” with “16” and it forms a new queue and is stored in the same stack element.

enqueue 1718f

Let us now see what happens when doing a Dequeue operation with this stack. It is removing the first element inserted with the current stack element.

dequeue performed

Again doing the dequeue the first element is removed.

dequeue first element

Let us check what happened when doing the Pop operation of the stack. Yes it will pop all there items present in the current queue element.

poping item 19 20 18

After doing the pop operation of the Stack two times, “15” and “14” are popped out.

pop 15 and 14

It will show an empty message when doing the dequeue three times when a stack queue element contains two items.

dequeue last element

Advantages
  • Provide an additional meaningful operation like Enqueue and Dequeue for a stack.
  • Provided a structure more advanced than the existing classic structure to access the data in a more efficient manner.
  • A single structure can behave like a stack or a queue.

Conclusion

Hence this Stacked queue provides the combined capabilites of both structures. That would help us to access the data in a fine way for proper memory allocation of the data.