A stack is a linear data structure that mimics real-life stacks such as a stack of physical disks. Stacks are useful to process the data in the Last In First Out (LIFO) order.
1. Concepts of Stack Data Structure
Stacks have only one end for both insertions and deletions. So, the stack always removes the last element inserted. This is known as Last In First Out (LIFO) or First In Last Out (FILO).
Properties of Stack
- Top: The top of the stack
- Element: The actual data
- Push: A new element is inserted on Top of the stack
- Pop: Element is removed from the Top of the stack
- Underflow: Stack is empty, but requested for pop
- Overflow: Stack reaches its capacity, but requested for push (applicable only for the array-based implementation of the stack)
2. Operations and Time Complexity of Stack
Basically, the insertion and deletion in the stack are called Push and pop respectively. The following are the Stack operations with time and space complexities.
| Operation | Short Description | Time Complexity (worst) | Space Complexity (worst) |
|---|---|---|---|
| Push | Insert a new element on top | O(1) | O(n) |
| Pop | Delete the element from the top | O(1) | O(n) |
| Search | Search the element by value | O(n) | O(n) |
Stack always performs the operations on Top, so the Push and Pop operations work faster in O(1) time. The search operation takes O(n) time, so they are not intended for the stack.
3. Implementation of Stack Data Structure
Stacks can be implemented both using Array and Linked List. However, we can choose the right implementation based on static or dynamic data.
3.1. Array implementation of Stack
Array implementation of Stack is static and limited by the array size. The stack can not store elements beyond its capacity. But, arrays work faster for push and pop operations because of the continuous memory. So, use the array-based implementation for the fixed amount of data.
Stack implementation using Array with C++ example
3.2. Linked List implementation of Stack
Linked List implementation of Stack is dynamic in size. It can grow and shrink based on dynamic data. However, the push and pop operations are slower than the array, because it requires memory allocation and deallocation. So, use the linked list based implementation only for the dynamic data.
Stack implementation using Linked List with C++ example
3.3. Array vs Linked List implementation of Stack
Look at the table to know the difference between Array and Linked list implementation of Stack.
| Stack using Array | Stack using Linked List |
| Static size | Dynamic size grows at runtime |
| Suitable for static data | Suitable for dynamic data |
| Faster push and pop operations. Because of its continuous memory locations which are cache friendly for the CPU. | Bit slower due to runtime allocations. Also, the data is not stored in continuous memory locations. |
| Memory is not effectively used. Because an array requires predefined memory which is not fully utilized. | Effective usage of the memory as it creates the node only when required. |
| No additional memory is required for bookkeeping | Additional memory is required to store the links. |
4. Applications of Stack Data Structure
4.1. When to use the Stack?
Stacks are useful for Applications that process the data in the Last In First Out (LIFO) order. Specifically, processing nested structures such as recursive operations. For example,
- Reversing a string – Recursively push all the characters on Stack. Finally, pop all the characters that result in reverse order.
- Balanced parenthesis – Matching open and closing braces in an expression.
- Backtracking – Remember certain states when you navigate and use them to go back to the previous states.
- Tree or graph traversals – Use stack to remember the path of traversal and to return back.
The stack data structure cannot be used for sequential First In First Out (FIFO) operations. Alternatively, use Queue Data Structure for FIFO operations.
4.2. Realtime Applications of Stack
- Stack memory allocation for programming – Allocates stack memory when you call a function and cleans when you return back.
- The compiler uses the stack to convert arithmetic expressions to either Prefix or Postfix form.
- Redo/Undo operations.
- Backward navigations.
- Tower of Hanoi.
- Stock span problem.
- Histogram problem.
- Graph algorithms like topological sorting and strongly connected components.
4.2. Advantages and Disadvantages of Stack
4.2.1. Pros
- Faster insertion and deletion operations in O(1) time.
- Requires additional memory to store the pointer in Linked List Implementation.
4.2.2. Cons
- Searching on the stack is slower and takes O(n) time.
- Not suitable for sequential First In First Out (FIFO) operations.
- Memory space is not effectively used in Array Implementation.