   # How can we implement two stack in an array?

+1 vote
68 views
How can we implement two stack in an array? posted Aug 11, 2014

Just an algo -
1. start two stacks from two extreme corners of array.
2. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0.
3. stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1).
4. Both stacks grow (or shrink) in opposite direction.

How to check overflow
Check space between top elements of the two stacks. answer Aug 12, 2014
#include<iostream>
#include<stdlib.h>

using namespace std;

class twoStacks
{
int *array;
int size;
int top_stack1, top_stack2;

public:
twoStacks(int n)
{
size = n;
array = new int[n];
top_stack1 = -1;
top_stack2 = size;
}

void push1(int x)
{
// check for one empty space
if (top_stack1 < top_stack2 - 1)
{
top_stack1++;
array[top_stack1] = x;
}
else
{
cout << "Overflow";
exit(1);
}
}

void push2(int x)
{
// check for one empty space
if (top_stack1 < top_stack2 - 1)
{
top_stack2--;
array[top_stack2] = x;
}
else
{
cout << "Overflow";
exit(1);
}
}

int pop1()
{
if (top_stack1 >= 0 )
{
int x = array[top_stack1];
top_stack1--;
return x;
}
else
{
cout << "Underflow";
exit(1);
}
}

int pop2()
{
if (top_stack2 < size)
{
int x = array[top_stack2];
top_stack2++;
return x;
}
else
{
cout << "Underflow";
exit(1);
}
}
};
Similar Questions