Stacks as data structure
What is stack?
Stack is an abstract data structure used which has this unique property called as LIFO, last in first out. LIFO means whatever goes in first, is last one to come out and item that has gone fist will be at the stack for longest. Stack data structure is used when you have to track all previous visited elements and process them in reverse them. This is typical in problems related to binary tree like non-recursive implementation of traversals of tree, parenthesis matching, print a word in reverse order etc.
Whenever we encounter a problem which requires some sort of reversing on the already existing arrangement, we go for stacks.
Basic operations allowed on stack.
1. Push() : With this operation, an element is added to stack.
2. Pop() : With this operation, element at the top of the stack is taken out.
Other operations which are commonly used during stack usage are :
1. is_empty() : This checks if there are some elements present in stack.
2. peek(): This operation return the element at the top, but unlike pop, it does not remove element from stack.
Since stack can dynamically increase and decrease in size based on push and pop operation, we need to keep track of the top of the stack. Notice that, stack can be represented as recursive structure i.e if we remove the top of the stack, remaining N-1 element is again a stack.
Let’s see an example to understand reversal order of stack, that means whatever is entered in stack is taken out in reverse order.
|Reversal order of stack
This reversal property is used to maintain called and calling function relationships, web browsers back button history etc.
Implementation of stack data structure
Stacks can be implemented in two ways.
1. Array based implementation of stack.
In this implementation, underlying data structure used is an array. We keep an extra variable (top) to keep track of number of elements present in stack at given time. When we add an element to stack, we increase the top. When we pop an element from stack, we decrease the top.
In this implementation, top being -1 represents empty stack and top equal to N-1, N being the size of array, represents stack full.
Push and pop operations are of O(1) complexity.
Drawback of this implementation is that we need to define stack size before hand and increasing and decreasing dynamically would be overhead.
2. Linked List based implementation of stack.
In this implementation, underlying data structure used is a linked list. Every node in the linked list represents an element in stack. Every push operation adds a node at the head of the linked list and every pop operation removes the node from the head of the linked list.
In this implementation too, push and pop operations are of O(1) complexity. Also stack can grow as much as required. Head being NULL represents empty stack.
Drawback is we need to store 4 bytes extra as next pointer for each element.
Stacks are used for supporting recursive paradigm in programming languages. During program management, parameters passed to functions, return values, return pointers are stored in stack.
Problems which can be solved efficiently using stack data structure