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