by Stack is a data structure used for storing collection of data where order in which data is arriving is important. In Stack, insertion and deletion both happened from the same end which is known as “Top”.
The data which is arrived last will be deleted first in Stack. This data ordering is called as Last in First out or LIFO.
Properties of Stack
- Insertion and Deletion both happened from the same end.
- Sequence in which data is arrived is important.
- Data can be accessed in Stack in LIFO (Last in First out) format.
Let’s look into the below diagram to understand how Stack works.
Applications of Stack
- Infix to postfix conversion
- Evaluation of postfix expression
- Implementing function calls (including recursive functions)
- Undo operation
Stack Operations
- PUSH – This operation will add an entry in Stack. In case Stack is full then error is returned. This condition is called Stack Overflow.
- POP – Removes the top item from the Stack. This ensures that LIFO is being maintained. In case Stack is empty then this condition is called Stack Underflow.
- IsEmpty – Checks whether Stack is empty or not.
- MaxSize – This returns the max size of Stack.
- Entries/Size – This returns the current number of entries in the Stack.
Implementation of Stack
- Simple array based implementation
- Linked lists implementation
Comparison between Single Array vs Linked List implementation
| Parameter | Simple Array | Linked List |
| Space Complexity | O(n) | O(n) |
| Push() Time Complexity | O(1) | O(1) |
| Pop() Time Complexity | O(1) | O(1) |
| Entries() Time Complexity | O(1) | O(1) |
| IsEmptyStack() Time Complexity | O(1) | O(1) |
| IsFullStack() Time Complexity | O(1) | O(1) |
| DeleteStack() Time Complexity | O(1) | O(n) |
| Stack Size | Expensive expansion operation once a while | Graceful expansion or shrink operation. |
| Space and Time usage | No extra space needed | Extra space needed along with reference manipulation |
Important Stack Topics
- Stack Implementation using array
- Generic Stack implementation using array for all data types
- Balanced parentheses check in an expression
- Infix to Postfix conversion
- Postfix expression evaluation
- Minimum number in Stack
- Reversal of a Stack
- Implement two Stacks in a single array
- Palindrome check for Linked List
