Hack The Stack
Stack is a data structure that can easily be explained and understood because there are many real-life examples available that you see daily and can easily relate to. The stack can be explained in easy words just imagine a box which is open from the top and anything you want to put inside it can only be done from the top and anything you want to take out that can also be done only from the top the things which are at the top will be removed first and the things at the bottom can only be removed once we remove the things are on the top because the box is only open from the top. Stack also works quite similarly, but it strictly follows the rule that the element at the top will be removed first and the element at the bottom will be removed at the end.
Stack is a linear data structure. Linear data structures are those data structures that store the data in contiguous memory blocks. And Operations performed are in a particular order, and that order can be LIFO.
LIFO — Stands for Last in First Out
Some real-life examples of the stack are:-
1. Imagine the Chapatti’s kept in the chapatti box on the dining table. The chapatti at the top will be removed first and the chapatti kept at the end will be removed at the end.
2. CDs kept in the cd box. Similar to the above example the cd at the top will be taken off first and the last one cannot be until all of them are removed.
3. Stack of books on your study table. The book you read will be kept at the top of the stack for the last time.
4. Plates are kept on the table in the kitchen for washing. Your mom is going to take the dish kept at the top first for washing.
5. Your Clothes arranged in your cupboard also follow the same principle if you want to take the shirt kept at the bottom u first need to take off all the clothes above it.
From the above examples, you can see that only the top side is open and hence the things kept at the top will get the first precedence. And in other words, the things kept at the end will get the last precedence. The below paragraph will give you a much better idea.
Stack is a data structure in which operations can only be performed from one end. The end of the stack is normally called the top and the other end is called the base. The element that is first entered in the stack remains for the longest time in the stack and the element added at the end will be removed first and that is why it is said that it follows a LIFO order. Unlike Queue in which the operations can be performed from both ends. And because the stack follows this order of performing the operations it is a very useful data structure, with lots of real-life applications.
Operations that can be performed on the stack are:-
1. Push: It adds an element to the top of the stack. Before adding any element on the top of the stack we need to check if the stack is full. If the stack is full we cannot add an element to the stack. It is called Stack Overflow.
2. Pop: It removes an element from the top of the stack. Before removing we need to check if the stack is empty. If it is empty we cannot remove any element from the stack. It is called stack Underflow.
3. Peek: It helps us to get the element present in the required index inside the stack.
4. IsEmpty: It returns true if the stack is Empty, Otherwise it returns false.
5. IsFull: It returns true if the stack is Full, Otherwise it returns false.
6. Display: it displays all the elements present inside the stack
The stack can be implemented using Arrays.
Code in C++ using Array :
Define Variable:
Wherever we will use MAX it will replace it with 1000
#define MAX 1000Class Stack:
Declaring a class stack
class stack {};
Data Members:
The variables and functions belonging to the particular class are called its data members.
Declaring the data members and member functions of the class stack, using public access specifiers.
public:int top = -1;int size;int arr[MAX];bool isEmpty();bool isFull();int pop();void push();int peek();void display();
The data members are:
1. Top = -1; Initializing the top as -1.
2. Declaring a size variable that will store the size of the stack.
3. Declaring an array of MAX size to store the elements of the stack.
4. Declaring a member function — isEmpty() of bool type, Which will return true if it is empty, otherwise, it will return true.
5. Declaring a member function — isFull() of bool type, which will return true if the stack is full.
6. Declaring another member function int pop() of int type will return the top elements of the stack.
7. Declaring another member function void push(). Which will push an element at the top of the stack
8. Next, Declaring a member function int peek(). Which will return the element present in the required index.
9. After that, declare a Display function that displays all the members of the stack.
Member functions:
Now Writing the code inside our member functions outside the class using scope resolution (::), to write the member function outside the class we need first write the return type than the name of the class to which it belongs, and then use a scope resolution operator function then the name of the member function.
- isEmpty():
bool stack :: isEmpty(){if(top == -1){return true;}else{return false;}}
⮚ In the above code using the if statement we have checked if the top variable is equal to -1. If true then return.
2. isFull():
bool stack :: isFull(){if(top == MAX-1){return true;}else{return false;}}
⮚ In the above code using the if statement we have checked that if the top is equal to MAX — 1. Because the array is MAX(1000), and since the index starts from 0 we have subtracted 1 from it. If it is true it will return true else it will return false.
3. Push():
void stack :: push(){if((isFull())){cout<<"stack overflow"<<endl;}else{int val;cout<<"Enter the element you want to push: ";cin>>val;top++;arr[top] = val;}}
⮚ In the push function we are pushing the element at the top of the stack, to push any element at the top of the stack we first need to check if the stack is not full, so after calling the isFull function, if it returns true then we will print “stack overflow” otherwise in else statement we will first declare a variable var of int type Then we will take the input from the user for var. Then we will Increment the top variable which is initially -1, then store the value of var in the top index of the array.
4. Pop():
void stack :: push(){int stack :: pop(){if((isEmpty())){return -1;}else{int value = arr[top];top--;return value;}}
⮚ The pop function is used to remove the element at the top of the stack. But before that, we need to check if the stack is not empty. If it’s empty we will return -1 or the element which is not present in the stack (unique number). And if it is not empty
First, we have declared a variable to store the value at the top of the stack, since then we have decremented the top variable we will not be able to return the value present at the top. To prevent data loss. And then we will finally return the value present in the variable.
5. Peek():
int stack :: peek(){if((isEmpty())){cout<<"stack is empty";return -1;}else{int index;cout<<"Enter the index: "<<endl;cin>>index;return arr[index];}}
⮚ The peek function is used to get the element present in the required index of the stack. In the above code again first we will check whether the stack is not empty because what will you search for if the stack is empty it also helps us to reduce the time complexity of the code because after traversing all the indexes we will say that the stack is empty instead we will first check it using the isEmpty function and return -1 if its empty,
And if it’s not empty then we will take the index from the user and return the element at the given index.
int main(){stack s1;int t=1;while (t){int x;cout<<"\n\n1. if you want to push any elemnet "<<endl;cout<<"2. if you want to pop the element "<<endl;cout<<"3. if you want to peek any element"<<endl;cout<<"4. if you want to display the stack\n"<<endl;cout<<"ENTER YOUR CHOICE :- ";cin>>x;switch(x){case 1:s1.push();break;case 2:cout<<s1.pop()<<" : is poped from the stack"<<endl;break;case 3:cout<<s1.peek()<<" : is present in the index"<<endl;break;case 4:s1.display();break;default :cout<<"invalid Number"<<endl;
Conclusion:
Stack is a very interesting and simple topic to learn, In this blog, I have tried to explain the stack using real-life examples because we can easily relate it with our real-life examples. Daily we do many things like discussed above in the blog which gives us a clear understanding of the principle followed by the stack. Implementation of the stack using an array and operations like pop, push, and peek are also implemented and explained in detail, which help you to understand the logic and the code easily, I hope the blog was informative and easy to understand, thanks for reading the blog.
