Creating Two Stacks with Single Array
Posted By : Pushpandra Kumar | 23-May-2018
The stack is an abstract data structure in which elements are added and removed in a LIFO manner i.e, Last In First Out. That is, an element that is last added will be removed first. We consider an example to understand stack. Suppose we have a pile of plates in the hotel, the waiter can access only the plate that is on the top. We can implement this abstract data structure in a number of ways i.e by using arrays or linked list.
But here we are not implementing this rather we will implement two stacks together in a single array in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.
There are two ways to do this:
1. Divide the array into two halves and implement both stacks accordingly but this is not space efficient method. Suppose the first stack reaches its max length i.e, the n/2 and second stack is empty. we have pushed more elements to stack1 it will throw overflow error although we have empty cells in the array. SO this is not space efficient.
2. The idea is to start two stacks from the corner ends and grow them towards each other. If one stack is empty, then still the second stack will be able to grow to the array has empty cells.
Here is the implementation of the code.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class TwoArrayStack{
int* arr;
int size, top1,top2;
public :
TwoArrayStack(int n = 100)
{
arr = new int[n];
size = n;
top1 = -1;
top2 = n;
}
void push1(int x);
void push2(int x);
int pop1();
int pop2();
void printStack1();
void printStack2();
void printCompleteStack(){
for(int i=0;i<size;i++)
{
cout<<arr[i]<<" ";
}
cout<<"\n";
}
};
void TwoArrayStack::push1(int x){
if(top1<top2-1)
{
top1++;
arr[top1]=x;
}
else {
cout<<"Stack Overflow!!!!!!!\n";
}
}
void TwoArrayStack::push2(int x){
if(top1<top2-1){
top2--;
arr[top2]=x;
}
else {
cout<<"Stack Overflow!!!!!!!\n";
}
}
int TwoArrayStack::pop1(){
if(top1>=0)
return arr[top1--];
else return -1;
}
int TwoArrayStack::pop2(){
if(top2<size)
return arr[top2++];
else return -1;
}
void TwoArrayStack::printStack1()
{
for(int i=0;i<=top1;i++)
cout<<arr[i]<<" ";
cout<<"\n";
}
void TwoArrayStack::printStack2()
{
for(int i=size-1;i>=top2;i--)
cout<<arr[i]<<" ";
cout<<"\n";
}
int main()
{
TwoArrayStack ts(10);
ts.push1(4);
ts.push1(3);
ts.push1(5);
ts.push1(12);
ts.push1(14);
ts.push1(15);
ts.push1(16);
ts.printStack1();
ts.push2(40);
ts.push2(31);
ts.push2(34);
ts.push2(37);
ts.push2(398);
ts.printStack2();
ts.printCompleteStack();
return 0;
}
Cookies are important to the proper functioning of a site. To improve your experience, we use cookies to remember log-in details and provide secure log-in, collect statistics to optimize site functionality, and deliver content tailored to your interests. Click Agree and Proceed to accept cookies and go directly to the site or click on View Cookie Settings to see detailed descriptions of the types of cookies and choose whether to accept certain cookies while on the site.
About Author
Pushpandra Kumar
Pushpender has experience in Core Java, C & C++. His hobbies are learning new technologies and listening music.