Summary:The stack is a very useful data structure which we use very often. This tutorial explains the Stack data structure in detail and its practical application.
The Stack is one of the most important data structure which has many uses. Several fundamental programming concepts such as recursion, backtracking, the function calls and many others use Stack.
What is Stack Data Structure?
The stack is an abstract data type and data structure which is based on LIFO (last in first out).
It means the element that we insert at last (top of stack) will be the first one to be taken out.Open Image
We use Stack in our daily life. Here are some examples which describe the working of Stack.
- Stack of Plates
- Stack of bread
The plate that we put on top is the first one that we take out.Open Image
There are two ways to create a stack in programming, first using an Array and second using a Linked list. Both are useful in specific situations.
The insert operation in Stack is called PUSH and delete operation POP.
PUSH Operation in Stack Data Structure
The PUSH operation is used to insert a new element in the Stack. PUSH operation inserts a new element at the top of the stack.Open Image
Stack Push Operation
It is important to check overflow condition before push operation when using an array representation of Stack.
If we try to insert a new element in full stack (array has limited size), a stack overflow condition occurs. It means that we cannot add more elements to the stack.
To avoid this situation we can use a linked list instead of the array because the linked list has dynamic size, we just need to add one more node with the data.
The push operation in Stack structure takes only O(1) constant time. The reason is that we only add one element on top of the Stack.
POP Operation in Stack Data Structure
The POP operation is to remove an element from the top of the stack. The element deleted is the recently inserted element in the Stack.
It means that we delete element from the top of the stack.Open Image
Stack Pop Operation
In POP operation we need to check Stack underflow condition.
Stack underflow condition occurs when the Stack is already empty and we try POP operation (we cannot remove an element from empty Stack).
The POP operation also takes only O(1) constant time because we remove only one element from the top of the stack.
Representation of Stack
There are two ways to implement Stack, the first one is using array and the other one is using a Linked list.
Array Representation of Stack
This is the general representation of Stack.
We initialize an empty array of size
nin which we perform PUSH and POP operations.
The array Stack contains the element from starting index up to the top pointer which represents the last element of the stack.Open Image
Stack using Array
topPointer = -1, it means the stack is empty and when the
topPointer = n it means the stack is full.
It can be very helpful to check overflow and underflow condition.
Here is the pseudo code for Stack using array
arr of size
check_Overflow if(top==n) return True else return False check_UnderFlow if(top==-1) return True else return False PUSH_OPERATION(data) if(check Overflow) print("Stack Over flow, No more space left") return else top = top+1 arr[top] = data POP_OPERATION if(check Underflow) print("Stack Underflow, No more elements left") return else top = top-1 return arr[top+1]
This is the pseudo code to create stack using an array. You can create a class in any language and implement these methods.
It is necessary to implement methods to check overflow and underflow condition because it is a common error.
Linked List Representation of Stack
Before moving to this part you must know about linked list and the difference between array and linked list.
A linked list has some advantages and disadvantages over an array which make it more suitable for some specific tasks.
They have dynamic length, it means there is no limit on the number of elements we can add. It is convenient to use a linked list in place of an array when the number of elements is unknown.Open Image
Stack using Linked list
Here are some quick facts about Stack using linked lists which will be helpful to make a decision.
PUSH and POP operations in the linked list take O(1) constant time because a pointer is at the end of the linked list which manage insertion and deletion.
We only need to check the underflow condition here. If top pointer refers to null then the Stack is already empty.
Applications of Stack Data Structure
As we already see that insertion and deletion take constant time which is performance efficient.
Here are some common application of Stack data structures.
- Back buttons in browsers
- Undo mechanism
- Evaluate prefix and postfix notation
- Track Nested Function calls
Now, you know how important the Stack is, here is a quick summary of all the above points.
- The stack is based on LIFO (last in first out). The last element inserted is popped out first.
- We call insert operation as Push and delete operation as Pop in Stack.
- We can implement stack using an array or a linked list.
- Use array when you want fixed size Stack and linked list for dynamic size.
- Properly check Stack overflow and underflow conditions to avoid bugs.