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.
Stack
A stack is a collection of items which can be modified by adding items to the end and removing items from the same end. This property makes it a last in, first out (LIFO) data structure. As a consequence, the first item to be inserted will also be the last item to be removed before the stack is empty again. Stacks have a wide variety of applications, including:
- 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.
Space | Push | Pop | Notes | |
---|---|---|---|---|
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
In this section, we will use a resizing array to implement the stack. In some languages, such as JavaScript, arrays will resize themselves automatically. In others, such as Java, arrays are always fixed size, so we will use a class such as ArrayList to handle the resizing for us. Note that if we know that our stack will have at most n items ahead of time, we can use a fixed-size array of size n and forgo using a resizing array, thus reducing the costs associated with dynamic array resizing. However, in this example, we'll stick to the dynamic array size approach. In the internal array, the item at the end of the array corresponds to the last item which will be popped, and the position pushed items will be placed in.
Coding a Stack with a Linked List
In this section, we'll use a linked list to implement the stack. If you are not familiar with linked lists, or would like to learn more about them, please visit our introduction to linked lists. For this implementation, we will use two classes:
- Node: an encapsulation of a node in the linked list, which will store a value and the reference to the next item in the list.
- Stack: an encapsulation of th eentire stack. This will hold a reference to the head of the linked list only.
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.