WHAT IS A STACK?
Stack is a linear list in which elements are inserted and deleted from the same end called the top of the stack. It is a LIFO (Last In First Out) type data structure.
Let’s see some real-life examples of the stack :
Here we can see set of plates . So when the plates were placed, we kept one above other. Now when we want to take out the plates, we first have to move the plate which is at the top. Then the ones which are down of it. So this is an example of stack.
Also, we see lots of examples of stacks in our daily life like stack of trays in café, a stack of books or tennis balls. In all these, we can see that any object can be removed or added only at the top.
BASIC OPERATIONS OF STACK:
Following are some common operations on stack:
· push() : Inserting elements inside the stack is called push operation. If the stack is full then we cannot add elements in the stack and this condition is called Stack Overflow.
· pop() : When we delete elements from the stack is is said to be pop operation. If the stack is empty that is no elements exist inside the stack. Then this condition is called Stack Underflow.
· isEmpty() : It checks whether a stack is empty or not.
· isFull : It checks if the stack is full or not.
· peek() : Returns the element at the given position.
· display() : Displays the elements inside the stack.
Implementation of Stack:
Since stack is a linear list, we can implement it using Arrays or Linked List.
If the size of stack is not known in advance , it is better to implement it as a linked list.
Some applications of Stack:
Expression Handling −
Infix to Postfix or Infix to Prefix Conversion −
The stack can be used to convert some infix expression into its postfix equivalent, or prefix equivalent. These postfix or prefix notations are used in computers to express some expressions. These expressions are not so much familiar to the infix expression, but they have some great advantages also. We do not need to maintain operator ordering and parenthesis.
Postfix or Prefix Evaluation −
After converting into prefix or postfix notations, we have to evaluate the expression to get the result. For that purpose, also we need the help of stack data structure.
Backtracking Procedure −
Backtracking is one of the algorithm designing techniques. For that purpose, we dive into some way, if that way is not efficient, we come back to the previous state and go into some other paths. To get back from the current state, we need to store the previous state. For that purpose, we need a stack. Some examples of backtracking are finding the solution for the Knight Tour problem or N-Queen Problem etc.
Another great use of stack is during the function call and return process. When we call a function from one other function, that function call statement may not be the first statement. After calling the function, we also have to come back from the function area to the place, where we have left our control. So we want to resume our task, not restart. For that reason, we store the address of the program counter into the stack, then go to the function body to execute it. After completion of the execution, it pops out the address from the stack and assigns it to the program counter to resume the task again.
👩💻Written By - Anushka Ghosh