[STACK] Design a stack which performs middle element operations in O(1) time
20 January, 2014 - 12 min read
Problem:
Design a dynamic stack which would perform following operations in O(1) time.
1.Push
2.Pop
3.Find middle
4.Delete middle
Solution:
Since the stack's size is not limited we can choose a linked list or preferably double linkedlist to store and retireve the elements of stack. Advantage of using doubly linked list is deletion of middle element would be easy. So, if we uve a doubly linked list, insertion(push()) would be done in O(1) time by keeping track of last node. Pop(0 is also can be done in the same way as we are aware of what the last node is. To find the mid element we use a variable which keeps track of middle element and gets updated during insertions and deletions of elements from stack. The same would be updated during deletion of middle element based on stack size. We maintain a flag that would help in assessing middle element behavior.
Code:
1: #include <iostream>
2:
3: using namespace std;
4:
5: typedef struct DoublyLinkedListNode {
6: int Data;
7: DoublyLinkedListNode *Next;
8: DoublyLinkedListNode *Prev;
9: DoublyLinkedListNode(int n) {
10: Data = n;
11: Next = NULL;
12: Prev = NULL;
13: }
14: } DLstack;
15:
16: class Stack {
17: public:
18: Stack ( ) ;
19: ~Stack ( ) ;
20: int Pop ( ) ;
21: void Push ( int num ) ;
22: int Mid ( ) ;
23: void PopMid ( ) ;
24: void Display ( ) ;
25: bool isEmpty ( ) ;
26: private:
27: int top;
28: DLstack *stack;
29: DLstack *midNode; //Keeps track of middle element
30: DLstack *lastNode;
31: bool midFlag; //To check the behaviour of Mid Element
32: };
33:
34: Stack::Stack() {
35: stack = NULL;
36: top = 0;
37: midNode = NULL;
38: lastNode = NULL;
39: midFlag = false;
40: }
41: Stack::~Stack() {
42: while( stack ) {
43: DLstack* temp = stack;
44: stack = stack->Next;
45: delete temp;
46: }
47: }
48: void Stack::Push(int n) {
49: DLstack *newNode = new DLstack(n);
50: if( !stack ) { // Stack is Empty
51: stack = newNode;
52: midNode = newNode;
53: lastNode = newNode;
54: midFlag = true;
55: }
56: else {
57: lastNode->Next = newNode;
58: newNode->Prev = lastNode;
59: lastNode = newNode;
60: //Update the Mid Element Node
61: midFlag = !midFlag;
62: if(midFlag)
63: midNode = midNode->Next;
64: }
65: top++;
66: }
67: int Stack::Pop() {
68: int nRet=0;
69: DLstack *temp = lastNode;
70: lastNode = lastNode->Prev;
71: if(lastNode)
72: lastNode->Next = NULL;
73: nRet = temp->Data;
74: delete temp;
75:
76: top--;
77: //Update the Mid Element Node
78: midFlag = !midFlag;
79: if(midFlag)
80: midNode = midNode->Prev;
81:
82: return nRet;
83: }
84: int Stack::Mid() {
85: return midNode->Data;
86: }
87: void Stack::PopMid() {
88: if( midNode ) {
89: DLstack *temp = midNode;
90: if( midNode->Prev )
91: midNode = midNode->Prev;
92:
93: midNode->Next = temp->Next;
94: temp->Next->Prev = midNode;
95: delete temp;
96:
97: midFlag = !midFlag;
98: if(midFlag)
99: midNode = midNode->Next;
100:
101: top--;
102: }
103: }
104: void Stack::Display() {
105: DLstack* temp = stack;
106: while( temp ) {
107: cout<<temp->Data;
108: temp = temp->Next;
109: (temp!=NULL)?cout<<"<=>":cout<<"\n";
110: }
111: }
112: bool Stack::isEmpty() {
113: if( NULL == stack )
114: return true;
115: return false;
116: }
117:
118: int main(int argc, char* argv[]) {
119: Stack s;
120: int ch;
121: for(int i=1;i<10;i++)
122: s.Push(i);
123:
124: do{
125: cout<<"1.Push"<<endl;
126: cout<<"2.Pop"<<endl;
127: cout<<"3.Display stack"<<endl;
128: cout<<"4.Display mid"<<endl;
129: cout<<"5.Delete mid"<<endl;
130: cout<<"6.Exit "<<endl;
131: cout<<"Select the operations on stack:";
132: cin>>ch;
133:
134: switch(ch){
135: case 1:
136: int n;
137: cout<<"Enter element to insert";
138: cin>>n;
139: s.Push(n);
140: break;
141: case 2:
142: if(s.isEmpty())
143: cout<<"Sorry, stack is empty"<<endl;
144: else
145: cout<<"Popped element"<<s.Pop()<<endl;
146: break;
147: case 3:
148: if(s.isEmpty())
149: cout<<"Sorry, stack is empty\n";
150: else
151: s.Display();
152: break;
153: case 4:
154: if(s.isEmpty())
155: cout<<"Sorry, stack is empty\n";
156: else
157: cout<<"Mid element is "<<s.Mid()<<endl;
158: break;
159: case 5:
160: if(s.isEmpty())
161: cout<<"Sorry, stack is empty\n";
162: else
163: s.PopMid();
164: break;
165: default:
166: if(ch!=6)
167: cout<<"Invalid choice"<<endl;
168: break;
169: }
170: }while(ch != 6);
171:
172: return 0;
173: }