Stack (data structure)

From wiki.gis.com
Jump to: navigation, search

In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are typically those that have been in the list the longest.

History

The stack was first proposed in 1955, and then patented in 1957, by the German Friedrich L. Bauer. The same concept was developed independently, at around the same time, by the Australian Charles Leonard Hamblin.

Inessential Operations

In modern computer languages, the stack is usually implemented with more operations than just "push" and "pop". Some implementations have a function which returns the current length of the stack. Another typical helper operation top[1] (also known as peek) can return the current top element of the stack without removing it from the stack.

Software Stacks

Implementation

In most high level languages, a stack can be easily implemented either through an array or a linked list. What identifies the data structure as a stack in either case 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 C.

Array Implementation

The array implementation aims to create an array where the zero-offset position is the bottom. That is, array[0] is the bottom. The program keeps track of which offset index corresponds to the top; this index changes as the stack shrinks and grows in size. The stack itself can therefore be effectively implemented as a two-element structure:

    typedef struct{
        int top;
        int items[STACKSIZE];
    }STACK;

The push() operation is used both to initialize the stack, and to store values to it. It is responsible for changing the value of ps->top and for inserting a value into the ps->items[] array. In a responsible C implementation, it also checks whether the array is already full—if it is, storing a value to it will result in a segmentation fault, at least in C.

    void push(int x, STACK *ps)
    {
        if(ps->top == STACKSIZE-1){
            printf("Error: stack overflow");
            exit(EXIT_FAILURE);
        } else
            ps->items[++(ps->top)] = x;
 
        return;
    }

The pop() operation is responsible for removing a value from the stack, and decrementing the value of ps->top. A responsible C implementation will also check that the array is not already empty. If it is, popping a value from the array will result in another segmentation fault.

    int pop(STACK *ps)
    {
        if(empty(ps)){
            printf("Error: stack underflow");
            exit(EXIT_FAILURE);
        } else
            return(ps->items[(ps->top)--]);
    }

Linked List Implementation

The linked-list implementation is equally simple and straightforward. In fact, a stack linked-list is much simpler than most linked-list implementations: it requires that we implement a linked-list where only the head node or element can be removed, or popped, and a node can only be inserted by becoming the new head node.

Unlike the array implementation, our structure typedef corresponds not to the entire stack structure, but to a single node:

    typedef struct stack{
        int data;
        struct stack *nxt;
    } STACK;

Such a node is identical to a typical linked-list node, at least to those that are implemented in C.

The push() operation both initializes an empty stack, and adds a new node to a non-empty one. It works by receiving a data value to push onto the stack, along with a target stack, creating a new node by allocating memory for it, and then inserting it into a linked list as the new head:

    void push(int nw, STACK **hd)
    {
        STACK *node= (STACK*) malloc(sizeof(STACK));  /* create a new node */
 
        if (node == NULL){
            printf("Error: no space available for node");
            getchar();
            exit(EXIT_FAILURE);
        } else {                                      /* initialize node */
            node->data = nw;
            node->nxt = NULL;
        }
 
        if(empty(*hd))                                /* initialize list */
            *hd = node;
        else {                                        /* insert new head */
            node->nxt = *hd;
            *hd = node;
        }
 
        return;
    }

A pop() operation removes the head from the linked list, and assigns the pointer to the head to the previous second node. It check whether the list is empty before popping from it:

    int pop(STACK **hd)
    {
        int value;
        STACK *dummy;
 
        if(empty(*hd)) {                             /* stack is empty */
           printf("Stack is empty");
           getchar();
        } else {                                     /* pop a node */
            value = (*hd)->data;
            dummy = *hd;
            *hd = (*hd)->nxt;
            free(dummy);
        }
 
        return value;
    }

Stacks and Programming Languages

Some languages, like LISP and Python, do not call for stack implementations, since push and pop functions are available for any list. All Forth-like languages (such as Adobe PostScript) are also designed around a stack that is directly visible to and manipulated by the programmer.

C++'s Standard Template Library provides a "stack" templated class which is restricted to only push/pop operations. Java's library contains a class that is a specialization of ---this could be considered a design flaw, since the inherited get() method from ignores the LIFO constraint of the .

Related data structures

The functionality of a queue and a stack can be combined in a deque data structure. Briefly put, a queue is a First In First Out (FIFO) data structure.

Hardware stacks

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, storing local data and call information for nested procedures. 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 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, usually in the form of a hardware register, 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, in which a data item is placed at the location pointed to by the stack pointer, and the address in the stack pointer is adjusted by the size of the data item;
  • a pop or pull operation: a data item at the current location pointed to by the stack pointer is removed, and the stack pointer is adjusted by the size of the data item.

There are many variations on the basic principle of stack operations. Every stack has a fixed location in memory at which it begins. As data items are added to the stack, the stack pointer is displaced to indicate the current extent of the stack, which expands away from the origin (either up or down, depending on the specific implementation).

For example, a stack might start at a memory location of one thousand, and expand towards lower addresses, in which case new data items are stored at locations ranging below 1000, and the stack pointer is decremented each time a new item is added. When an item is removed from the stack, the stack pointer is incremented.

Stack pointers may point to the origin of a stack or to a limited range of addresses either above or below the origin (depending on the direction in which the stack grows); 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 (towards addresses 999, 998, and so on), the stack pointer must never be incremented beyond 1000 (to 1001, 1002, etc.). 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:

  • Dup(licate): the top item is popped, and then pushed again (twice), so that an additional copy of the former top item is now on top, with the original below it.
  • Peek: the topmost item is inspected (or returned), but the stack pointer is not changed, and the stack size does not change (meaning that the item remains on the stack). This is also called top operation in many articles.
  • Swap or exchange: the two topmost items on the stack exchange places.
  • Rotate: the n topmost items are moved on the stack in a rotating fashion. For example, if n=3, 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.

