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;
}

 

About Author

Author Image
Pushpandra Kumar

Pushpender has experience in Core Java, C & C++. His hobbies are learning new technologies and listening music.

Request for Proposal

Name is required

Comment is required

Sending message..