What is Stack? 🤔
Stack is a very simple data structure with predefined size which allows inserting or removing elements in a particular order.
To understand the basic concept, let’s have a look at a small example. Consider that you are putting bricks on top of each other to create a tower. Now to take the bricks out of the tower, you will have to take out the brick that is on top first and so on. Stack offers the same behavior, commonly known as First-In-Last-Out or Last-In-First-Out.
- Stack is like a pipe with only one open end.
- You can do two operations:
- PUSH: to insert new element.
- POP: to remove the existing element.
- When the it is full, it’s said to be in a “Overflow State”, since you cannot perform PUSH operation anymore.
- When the it is empty, it’s said to be in a “Underflow State”, since you cannot perform POP operation anymore.
Where do we use it?
- Most popular application would be to implement Undo and Redo operations in software products.
- Expression Evaluation, for example Arithmetic expressions.
- Backtracking Algorithms.
- For memory management when running the programs.
How to implement?
Stack data structure can be easily implemented using Array.
- Check if the stack is full or not.
- If full, print error saying it is in “Overflow State”.
- If not, increment top by 1 and add element in the last.
- Check if the stack is empty or not.
- If empty, print error saying it is in “Underflow State”.
- If not, decrement top by 1 and delete last.
- Just return the value of top variable, i.e. index of the last element in array.
- Perform Linear Search on the array and return the element.