Stack
In computer science, a stack is an abstract data type (ADT) that supports last-in first-out (LIFO) access to its contents. Stacks are used extensively in computer science.
Stacks can be viewed as a container object with at least two operations: push and pop. The push operation adds a new object to the top of the stack, pushing down whatever was there before. The pop operation removes the object on the top of the stack, and moves the remaining elements up, or if the stack was empty, produces an error. Stacks often have many more operations implemented on them, such as a top operation, which returns the object on the top of the stack without modifying the stack, and a size or count operation, which determines the number of objects within the stack container.
For instance, suppose we start with an empty stack of integers, and then push the object 5. The stack now contains one object, and the top of the stack is five. If we later push the object 6, then the stack will contain two objects, and the top of the stack is 6. Then, popping the stack will yield the object 6, and the stack will have one object, and the top of the stack is 5. Since objects are removed from the stack in the reverse order that they were added, a stack supports LIFO access.
Implementation of Stacks
Perhaps the simplest implementation of a stack uses a flat array and an associated stack pointer variable:
DataStructure Stack
Has-a Array Arr of Objects
Has-a Integer SP, initially 0
Method Push(Stack S, Object O)
If S.SP > S.Arr.Size, then Error
S.Arr[ S.SP ] <- O
S.SP <- S.SP + 1
Method Pop(Stack S)
If S.SP == 0, then Error
S.SP <- S.SP - 1
return S.Arr[ S.SP ]
This implementation has the drawback of having a static size limit, determined by the size of its array Arr. This type of array is implemented at the instruction level on many architectures.
A more advanced stack implementation would store its contents in a linked list ADT. In this way, the programmer does not need to determine the maximum size of the stack. Many languages, particularly scripting langauges such as Perl and Ruby do not offer separate implementations of a stack ADT, and instead encourage the programmer to use the linked list ADT.
Some Applications of Stacks
As was mentioned earlier, stacks are used extensively in computer programming. Nonetheless, here are some noteworthy uses of stacks:
- In many high-level languages, a stack frame, based upon the idea of a stack, is used to store
local variables and function parameters.
- To hold search state in depth-first search (DFS) algorithms, as opposed to breadth first search (BSF) which uses a queue.
See Also
- abstract data types, such as:
- data structures
- last-in first-out (LIFO) access pattern
- first-in first-out (FIFO) access pattern
- tree search, and in particular