Similarly to a stack of plates, adding or removing is only practical at the top.
Simple representation of a stack runtime with push and pop operations
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 typically requires 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.
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 (pop stack) ;; get top (leftmost) element, should modify the stack\nA\n> stack ;; check the value of stack\n(B C)\n> (push 'new stack) ;; push a new top onto the stack\n(NEW B C)\n"}}'>>(setfstack(list'a'b'c));; set the variable "stack" (ABC) >(popstack);; get top (leftmost) element, should modify the stack A >stack;; check the value of stack (BC) >(push'newstack);; push a new top onto the stack (NEWBC)
Several of the C++ Standard Library container types have std::stack template class adapts existing containers to provide a restricted API with only push/pop operations. PHP has an Vector. Following is an example program in Java language, using that class.
Hardware stack
editStacks are often visualized growing from the bottom up (like real-world stacks). They may also be visualized growing from left to right, where the top is on the far right, or even growing from top to bottom. The important feature is for the bottom of the stack to be in a fixed position. The illustration in this section is an example of a top-to-bottom growth visualization: the top (28) is the stack "bottom", since the stack "top" (9) is where items are pushed or popped from.
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 bananaA 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 (either decrementing or incrementing, depending on the direction in which the stack grows in memory), 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.
Stack in main memory
editMany CISC-type CPU designs, including the x86, Z80 and 6502, have a dedicated register for use as the call stack stack pointer with dedicated call, return, push, and pop instructions that implicitly update the dedicated register, thus increasing code density. Some CISC processors, like the PDP-11 and the 68000, also have special addressing modes for implementation of stacks, typically with a semi-dedicated stack pointer as well (such as A7 in the 68000). In contrast, most RISC CPU designs do not have dedicated stack instructions and therefore most, if not all, registers may be used as stack pointers as needed.
Stack in registers or dedicated memory
edit
The programmable pocket calculator HP-42S from 1988 had, like nearly all of the company's calculators of that time, a 4-level-stack and could display two of four values of the stack registers X, Y, Z, and T at the same time due to its two-line display, here X and Y. In later models like the HP-48, the number of levels was increased to be only limited by memory size.
A typical call stack, storing local data and call information for multiple levels of procedure calls. This stack grows downward from its origin. The stack pointer points to the current topmost datum on the stack. A push operation decrements the pointer and copies the data to the stack; a pop operation copies data from the stack and then increments the pointer. Each procedure called in the program stores procedure return information (in yellow) and local data (in other colors) by pushing them onto the stack. This type of stack implementation is extremely common, but it is vulnerable to buffer overflow attacks (see the text).
A number of programming languages are stack-oriented, meaning they define most basic operations (adding two numbers, printing a character) as taking their arguments from the stack, and placing any return values back on the stack. For example, PostScript has a return stack and an operand stack, and also has a graphics state stack and a dictionary stack. Many virtual machines are also stack-oriented, including the p-code machine and the Java Virtual Machine.
Almost all calling conventions
- Knuth, Donald (1997). "§2.2.1: Stacks, Queues, and Deques". The Art of Computer Programming. Vol. 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. pp. 238–243. ISBN 0-201-89683-4.