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.
#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);
};
#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