In computer science, a stack is an abstract data type that serves as a collection of elements with two main operations:
Push, which adds an element to the collection, and Pop, which removes the most recently added element. Additionally, a peek operation can, without modifying the stack, return the value of the last element added (the item at the top of the stack). The name stack is an analogy to a set of physical items stacked one atop another, such as a stack of plates. The order in which elements are added to or removed from a stack is described as last in, first out, referred to by the acronym LIFO. As with a stack of physical objects, this structure makes it easy to take an item off the top of the stack, but accessing a datum deeper in the stack may require removing multiple other items first. Considered a sequential collection, a stack has one end which is the only position at which the push and pop operations may occur, the top of the stack, and is fixed at the other end, the bottom. A stack may be implemented as, for example, a singly linked list with a pointer to the top element. A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept another element, the stack is in a state of stack overflow.
History
Stacks entered the computer science literature in 1946, when Alan Turing used the terms "bury" and "unbury" as a means of calling and returning from subroutines. Subroutines and a two-level stack had already been implemented in Konrad Zuse's Z4 in 1945. Klaus Samelson and Friedrich L. Bauer of the Technical University of Munich proposed the idea of a stack called Operationskeller ("operational cellar") in 1955 and filed a patent in 1957. In March 1988, by which time Samelson was deceased, Bauer received the IEEE Computer Pioneer Award for the invention of the stack principle. Similar concepts were independently developed by Charles Leonard Hamblin in the first half of 1954 and by Wilhelm Kämmerer with his automatisches Gedächtnis ("automatic memory") in 1958. Stacks are often described using the analogy of a spring-loaded stack of plates in a cafeteria. Clean plates are placed on top of the stack, pushing down any plates already there. When the top plate is removed from the stack, the one below it is elevated to become the new top plate.
Non-essential operations In many implementations, a stack has more operations than the essential "push" and "pop" operations. An example of a non-essential operation is "top of stack", or "peek", which observes the top element without removing it from the stack. Since this can be broken down into a "pop" followed by a "push" to return the same data to the stack, it is not considered an essential operation. If the stack is empty, an underflow condition will occur upon execution of either the "peek" or "pop" operation. Additionally, many implementations include convenience operations that handle common tasks, such as checking if the stack is empty or returning its size.
Software stacks
Implementation A stack can be easily implemented either through an array or a linked list, as it is merely a special case of a list. In either case, what identifies the data structure as a stack is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations. The following will demonstrate both implementations using pseudocode.
Array An array can be used to implement a (bounded) stack, as follows. The first element, usually at the zero offset, is the bottom, resulting in array[0] being the first element pushed onto the stack and the last element popped off. The program must keep track of the size (length) of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted (assuming a zero-based index convention). Thus, the stack itself can be effectively implemented as a three-element structure:
structure stack: maxsize: integer top: integer items: array of item
procedure initialize(stk: stack, size: integer): stk.items ← new array of size items, initially empty stk.maxsize ← size stk.top ← 0
The push operation adds an element and increments the top index, after checking for overflow:
procedure push(stk: stack, x: item): if stk.top = stk.maxsize: report overflow error else: stk.items[stk.top] ← x stk.top ← stk.top + 1
Similarly, pop decrements the top index after checking for underflow, and returns the item that was previously the top one:
procedure pop(stk : stack): if stk.top = 0: report underflow error else: stk.top ← stk.top − 1 r ← stk.items[stk.top] return r
Using a dynamic array, it is possible to implement a stack that can grow or shrink as much as needed. The size of the stack is simply the size of the dynamic array, which is a very efficient implementation of a stack since adding items to or removing items from the end of a dynamic array requires amortized O(1) time.
Linked list Another option for implementing stacks is to use a singly linked list. A stack is then a pointer to the "head" of the list, with perhaps a counter to keep track of the size of the list:
structure frame: data : item next : frame or nil
structure stack: head : frame or nil size : integer
procedure initialize(stk : stack): stk.head ← nil stk.size ← 0
Pushing and popping items happens at the head of the list; overflow is not possible in this implementation (unless memory is exhausted):
procedure push(stk : stack, x : item): newhead ← new frame newhead.data ← x newhead.next ← stk.head stk.head ← newhead stk.size ← stk.size + 1
procedure pop(stk : stack): if stk.head = nil: report underflow error else: r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 return r
… excerpt ends here. Continue reading the full article.
