by Stack is a data structure used for storing collection of data where order in which data is arriving is important. In Stack, insertion and deletion both happened from the same end which is known as “Top”.
The data which is arrived last will be deleted first in Stack. This data ordering is called as Last in First out or LIFO. Before going ahead have a look into Stack basics and Generic Stack Implementation.
Two Stacks in a Single Array
In this case, we need to define two stacks which are using same array. This method can be very useful from space optimization point of view in the software as this method has a potential to provide better memory utilization. Here we are going to look into the Stack definition which are going to use the Single array.
Algorithm
- Define two indexes one pointing at the left end and other pointing at the right end.
- Left index will be used for One Stack while Right index will be used for Second Stack.
- If element needs to push into First Stack then using left index data will be pushed and index will be incremented by 1.
- If element needs to push into Second Stack then using right index data will be pushed and index will be decremented by 1.
Let’s look into the below example to make it more clear.
As shown in above image, First Stack grows from Left to Rigth whereas Second Stack grows from Right to Left.
Few of the functions used below are explained in Stack Implementation. Refer those before going ahead.
Let’s look into the sample code.
class DoubleStack
{
private:
int size;
int top_left;
int top_right;
int* elements;
public:
DoubleStack (int sz): size (sz),
top_left (0),
top_right (sz - 1)
{
elements = new int[size] ();
if (!elements)
{
cout << "Stack initialization failed" << endl;
}
}
~DoubleStack ()
{
delete []elements;
}
bool push (int value, bool first)
{
if (top_left >= top_right)
{
cout << "Stack full" << endl;
return false;
}
if (first)
{
elements[top_left++] = value;
return true;
}
elements[top_right--] = value;
return true;
}
int pop (bool first)
{
if (first)
{
if (!top_left)
{
cout << "Stack is empty" << endl;
return -1;
}
return elements[--top_left];
}
if (top_right == size - 1)
{
cout << "Stack is empty" << endl;
return -1;
}
return elements[++top_right];
}
bool isEmpty (bool first)
{
if (first)
{
return !top_left;
}
return (top_right == (size - 1));
}
int entries (bool first)
{
if (first)
return top_left;
return (size - top_right);
}
void printContent ()
{
cout << "First Stack contents: " ;
for (int i = 0; i < top_left; i++)
cout << elements[i] << " ";
cout << endl;
cout << "Second Stack contents: " ;
for (int i = size - 1; i > top_right; i--)
cout << elements[i] << " ";
cout << endl;
}
};
Let’s define a main function to use above methods.
int main ()
{
DoubleStack d(10);
d.push (10, true);
d.push (20, true);
d.push (30, false);
d.push (40, true);
d.push (50, false);
d.push (60, true);
d.push (70, true);
d.printContent ();
d.push (100, true);
d.push (200, false);
d.push (300, false);
d.push (400, true);
d.printContent ();
d.pop(true);
d.pop(false);
d.printContent ();
d.push (300, false);
d.push (400, true);
d.printContent ();
}
Let’s analyze the output of this main function.
First Stack contents: 10 20 40 60 70
Second Stack contents: 30 50
Stack full
Stack full
First Stack contents: 10 20 40 60 70 100
Second Stack contents: 30 50 200
First Stack contents: 10 20 40 60 70
Second Stack contents: 30 50
First Stack contents: 10 20 40 60 70 400
Second Stack contents: 30 50 300
