Although Stack Data Structure is already defined in C++. But for the sake of learning, we will define our own Stack class and define all the methods there.
#include <iostream>
using namespace std;
static const int SIZE = 10;
class ArrStack {
public :
int stackArray[SIZE];
int tp = -1;
ArrStack(int size) {
}
bool push(int i) {
if (size() == SIZE) {
cout << "Stack Overflow" << endl;
return false;
}
else {
stackArray[++tp] = i;
return true;
}
}
int pop() {
int element;
if (isEmpty()) {
cout << "Stack is Empty" << endl;
return -1;
}
else {
element = stackArray[tp];
stackArray[tp--] = 0;
cout << "The element " << element << " is popped out of the Stack" << endl;
return element;
}
}
int top() {
if (isEmpty()) {
cout << "Stack is Empty" << endl;
return -1;
} else {
cout << "The top element is " << stackArray[tp] << endl;
return stackArray[tp];
}
}
int size() {
return (tp+1);
}
bool isEmpty() {
return (tp<0);
}
};
int main() {
ArrStack arrStack(SIZE);
arrStack.push(10);
arrStack.push(20);
arrStack.push(30);
arrStack.top();
arrStack.pop();
arrStack.pop();
arrStack.pop();
}
As we know the most important operations/methods of Stack are Push and Pop. However, there are other methods that we will be using here.
So, we have the below methods :
So, at first, we define the array where we will be storing the elements of the Stack.
int stackArray[SIZE];
Also, we have defined a constant called SIZE where we have defined the size of the array.
static const int SIZE = 10;
And, then we have initialised the variable tp with -1.
int tp = -1;
The variable tp always points to the top element. Initially tp is -1 because it is not pointing to any element yet. When it becomes 0, it should be pointing to the 0th element.
Now, let us go to the main(..) method and see the Stack in action.
So, we have represented the Stack as an Array,
int stackArray[SIZE];
So, initially we have an empty Stack.
Then we try to push the element 10 into the Stack
arrStack.push(10);
So, the push() method is called,
public bool push(int i) {
if (size() == SIZE) {
cout << "Stack Overflow";
return false;
}
else {
stackArray[++tp] = i;
return true;
}
}Now, the push() method calls the size() method to check the size of the Array.
int size() {
return (tp+1);
}The size() method returns tp+1.
And if we see the value of variable tp, it is -1 initially.
So, size() method returns tp+1, i.e. -1+1 = 0.
So, we are back in the push() method with the value 0 returned from size() method.
Now, in the if statement, we find the condition,
if (size() == SIZE)
But in this case size() returned 0 and SIZE is initialised with 10.
So, we come to the else part,
else {
stackArray[++tp] = i;
return true;
}And in the else part we increment the value of the variable tp first. As tp points to the top element.
So, tp is -1 initially. After incrementing it becomes 0.
Now, the below line,
stackArray[++tp] = i;
Inserts the element 10(As i is 10) to the 0th location of the Array stackArray.
Then we try inserting the element 20 using the push(...) method again.
arrStack.push(20);
Similarly, push(...) method is called,
bool push(int i) {
if (size() == SIZE) {
cout << "Stack Overflow";
return false;
}
else {
stackArray[++tp] = i;
return true;
}
}Now the value of i is 20.
Same way as above, the if condition checks, if the total number of elements in the array(Determined by the size() method) is equal to the size of the array.
In this case the total number of elements in the array is just one i.e. 10(And we are going to insert 20). And the size of the array is 10.
So, we come to the else part.
else {
stackArray[++tp] = i;
return true;
}The line in the else part,
stackArray[++tp] = i;
Increments the variable tp first.
The current value of tp is 0. As tp is pointing to the first element.
After incrementing tp, it becomes 1. And in stackArray[1], we insert 20.
And just remember 20 is the top element now. So, tp would be pointing to it.
After that, we try inserting the element 30 using the push(...) method again.
arrStack.push(30);
And, as usual, push(...) method is called and the element 30 is inserted into the Stack.
Next, we try getting the top element of the stack by calling the top(..) mkethod.
arrStack.top();
And as we know the variable tp always points to the top element. So, if we could get the value of the variable tp, we could get the top element.
And exactly, the same thing is done in the top() method.
int top() {
if (isEmpty()) {
cout << "Stack is Empty";
return -1;
} else {
cout << "The top element is " << stackArray[tp];
return stackArray[tp];
}
}In the top() method, we check if the array is empty or not.
if (isEmpty()) {
cout << "Stack is Empty";
return -1;
}And if the array is not empty, we come to the else part. Where the value of the top position is returned.
return stackArray[tp];
Say, for example, the value of tp is 2 currently. So, stackArray[tp] would return 30 as the top element.
Next, we try popping the elements from the Stack. One at a time.
So, when we run the first pop() method.
arrStack.pop();
The pop() method is called.
int pop() {
int element;
if (isEmpty()) {
cout << "Stack is Empty";
return -1;
}
else {
element = stackArray[tp];
stackArray[tp--] = 0;
cout << "The element " << element << " is popped out of the Stack";
return element;
}
}So, as usual we check if the array is empty or not.
if (isEmpty()) {
cout << "Stack is Empty";
return -1;
}Now, if the array is not empty, we come to the else part.
else {
element = stackArray[tp];
stackArray[tp--] = 0;
cout << "The element " << element << " is popped out of the Stack";
return element;
}The operation is quite simple,
We take the current top element in the element variable.
element = stackArray[tp];
i.e.
element = 30.
Then we replace the current top element with 0. And at the same time, reduce the value of tp by 1. So that tp points to the second element.
Similarly, after running pop() method twice,
arrStack.pop(); arrStack.pop();
Both the elements 20 and 10 are popped out of the Stack.
