A stack is a data structure containing zero or more items, all of the same type, which supports two basic operations:
- Push an element onto the stack.
- Pop the most recently added item off the stack, returning its value in the process.
In practice, we might choose to include the following operations as well:
- Construct a new, empty stack. (This one is more or less implicit.)
- Copy the contents of one stack to another.
- Peek at the top element in the stack (the one which would be popped next), without removing it.
- Empty an already existing stack.
- Find size of a stack.
- Test if empty.
Notice that the peek operation can be implemented as a pop followed by a push (and is therefore not fundamental) and the test if empty operation is the same as the find size operation followed by a test of whether or not the size is zero.
Anatomy and terminology
The name stack is quite simply based on real-life objects which are also known as stacks. For example, a stack of paper, a stack of books, a stack of plates. In such stacks, we add new items to the top, and we also remove items from the top; attempting to add or remove items anywhere else has potentially disastrous consequences. In computer science, of course, there does not always need to be a top and bottom. Instead, elements are added one-by-one to the stack. The most recently added element (and the first that would be removed) is at the top, and the oldest element (the last that would be removed) is at the bottom. An element is said to be higher than another if the former was added later (and will be removed sooner) than the latter; the latter element is said to be lower. To push means to add an element, and to pop means to remove an element.
The current state of program execution is partially described by a call stack. Each item in the call stack is a stack frame, that stores the entire environment of a specific invocation of a function. When a function calls another, a stack frame is created for the latter and pushed onto the call stack; when a function returns, its stack frame is popped off the stack. For example, if the function
main calls the function
fox, which in turn calls itself with different arguments, then during the deeper call to
fox, the call stack will contain, from bottom to top, frames for
fox. Each frame will contain the parameters of the corresponding function call, as well as any local variables in the corresponding function call. Hence, the two
fox frames will differ in that the higher one will contain the parameters for the deeper
fox call, and the lower one the parameters for the other. The call stack is implemented implicitly in essentially all programming languages that support function calls (that is, almost all useful programming languages).
In an array implementation of a stack, the contents of the stack are stored in contiguous indices in an array. Usually, the bottom of the stack is at the lowest index (such as 0), and the top of the stack at the highest. We may then implement the stack as follows:
object stack function construct(max_size) let A be an array that can hold at least max_size elements let top = 0 function push(x) A[top]=x top = top + 1 function pop top = top - 1 return A[top] function peek return A[top-1] function size return top function make_empty top = 0
Error-checking code has been omitted (consider what happens for example if we attempt to pop from an empty stack). The test if empty and copy operations have been omitted for the sake of brevity.
Linked list implementation
The array implementation will almost always be appropriate. However, for rare instances in which a contiguous block of memory of the required size cannot be found, a linked list can be used instead. Details of the list implementation are omitted below:
object stack function construct let L be an empty linked list function push(x) insert x after tail of L function pop remove tail of L, returning its data element function peek return data element at tail of L function size return size of L function make_empty empty L
As one can easily see, the stack is merely a container over the operations supported by the list itself. (Here we assume that the list maintains its own size; if this is not so then we can add a
size field to the stack object.)
C++ STL stack class
In the C++ STL,
std::stack, found in the
<stack> header, is a template container capable of holding items of any (fixed) type, the type being supplied as a template argument. Hence, for example,
stack<char> is a stack of characters. The container supplies the following member functions (note that
T is the type of the elements of the stack):
void push(const T& x): pushes
xonto the stack.
void pop(): performs a pop.
T& top(): returns the element which is to be popped next
size_type size(): returns the number of elements currently on the stack
bool empty(): returns
trueif the stack is empty,
stack container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own stack. There are, however, times when it might be necessary to execute some unsupported operation such as iteration through the elements of the stack. In such circumstances the STL
stack cannot be used and a custom stack must be implemented.
Note that the pop operation defined by this container is not identical to our own; it only removes the element and it does not return its value. To do both, call
top followed by