Much list a “list”, a stack does not describe a concrete data structure, but rather an abstract data type (ADT). A stack is a collection of items where we expect to mostly work with the item at the top of the stack.
Common operations on a stack include push(item), which adds an item to the top of the stack, and pop(), which removes and returns the item at the top of the stack. We can also have a peek() operation that returns the item at the top of the stack without removing it. But we do not typically have operations to access or modify items that are not at the top of the stack.
Picture a stack of plates while doing dishes. When you go to wash a plate, you take the top plate off the stack. You don’t go digging through the stack to find a plate in the middle. You only ever add or remove plates from the top of the stack. People might come up and add plates to the top of the stack while you are working.
A stack is a linear structure, like a list, but it has more restricted access. So a natural way to implement a stack is to use a list as the underlying data structure. We can use either an array based list or a linked list to implement a stack. In either case, we will only ever add or remove items from one end of the list, which we will consider to be the top of the stack.
First let’s consider a linked list based implementation. Even in the simplest linked list, we can efficiently add and remove items from the front of the list. So that is the logical end of the list to consider as the top of the stack.
Activity29.1.1.Stack Implemented with a Linked List.
A stack of integers has been implemented using a singly linked list. Use the interactive below to experiment with pushing and popping items from the stack.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
We could also use an array based list to implement a stack. In that case, to make push() and pop() efficient, we would add and remove items from the end of the array.
A stack of integers has been implemented using an array based list. Use the interactive below to experiment with pushing and popping items from the stack.
This particular implementation uses a fixed size array and thus has a limited capacity. We would typically implement a dynamic array to allow the stack to grow as needed.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
Because the stack is so simple, we might choose to implement it directly using an array or list nodes. But, if we already have access to a list implementation, it is often easier to just use that as the underlying data structure for the stack. In that case, we might just write a thin wrapper around the list to provide the stack interface. Something like:
This IntStack class just provides a limited interface to the underlying vector, forcing us to only interact with the stack through push, pop, peek, and isEmpty operations. The highlighted lines show all the places where the stack is handing off work to the underlying vector.
Also note that we do not need a destructor, copy constructor, or assignment operator because the vector is taking care of the memory management. When the IntStack object is destroyed, the vector that is a member of it is also destroyed. That executes the vector’s destructor, which cleans up the memory.
With a doubly linked list, we can efficiently add and remove items from either end of the list, so either end would be a reasonable choice for the top of the stack.
