[Home]Stack data structure

HomePage | Recent Changes | Preferences

The stack is a data structure which works in 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 with a real stack of plates.

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                 ==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 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.

In application programs written in a [high level language]?, a stack can be implemented efficiently using both arrays and linked lists.


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. These languages include Forth, and Postscript.

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.

HomePage | Recent Changes | Preferences
This page is read-only | View other revisions
Last edited December 4, 2001 8:29 pm by 144.132.75.xxx (diff)