Stacks are either visualized growing from the bottom up (like real-world stacks), or, with the top of the stack in a fixed position (see image), a coin holder, a Pez dispenser, or growing from left to right, so that "topmost" becomes "rightmost". This visualization may be independent of the actual structure of the stack in memory. 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 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 terminology are used irrespective of whether the stack actually grows towards lower memory addresses or 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.

Hardware support

Stack in main memory

Many CPUs have registers that can be used as stack pointers. Some, like the Intel x86 and the Zilog Z80, have special instructions that implicitly use a register dedicated to the job of being a stack pointer. Others, like the DEC PDP-11 and the Motorola 68000 family have addressing modes that make it possible to use any of a set of registers as a stack pointer.

Stack in registers

The Intel 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. Sun's C has a number of register windows organized as a stack which significantly reduces the need to use memory for passing function's arguments and return values.

Stack in separate stack memory

There are also a number of microprocessors which implement a stack directly in hardware: Some microcontrollers have a fixed-depth stack that is not directly accessible.

  • some PIC microcontrollers
  • Computer Cowboys MuP21
  • Harris RTX line
  • Novix NC4016

Many stack-based microprocessors were used to implement the programming language Forth at the microcode level. Stacks were also used as a basis of a number of mainframes and mini computers. Such machines were called stack machines, the most famous being the Burroughs B5000.

Applications

Stacks are ubiquitous in the computing world.

Expression evaluation and syntax parsing

Calculators employing reverse Polish notation use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form may be accomplished using a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context-free languages allowing them to be parsed with stack based machines.

Example (general)

The calculation: ((1 + 2) * 4) + 3 can be written down like this in postfix notation with the advantage of no precedence rules and parentheses needed:

1 2 + 4 * 3 +

The expression is evaluated from the left to right using a stack:

  1. push when encountering an operand and
  2. pop two operands and evaluate the value when encountering an operation.
  3. push the result

Like the following way (the Stack is displayed after Operation has taken place):

Input Operation Stack
1 Push operand 1
2 Push operand 1, 2
+ Add 3
4 Push operand 3, 4
* Multiply 12
3 Push operand 12, 3
+ Add 15

The final result, 15, lies on the top of the stack at the end of the calculation.

Example (Pascal)

This is an implementation in Pascal, using marked sequential file as data archives.

{
programmer : clx321
file  : stack.pas
unit  : Pstack.tpu
}
program TestStack;
{this program use ADT of Stack, i will assume that the unit of ADT of Stack has already existed}
 
uses
   PStack;   {ADT of STACK}
 
{dictionary}
const
   mark = '.';
 
var
   data : stack;
   f : text;
   cc : char;
   ccInt, cc1, cc2 : integer;
 
  {functions}
  IsOperand (cc : char) : boolean;    {JUST  Prototype}
    {return TRUE if cc is operand}
  ChrToInt (cc : char) : integer;     {JUST Prototype}
    {change char to integer}
  Operator (cc1, cc2 : integer) : integer;     {JUST Prototype}
    {operate two operands}
 
{algorithms}
begin
  assign (f, cc);
  reset (f);
  read (f, cc);  {first elmt}
  if (cc = mark) then
     begin
        writeln ('empty archives !');
     end
  else
     begin
        repeat
          if (IsOperand (cc)) then
             begin
               ccInt := ChrToInt (cc);
               push (ccInt, data);
             end
          else
             begin
               pop (cc1, data);
               pop (cc2, data);
               push (data, Operator (cc2, cc1));
             end;
           read (f, cc);   {next elmt}
        until (cc = mark);
     end;
  close (f);
end.

Runtime memory management

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.

Forth 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, including the p-code machine and the Java virtual machine.

Almost all computer runtime memory environments use a special stack (the "call stack") to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes. They follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls. This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.

Some programming languages use the stack to store data that is local to a procedure. Space for local data items is allocated from the stack when the procedure is entered, and is deallocated when the procedure exits. The C programming language is typically implemented in this way. Using the same stack for both data and procedure calls has important security implications (see below) of which a programmer must be aware in order to avoid introducing serious security bugs into a program.

Security

Some computing environments use stacks in ways that may make them vulnerable to security breaches and attacks. Programmers working in such environments must take special care to avoid the pitfalls of these implementations.

For example, some programming languages use a common stack to store both data local to a called procedure and the linking information that allows the procedure to return to its caller. This means that the program moves data into and out of the same stack that contains critical return addresses for the procedure calls. If data is moved to the wrong location on the stack, or an oversized data item is moved to a stack location that is not large enough to contain it, return information for procedure calls may be corrupted, causing the program to fail.

Malicious parties may attempt to take advantage of this type of implementation by providing oversized data input to a program that does not check the length of input. Such a program may copy the data in its entirety to a location on the stack, and in so doing it may change the return addresses for procedures that have called it. An attacker can experiment to find a specific type of data that can be provided to such a program such that the return address of the current procedure is reset to point to an area within the stack itself (and within the data provided by the attacker), which in turn contains instructions that carry out unauthorized operations.

This type of attack is a variation on the buffer overflow attack and is an extremely frequent source of security breaches in software, mainly because some of the most popular programming languages (such as C) use a shared stack for both data and procedure calls, and do not verify the length of data items. Frequently programmers do not write code to verify the size of data items, either, and when an oversized or undersized data item is copied to the stack, a security breach may occur.

See also

  • Queue
  • Deque
  • Call stack
  • Stack-based memory allocation
  • Stack machine

References

  1. Horowitz, Ellis: "Fundamentals of Data Structures in Pascal", page 67. Computer Science Press, 1984

Further reading

  • Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition.Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp. 200–204.

External links