Stack (abstract data type)
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.
The order in which an element 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 Technical University Munich proposed the idea of a stack called Operationskeller 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 with his automatisches Gedächtnis 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 "stack top" or "pop" operations. 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 stack, as follows. The first element, usually at the zero offset, is the bottom, resulting inarray being the first element pushed onto the stack and the last element popped off. The program must keep track of the size 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. 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.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:
if stk.top = stk.maxsize:
report overflow error
else:
stk.items ← 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:
if stk.top = 0:
report underflow error
else:
stk.top ← stk.top − 1
r ← stk.items
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 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.head ← nil
stk.size ← 0
Pushing and popping items happens at the head of the list; overflow is not possible in this implementation :
procedure push:
newhead ← new frame
newhead.data ← x
newhead.next ← stk.head
stk.head ← newhead
stk.size ← stk.size + 1
procedure pop:
if stk.head = nil:
report underflow error
r ← stk.head.data
stk.head ← stk.head.next
stk.size ← stk.size - 1
return r
Stacks and programming languages
Some languages, such as Perl, LISP, JavaScript and Python, make the stack operations push and pop available on their standard list/array types. Some languages, notably those in the Forth family, are designed around language-defined stacks that are directly visible to and manipulated by the programmer.The following is an example of manipulating a stack in Common Lisp :
> ;; set the variable "stack"
> ;; get top element, should modify the stack
> stack ;; check the value of stack
> ;; push a new top onto the stack
Several of the C++ Standard Library container types have and operations with LIFO semantics; additionally, the template class adapts existing containers to provide a restricted API with only push/pop operations. PHP has an class. Java's library contains a class that is a specialization of. Following is an example program in Java language, using that class.
package org.wikipedia.examples;
import java.util.Stack;
public class Example
Some processors, such as the PDP-11, VAX, and Motorola 68000 series have addressing modes useful for stack manipulation. The following trivial PDP-11 assembly source code pushes two numbers on a stack and adds them, leaving the result on the stack.
; R0 is assumed to point to a stack area
; - pre-decrements stack pointer allocating item on stack
; + Post-increments stack pointer removing item on stack
MOV #12,- ; Push 12 on stack
MOV #34,- ; push 34 on stack
ADD +, ; Pop 34 off stack and add to 12
; leaving the result on the stack
Hardware stack
A common use of stacks at the architecture level is as a means of allocating and accessing memory.Basic architecture of a stack
A typical stack is an area of computer memory with a fixed origin and a variable size. Initially the size of the stack is zero. A stack pointer points to the most recently referenced location on the stack; when the stack has a size of zero, the stack pointer points to the origin of the stack.The two operations applicable to all stacks are:
- A push operation: the address in the stack pointer is adjusted by the size of the data item and a data item is written at the location to which the stack pointer points.
- A pop or pull operation: a data item at the current location to which the stack pointer points is read, and the stack pointer is moved by a distance corresponding to the size of that data item.
Stack pointers may point to the origin of a stack or to a limited range of addresses above or below the origin ; however, the stack pointer cannot cross the origin of the stack. In other words, if the origin of the stack is at address 1000 and the stack grows downwards, the stack pointer must never be incremented beyond 1000. If a pop operation on the stack causes the stack pointer to move past the origin of the stack, a stack underflow occurs. If a push operation causes the stack pointer to increment or decrement beyond the maximum extent of the stack, a stack overflow occurs.
Some environments that rely heavily on stacks may provide additional operations, for example:
- Duplicate: the top item is popped and then pushed twice, such that two copies of the former top item now lie at the top.
- Peek: the topmost item is inspected, but the stack pointer and stack size does not change. This can also be called the top operation.
- Swap or exchange: the two topmost items on the stack exchange places.
- Rotate : the topmost items are moved on the stack in a rotating fashion. For example, if, items 1, 2, and 3 on the stack are moved to positions 2, 3, and 1 on the stack, respectively. Many variants of this operation are possible, with the most common being called left rotate and right rotate.
A right rotate will move the first element to the third position, the second to the first and the third to the second. Here are two equivalent visualizations of this process:
apple banana
banana right rotate> cucumber
cucumber apple
cucumber apple
banana left rotate> cucumber
apple banana
A stack is usually represented in computers by a block of memory cells, with the "bottom" at a fixed location, and the stack pointer holding the address of the current "top" cell in the stack. The "top" and "bottom" nomenclature is used irrespective of whether the stack actually grows towards higher memory addresses.
Pushing an item on to the stack adjusts the stack pointer by the size of the item, pointing it to the next cell, and copies the new top item to the stack area. Depending again on the exact implementation, at the end of a push operation, the stack pointer may point to the next unused location in the stack, or it may point to the topmost item in the stack. If the stack points to the current topmost item, the stack pointer will be updated before a new item is pushed onto the stack; if it points to the next available location in the stack, it will be updated after the new item is pushed onto the stack.
Popping the stack is simply the inverse of pushing. The topmost item in the stack is removed and the stack pointer is updated, in the opposite order of that used in the push operation.