Design a stack with additional operations on middle element.

Problem: Implement a stack which supports following operations in O(1) -
1) push() which adds an element to the top of stack.
2) pop() which removes an element from top of stack.
3) findMiddle() which returns middle element of the stack.
4) delMiddle() which deletes the middle element.

Solution: Use Doubly Linked List to implement this stack.

Implementation:

struct DLNode
{
       int data;
       DLNode *next;
       DLNode *prev;
       DLNode(int i):data(i), next(0), prev(0){}
};

class Stack
{
public:
       Stack():head(0), mid(0), size(0){}
       void push(int i);
       int pop();
       int findMiddle();
       void delMiddle();
private:
      DLNode *head;
      DLNode *mid;
      int size;
};

void Stack::push(int i)
{
     DLNode *node = new DLNode(i);
     node->next = head;
     node->prev = NULL;
     size += 1;
     if(size == 1)
         mid = node;
     else
     {
         head->prev = node;
         if(size & 1)
                 mid = mid->prev;
     }
     head = node;  
}

int Stack::pop()
{
    if(size == 0)
             return -1;
    DLNode *node = head;
    int retVal = head->data;
    head = head->next;
    if(head)
            head->prev = 0;
    size -= 1;
    if(!(size & 1))
            mid =  mid->next;
    delete node;
    return retVal;
}

int Stack::findMiddle()
{
    int retVal = -1;
    if(size != 0)
           retVal = mid->data;
    return retVal;
}

void Stack::delMiddle()
{
     if(size == 0)
             return;
     DLNode *node = mid;
     if(size == 1)
     {
             mid = 0;
             head = 0;
     }
     --size;
     mid->prev->next = mid->next;
     mid->next->prev = mid->prev;
     if(!(size & 1))
               mid = node->next;
     else
         mid = node->prev;
     delete node;
}