The stack data structure is one of the simplest and most fundamental data structures and has a wide range of applications. Some more advanced data structures may use stacks internally depending upon their implementation strategy. Having a full knowledge and understanding of this fundamental data structure is important for any serious programmer or computer science student. In this article, we'll discuss some of the places stacks are used, different ways we can implement stacks and their benefits & drawbacks, and provide example stack implementations in multiple programming languages.
- Function Calls: stacks are implicitly used to keep track of nested function calls.
- Syntax Checking: stacks are a good fit for checking if an expression has the same number of open and close parenthesis.
- Undo / Redo: stacks can be used as a means of implementing undo / redo functionality.
- Graph traversals: stacks can be used to facilitate depth-first search within trees and graphs.
How to Implement a Stack
There are many ways in which a stack can be implemented. In the table below, we'll outline a few possible approaches, discuss their space and time complexity for different operations, and give some general notes. If you're not familiar with Big O notation: n represents the number of input elements, O(n) means the operation takes steps, and O(1) means the operation takes a small number of steps, regardless of how large n is.
|Array||O(n)||O(1)||O(1)||Depending upon how the number of elements in the stack changes, the array may need to resize itself, thus causing potential slowdowns.|
|Linked List||O(n)||O(1)||O(1)||No overhead caused by changes in the stack's size.|
Coding a Stack with an Array
Coding a Stack with a Linked List
Unlike the array implementation, the head of the list will correspond to the last item in the stack. When we push an item to the stack, we will create a new node, set the next reference of that node to the current head, then set the head to that new node. When we pop an item, we'll get the value from the head node, then set the head reference to the head's next reference.