Main Page | See live article | Alphabetical index

Stack (computing)

A stack is a data structure that works on the principle of Last In First Out (LIFO). This means that the last item put on the stack is the first item that can be taken off, like a physical stack of plates. A stack-based computer system is one that is based on the use of stacks, rather than being register based.

The two main operations applicable to a stack are:

Some environments that rely heavily on stacks may provide additional operations, for example:

Stacks are either visualised growing from the bottom up (like real-world stacks) or growing from left to right, so that "topmost" becomes "rightmost". This means that 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 visualisations of this process:

apple                                     banana
banana                 		

Table of contents
1 right rotate
2 right rotate
3 External link
4 Applications
5 External link

right rotate

> cucumber cucumber apple

cucumber banana apple

right rotate

> apple cucumber banana

A stack may be represented in computers inside block of memory cells, with the bottom at a fixed location, and a variable stack pointer to the current top cell. pushing first increases the top pointer by one, pointing it to the next cell, and then fills that with the new top value. poping first takes the top value, and then decreases the top pointer by one. Increasing and decreasing may be exchanged to yield a stack representation that grows from high addresses to lower ones.

Many CPUs have registers that can be used as stack pointers. Some, like the x86, have special instructions that implicitly use a register dedicated the job of being a stack pointer. Others, like the PDP-11 and the 68000 family have addressing modes that make it possible to use any of a set of registers as a stack pointer. The 80x87 series of numeric coprocessors has a set of registers that can be accessed either as a stack, or as a series of numbered registers. Some microcontrollers, like the PIC and AVR, have a fixed-depth stack that is not directly accessible.

There are also a few processors which implement a stack directly in hardware. Examples include the MuP21 processor from Computer Cowboys, and the Harris RTX line.

External link

In application programs written in a high level language, a stack can be implemented efficiently using either arrays or linked lists.

Applications

Calculators employing reverse polish notation use a stack structure to hold values.

A number of computer 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.

The Forth programming language uses two stacks, one for argument passing and one for subroutine return addresses. The use of a return stack is extremely commonplace, but the somewhat unusual use of an argument stack for a human-readable programming language is the reason Forth is referred to as a stack-based language.

Many virtual machines are also stack-oriented: p-Code machine, Java virtual machine.

Almost all computer environments use a stack to hold information about procedure/function nesting.

External link