The Circular Stack, An Advance in Data Structure

Introduction

I was wondering why there is no possibility for a circular structure in a stack. But I wish to break this impossible thing. So I began to research to make this possible and something happened, The Circular Stack. I hope this tour on circular stack will be a great fun on the renovation of data structure.

The Circular Stack

My guess is that you are curios about what a circular stack actually does. It is just simply a dual stack. Confusing? Let me explain more that a circular stack has a super-power on the push and pop of the elements in both sides, I mean the front and back (element should pop at the side where it was actually pushed). Imagine the operation will flow as a circular queue but without compromising the stack behavior.
The CircularStack
In our proposed structure since a circular stack actually contains a single collection that then acts as two stacks by the name Front Stack and Back Stack. Which means that the array stack occupies the entire front stack or the back stack or any composition of both stacks.
back Stack Items
Properties

    Space: The storage space
    Root: The first element of the front stack
    Peak: The item in the front stack that is about to pop
    Deep: The item in the back stack that is about to pop
Operations
    PushFront: Push an item onto the front stack that may be a top side
    PushBack: Push an item onto back stack that may be the other side
    PopFront: Pop an item from the front stack
    PopBack: Pop an item from the back stack

Algorithm

Function Push Front:

if the Root is less than SpaceLength and Deep is less than SpaceLength

Then loop up to before Deep

Shift item to one place ahead

Place item on top

Increament Root and Deep

else PrintMessage : Full

Function Push Back

if the Root is less than SpaceLength and Deep is less than SpaceLength

Then Place the item in the Space at Deep

Increament Root and Deep

Else PrintMessage : Full

Function Pop Front

if
Deep is greater than -1 and Root is not equal to -1

Top item as popped item of

Loop up to Deep element

Place space element one step before

Empty deep space element

Decrement
Deep and root

return
popedItem

else if Deep - 1 is not equal to Root

Then PrintMessage : FrontEmpty

else PrintMessage :Empty

return null

Function Pop Back

if
Deep -1 less than SpaceLength And Deep -1 greater than Root

Deep item as poped items

Empty space at deep

Decrement deep

return popedItem

else if Root equals -1

Then PrintMessage :Empty

else PrintMessage : BackEmpty

return null

Code snippet

  1. namespace TheCircularStack  
  2. {  
  3.     public class CircluarStack  
  4.     {  
  5.         public int[] Space = new int[5];  
  6.   
  7.         public int Root =-1, Peak = -1, Deep = 0;  
  8.   
  9.         public string Message = string.Empty;  
  10.   
  11.   
  12.         public void PrintMessage(string message)  
  13.         {  
  14.             switch(message)  
  15.             {  
  16.                 case  "Full":  
  17.                     Message = "Stack Full";  
  18.                     break;  
  19.                 case "FrontEmpty":  
  20.                     Message = "Stack Empty At Front";  
  21.                     break;  
  22.                 case "BackEmpty":  
  23.                     Message = "Stack Empty At Back";  
  24.                     break;  
  25.                 case "Empty":  
  26.                     Message = "Oops! Stack Empty";  
  27.                     break;  
  28.   
  29.             }  
  30.         }  
  31.   
  32.         /// <summary>  
  33.         /// Push Item in Front  
  34.         /// </summary>  
  35.         /// <param name="item"></param>  
  36.         public void PushFront(int item)  
  37.         {  
  38.             Message = string.Empty;  
  39.   
  40.             if (Root < Space.Length && Deep < Space.Length)  
  41.             {  
  42.                 for (int i = Deep - 1; i >= 0; i--)  
  43.                 {  
  44.                     Space[i + 1] = Space[i];  
  45.                 }  
  46.                 Space[0] = item;  
  47.                 Root++;  
  48.                 Deep++;  
  49.             }  
  50.             else  
  51.             {  
  52.                 PrintMessage("Full");  
  53.             }  
  54.   
  55.         }     
  56.   
  57.         /// <summary>  
  58.         /// Push Item in Back  
  59.         /// </summary>  
  60.         /// <param name="item"></param>  
  61.         public void PushBack(int item)  
  62.         {  
  63.             Message = string.Empty;  
  64.   
  65.             if(Root == Deep)  
  66.             {  
  67.                 Deep++;  
  68.             }  
  69.   
  70.             if (Root < Space.Length && Deep < Space.Length)  
  71.             {  
  72.                 Space[Deep] = item;  
  73.                 Deep++;  
  74.             }  
  75.             else  
  76.             {  
  77.                 PrintMessage("Full");  
  78.             }  
  79.   
  80.         }  
  81.   
  82.         /// <summary>  
  83.         /// Pop Item In Front  
  84.         /// </summary>  
  85.         /// <returns></returns>  
  86.         public int PopFront()  
  87.         {  
  88.             Message = string.Empty;  
  89.   
  90.             if ( Deep > -1 &&  Root != -1)  
  91.             {  
  92.                 var popedItem = Space[0];  
  93.                 for (int i = 0; i < Deep-1; i++)  
  94.                 {  
  95.                     Space[i] = Space[i + 1];  
  96.                 }  
  97.   
  98.                 Space[Deep-1] = 0;  
  99.   
  100.                 Root--;  
  101.                 Deep--;  
  102.   
  103.                 return popedItem;  
  104.             }  
  105.             else  
  106.             {  
  107.                 if (Deep - 1 != Root)  
  108.                 {  
  109.                     PrintMessage("FrontEmpty");  
  110.                 }  
  111.                 else  
  112.                 {  
  113.                     PrintMessage("Empty");  
  114.                 }  
  115.   
  116.                 return -1;  
  117.             }  
  118.         }  
  119.   
  120.         /// <summary>  
  121.         /// Pop Item in Back  
  122.         /// </summary>  
  123.         /// <returns></returns>  
  124.         public int PopBack()  
  125.         {  
  126.             Message = string.Empty;  
  127.   
  128.             if (Deep -1 < Space.Length &&  Deep -1 > Root)  
  129.             {  
  130.                 var popedItem = Space[Deep-1];  
  131.                 Space[Deep -1] = 0;  
  132.                 Deep--;  
  133.                 return popedItem;  
  134.             }  
  135.             else  
  136.             {  
  137.                 if (Root == -1)  
  138.                 {  
  139.                     PrintMessage("Empty");  
  140.                 }  
  141.                 else  
  142.                 {  
  143.                     PrintMessage("BackEmpty");  
  144.                 }  
  145.               
  146.                 return -1;  
  147.             }  
  148.         }    
  149.   
  150.     }  
  151. }  
push operations

pop operation
Conclusion

Since the proposed circular stack structure can allocate and access the pushed item over the circular structure and provide a two-way assessment on a single stack.


Similar Articles