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.

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.

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. }

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.