Let's start by understanding the problem statement for this task.
You are given two stacks, and you need to implement both stacks in the same array.
Hint:
One may think about how to implement two stacks in the same array, this can be done easily when we think that both the stacks have their insertion operations from both ends of the array and the number of elements to be pushed into the array should depend upon the size of the array.
Quick Think:
While implementing two stacks in the same array, we need to check the following conditions:-
- There should be a difference of at least one index while inserting the stack elements into the array so that the elements from the different stacks, do not overwrite each other and prevent data loss.
- While popping the elements from the stack, the popping should be done from the last index where the insertion of the element is finished to make the stack work on the principle of the LIFO rule.
- The implementation will work on the following functions, they are the pop function and the push function.
Algorithm:
To implement the stack with the use of an array structure, we will ponder over the following points:-
Step1: Create a class name of your choice define the necessary variables such as the array size, the top_1 of the first stack, the top_2 of the second stack, the variable which will contain the element to be pushed into the stack, and the array.
Step2: Now create a public parameterized constructor with an argument as the total size of the array which will be called automatically and initialize all the variables such as the size of the array, the total size of the array the top_1 index of the stack_1 as -1 and the top_2 index of the stack_2 as size.
Step3: Define all the functions inside the same class along with their data types such as the push_1 function for pushing into the stack1, the push_2 function for pushing into the stack_2, the pop1 function for popping out the data value from stack_1, pop_2 function for popping out the data value from the stack_2.
Step4: Create the function push_1 with the argument as the data value to be pushed into stack_1, and check for the size of the stack_1, if the top_1 value is greater than the value of top_2 - 1 then print “stack overflow” else go to step 5.
Step5: Increment the top_1 index by one and push the data value to the array-based stack.
Step6: Create a function push_2 with the argument as the data value to be pushed into stack_2, and check for the size of the stack_2, if the top_1 value is greater than the value of top_2 - 1 then print “stack overflow” else go to step 7.
Step7: Decrement the top_2 value by one and push the data value to the array-based stack from the back of the array.
Step8: Create a function pop_1 with no argument, check for the current index of the variable top_1 if it is less than 0 then print “stack underflow” else go to step 9.
Step9: Store the current stack element to be popped in a variable decrement the top_1 variable by one and return the popped-out data value.
Step10: Create a function pop_2 with no argument, check for the current index of the variable top_2 if it is greater than the total size of the array then print “stack underflow” else go to step 11.
Step11: Store the current stack element to be popped in a variable, increment the top_2 variable by one, and return the popped-out data value.
Implementation Of The Above Algorithm:
Now let's see the implementation of the above algorithm,
#include <bits/stdc++.h>
using namespace std;
/*Class function to initialize variables and functions. */
class stack_fun
{
/*Variables. */
int size;
int top_1, top_2;
int *arr;
int x;
/*Parameterized Constructor. */
public: stack_fun(int n)
{
size = n;
arr = new int[size];
top_1 = -1;
top_2 = size;
}
/*Functions. */
void push_1(int x);
void push_2(int x);
int pop_1();
int pop_2();
};
/*Push Function For Stack_1. */
void stack_fun::push_1(int x)
{
if (top_1 < top_2 - 1)
{
top_1++;
arr[top_1] = x;
}
else
cout << "Stack Overflow" << endl;
}
/*Push Function For Stack_2. */
void stack_fun::push_2(int x)
{
if (top_1 < top_2 - 1)
{
top_2--;
arr[top_2] = x;
}
else
cout << "Stack Overflow" << endl;
}
/*Pop Function For stack_1. */
int stack_fun::pop_1()
{
if (top_1 >= 0)
{
int y = arr[top_1];
top_1--;
return y;
}
else
cout << "Stack Underflow" << endl;
}
/*Pop Function For stack_2. */
int stack_fun::pop_2()
{
if (top_2 < size)
{
int y = arr[top_2];
top_2++;
return y;
}
else
cout << "Stack Underflow" << endl;
}
/*Driver function to check stack class. */
int main()
{
stack_fun ts(5);
ts.push_1(50);
ts.push_2(11);
ts.push_2(23);
ts.push_1(67);
ts.push_2(78);
cout << "Popped element from stack_1 is " << ts.pop_1();
ts.push_2(56);
cout << "\n Popped element from stack_2 is " << ts.pop_2();
return 0;
}
The running time complexity of the above algorithm is: O(1).
The output of the above algorithm is:
Popped element from stack_1 is 67.
Popped element from stack_2 is 56.
Explanation Of The Above Algorithm:
The above algorithm will work in the following way:-
Let us consider the same example as given in the above code
- At first, the push function is called with the data element to be pushed into the
stack_1 as 50 and the element is pushed into the stack_1 and the top_1 index value is incremented by one i.e., the new value is 0 as shown in the diagram above.
- Now the push function is called with the data element to be pushed into the
stack_2 as 11 and the element is pushed into the stack_2 and the top_2 index value is decremented by one, i.e., the new value is 4 as shown in the diagram above.
- Now the push function is called with the data element to be pushed into the
stack_2 as 23 and the element is pushed into the stack_2 and the top_2 index value is decremented by one, i.e., the new value is 3 as shown in the diagram above.
- Now the push function is called with the data element to be pushed into the
stack_1 as 67 and the element is pushed into the stack_1 and the top_1 index value is incremented by one, i.e., the new value is 1 as shown in the diagram above.
- Now the push function is called with the data element to be pushed into the
stack_2 as 78 and the element is pushed into the stack_2 and the top_2 index value is decremented by one, i.e., the new value is 2 as shown in the diagram above.
- Now the last index of top_1 is at index value 1, so the data from index 1 is popped out, and the index value is decremented by one, i.e., the new value is 0 as shown in the diagram above.
- Now again the push function is called with the data element to be pushed into the
stack_2 as 56 and the element is pushed into the stack_2 and the top_2 index value is decremented by one, i.e., the new value is 1 as shown in the diagram above.
- Now the last index of
top_2 is at index value 1, so the data from index 1 is popped out, and the index value is incremented by one, i.e., the new value is 2 as shown in the diagram above.
