Design a stack which performs middle element operations in O(1) time.

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:

// StackWithOOfOne.cpp : Defines the entry point for the console application.
// Written by __Sreeni__ on 06/12/2013 11:26AM
 
#include <iostream>
 
using namespace std;
 
class llist
{
public:
    int data;
    llist *pNext;
    llist *pPrev;
    llist(int n)
    {
        data = n;
        pNext = NULL;
        pPrev = NULL;
    }
};
 
class Stack
{
private:
    int top;
    llist *list;
    llist *midNodeOfList;
    llist *lastNodeOfList;
    bool flagSet;
public:
    Stack()
    {
        list = NULL;
        top = 0;
        midNodeOfList = NULL;
        lastNodeOfList = NULL;
        flagSet = false;
    }
    ~Stack()
    {
        while(list != NULL)
        {
            llist* temp = list;
            list = list->pNext;
            delete temp;
        }
    }
    void push(int n)
    {
        llist *newNode = new llist(n);
        if(list == NULL)
        {
            list = newNode;
            midNodeOfList = newNode;
            lastNodeOfList = newNode;
            flagSet = true;
        }
        else
        {
            lastNodeOfList->pNext = newNode;
            newNode->pPrev = lastNodeOfList;
            lastNodeOfList = newNode;
            flagSet = !flagSet;
            if(flagSet)
            {
                midNodeOfList = midNodeOfList->pNext;
            }
        } 
        top++;
    }
    int pop()
    {
        int nRet=0;
        llist *temp = lastNodeOfList;
        lastNodeOfList = lastNodeOfList->pPrev;
        if(lastNodeOfList)lastNodeOfList->pNext = NULL;
        nRet = temp->data;
        delete temp;
 
        top--;
 
        flagSet = !flagSet;
        if(flagSet)
        {
            midNodeOfList = midNodeOfList->pPrev;
        }
        return nRet;
    }
    int mid()
    {
        return midNodeOfList->data;
    }
    void deleteMid()
    {
        if(midNodeOfList != NULL)
        {
            llist *temp = midNodeOfList;
            if(midNodeOfList->pPrev != NULL)
            {
                midNodeOfList = midNodeOfList->pPrev;
            }
            midNodeOfList->pNext = temp->pNext;
            temp->pNext->pPrev = midNodeOfList;
            delete temp;
            flagSet = !flagSet;
            if(flagSet)
            {
                midNodeOfList = midNodeOfList->pNext;
            }
            top--;
        }
    }
    void display()
    {
        llist* temp = list;
        while(temp != NULL)
        {
            cout<<temp->data;
            temp = temp->pNext;
            (temp!=NULL)?cout<<"<=>":cout<<"\n";
        }
    }
    bool isEmpty()
    {
        if(list == NULL)
        {
            return true;
        }
        return false;
    }
};
 
int main(int argc, char* argv[])
{
    Stack s;
    int ch;
    for(int i=1;i<10;i++)
        s.push(i);
 
    do{
        cout<<"1.Push"<<endl;
        cout<<"2.Pop"<<endl;
        cout<<"3.Display stack"<<endl;
        cout<<"4.Display mid"<<endl;
        cout<<"5.Delete mid"<<endl;
        cout<<"6.Exit "<<endl;
        cout<<"Select the operations on stack:";
        cin>>ch;
        
        switch(ch){
        case 1:
            int n;
            cout<<"Enter element to insert";
            cin>>n;
            s.push(n);
            break;
        case 2:
            if(s.isEmpty())
                cout<<"Sorry, stack is empty"<<endl;
            else
                cout<<"Popped element"<<s.pop()<<endl;
            break;
        case 3:
            if(s.isEmpty())
                cout<<"Sorry, stack is empty\n";
            else
                s.display();
            break;
        case 4:
            if(s.isEmpty())
                cout<<"Sorry, stack is empty\n";
            else
                cout<<"Mid element is "<<s.mid()<<endl;
            break;
        case 5:
            if(s.isEmpty())
                cout<<"Sorry, stack is empty\n";
            else
                s.deleteMid();
            break;
        default:
            if(ch!=6)
                cout<<"Invalid choice"<<endl;
            break;
        }
    }while(ch != 6);
 
    return 0;
}