Double Stack Tutorial.

What is Double Stack?

We can also maintain two stacks in one array. This type of implementation is known as double stack. In this implementation both stacks grow in opposite directions. One from lower index to higher index and second from higher to lower index.

double stack - Data Structure Tutorial

TOP1 initially is -1 and TOP2 initially is MAX.

Declaration of Double Stack

    #define MAX 5

    //Declaration of Double Stack
    typedef struct
    {
	    int top1;
	    int top2;
	    int ele[MAX];
    }DStack;
    #define MAX 5

    //Declaration of Double Stack
    class DStack
    {
	    private:
		    int top1;
		    int top2;
		    int ele[MAX];

	    public:
		    DStack();
		    void pushA(int  item);
		    void pushB(int  item);
		    int  popA (int *item); 
		    int  popB (int *item);

    }; 

Complete program to implement Double Stack

    #include<stdio.h>
    #define MAX 5

    //Declaration of Double Stack
    typedef struct
    {
	    int top1;
	    int top2;
	    int ele[MAX];
    }DStack; 

    //Initialization of Double Stack
    void init( DStack *s )
    {
	    s->top1 = -1;
	    s->top2 = MAX;
    }

    //Push Operation on Stack1
    void pushA( DStack *s, int item )
    {
	    if( s->top2 == s->top1 + 1 )
	    {
		    printf("\nStack Overflow Stack1");
		    return;
	    }

	    s->top1++;
	    s->ele[s->top1] = item;

	    printf("\nInserted item in Stack1 : %d",item);	
    }

    //Push Operation on Stack2
    void pushB( DStack *s, int item )
    {
	    if( s->top2 == s->top1 + 1 )
	    {
		    printf("\nStack Overflow Stack2");
		    return;
	    }

	    s->top2--;
	    s->ele[s->top2] = item;

	    printf("\nInserted item in Stack2 : %d",item);	
    }

    //Pop Operation on Stack1
    int popA( DStack *s, int *item )
    {
	    if( s->top1 == -1 )
	    {
		    printf("\nStack Underflow Stack1");
		    return -1;
	    }

	    *item = s->ele[s->top1--];
	    return 0;
    }

    //Pop Operation on Stack2
    int popB( DStack *s, int *item )
    {
	    if( s->top2 == MAX )
	    {
		    printf("\nStack Underflow Stack2");
		    return -1;
	    }

	    *item = s->ele[s->top2++];
	    return 0;
    }


    int main()
    { 
	    int item = 0;

	    DStack s;

	    init(&s);

	    pushA( &s, 10);
	    pushA( &s, 20);
	    pushA( &s, 30);
	    pushB( &s, 40);
	    pushB( &s, 50);
	    pushB( &s, 60);


	    if( popA(&s, &item) == 0 )
		    printf("\nDeleted item From Stack1 : %d",item);
	    if( popA(&s, &item) == 0 )
		    printf("\nDeleted item From Stack1 : %d",item);
	    if( popA(&s, &item) == 0 )
		    printf("\nDeleted item From Stack1 : %d",item);
	    if( popB(&s, &item) == 0 )
		    printf("\nDeleted item From Stack2 : %d",item);
	    if( popB(&s, &item) == 0 )
		    printf("\nDeleted item From Stack2 : %d",item);
	    if( popB(&s, &item) == 0 )
		    printf("\nDeleted item From Stack2 : %d",item);

	    printf("\n");
	    return 0;
    }
    Inserted item in Stack1 : 10
    Inserted item in Stack1 : 20
    Inserted item in Stack1 : 30
    Inserted item in Stack2 : 40
    Inserted item in Stack2 : 50
    Stack Overflow Stack2
    Deleted item From Stack1 : 30
    Deleted item From Stack1 : 20
    Deleted item From Stack1 : 10
    Deleted item From Stack2 : 50
    Deleted item From Stack2 : 40
    Stack Underflow Stack2
    #include <iostream>
    using namespace std;
    #define MAX 5

    //Declaration of Double Stack
    class DStack
    {
	    private:
		    int top1;
		    int top2;
		    int ele[MAX];

	    public:
		    DStack();
		    void pushA(int  item);
		    void pushB(int  item);
		    int  popA (int *item); 
		    int  popB (int *item);

    }; 

    //Initialization of Double Stack
    DStack::DStack()
    {
	    top1 = -1;
	    top2 = MAX;
    }

    //Push Operation on Stack1
    void DStack::pushA( int item )
    {
	    if( top2 == top1 + 1 )
	    {
		    cout<<"\nStack Overflow Stack1";
		    return;
	    }

	    top1++;
	    ele[top1] = item;

	    cout<<"\nInserted item in Stack1 : "<< item;	
    }

    //Push Operation on Stack2
    void DStack::pushB( int item )
    {
	    if( top2 == top1 + 1 )
	    {
		    cout<<"\nStack Overflow Stack2";
		    return;
	    }

	    top2--;
	    ele[top2] = item;

	    cout<<"\nInserted item in Stack2 : "<< item;	
    }

    //Pop Operation on Stack1
    int DStack::popA( int *item )
    {
	    if( top1 == -1 )
	    {
		    cout<<"\nStack Underflow Stack1";
		    return -1;
	    }

	    *item = ele[top1--];
	    return 0;
    }

    //Pop Operation on Stack2
    int DStack::popB( int *item )
    {
	    if( top2 == MAX )
	    {
		    cout<<"\nStack Underflow Stack2";
		    return -1;
	    }

	    *item = ele[top2++];
	    return 0;
    }


    int main()
    { 
	    int item = 0;

	    DStack s = DStack();

	    s.pushA(10);
	    s.pushA(20);
	    s.pushA(30);

	    s.pushB(40);
	    s.pushB(50);
	    s.pushB(60);


	    if( s.popA(&item) == 0 )
		    cout<<"\nDeleted item From Stack1 : "<< item;
	    if( s.popA(&item) == 0 )
		    cout<<"\nDeleted item From Stack1 : "<< item;
	    if( s.popA(&item) == 0 )
		    cout<<"\nDeleted item From Stack1 : "<< item;

	    if( s.popB(&item) == 0 )
		    cout<<"\nDeleted item From Stack2 : "<< item;
	    if( s.popB(&item) == 0 )
		    cout<<"\nDeleted item From Stack2 : "<< item;
	    if( s.popB(&item) == 0 )
		    cout<<"\nDeleted item From Stack2 : "<< item;

	    cout<< endl;

	    return 0;
    }
    Inserted item in Stack1 : 10
    Inserted item in Stack1 : 20
    Inserted item in Stack1 : 30
    Inserted item in Stack2 : 40
    Inserted item in Stack2 : 50
    Stack Overflow Stack2
    Deleted item From Stack1 : 30
    Deleted item From Stack1 : 20
    Deleted item From Stack1 : 10
    Deleted item From Stack2 : 50
    Deleted item From Stack2 : 40
    Stack Underflow Stack2