Create a data structure twoStacks that represents two stacks. Implementation of twoStacksshould use only one array, i.e., both stacks should use the same array for storing elements.
Method 2 (A space efficient implementation)
The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.
The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.
class
twoStacks
{
int
*arr;
int
size;
int
top1, top2;
void
push1(
int
x)
{
// There is at least one empty space for new element
if
(top1 < top2 - 1)
{
top1++;
arr[top1] = x;
}
else
{
cout <<
"Stack Overflow"
;
exit
(1);
}
}
// Method to push an element x to stack2
void
push2(
int
x)
{
// There is at least one empty space for new element
if
(top1 < top2 - 1)
{
top2--;
arr[top2] = x;
}
else
{
cout <<
"Stack Overflow"
;
exit
(1);
}
}
// Method to pop an element from first stack
int
pop1()
{
if
(top1 >= 0 )
{
int
x = arr[top1];
top1--;
return
x;
}
else
{
cout <<
"Stack UnderFlow"
;
exit
(1);
}
}
// Method to pop an element from second stack
int
pop2()
{
if
(top2 < size)
{
int
x = arr[top2];
top2++;
return
x;
}
else
{
cout <<
"Stack UnderFlow"
;
exit
(1);
}
}
};