##### 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: }`