Dynamic data structure

A stack is an abstract data type often used in the field of computing.  A stack is also known as a dynamic data structure because it can grow and shrink at run-time.

A stack is a Last In First Out (LIFO) data structure. It allows items to the be added (pushed) and removed (popped) from the top only.

Where stacks are used

The call stack (execution stack) is maintained in memory by the operating system. The call stack allows one program (procedure or function) to call another, ensuring that control is passed back to the calling program so that it can continue from where it left off when the called program finishes. The call stack is used to store return addresses, parameters and register contents.

Similarly, the call stack is used when a function or procedure calls itself recursively. Each time a function invokes itself, it effectively interrupts its previous invocation. This is similar to one program calling another, which in turn calls another, and so on.

The call stack is used when a program is interrupted, either by a hardware interrupt, or a clock interrupt. This allows the operating system to return control to the interrupted program once the interrupting program (known as the interrupt service request handler (ISR)) has finished.

A stack can be used to implement an undo facility.  For example, the undo button in a word processor undoes the changes made to a document in reverse order, starting with the most recent change first (LIFO)

Two stacks can be used programmatically to build an expression tree for an infix expression. This tree can then be traversed to obtain a reverse polish expression.

A stack can be used to programmatically evaluate a reverse polish expression.

Stacks may also be appropriate for some applications. A classic example being the game ‘Towers of Hanoi’.

Push and pop operations

Because a stack is a Last In First Out (LIFO) structure, data items can only be added to the top of the stack, or removed from the top.

Adding an item to the top of a stack is known as a push operation.

Removing an item from the top of the stack is known as a pop operation.

A stack can be implemented using an array variable, plus additional variables to indicate the maximum possible size of the stack and the current position of the top.

The following diagram illustrates a stack during a succession of push and pop operations. Note that it is not strictly necessary to remove an item from the stack when it is popped. Redefining the top of the stack below the item that was ‘removed’ means that the old data will be overwritten when a new item is later pushed onto the stack.

Algorithms

The two fundamental operations of a stack, push and pop, are described below:

Push

Check to see if stack is full (Top = MaxStackSize)
If the stack is full report an error and stop
Else increment Top pointer
Add data item to top of stack

Pop

Check to see if the stack is empty (Top = 0)
If the stack is empty report an error and stop
Else copy data item from top of stack
[Optionally, remove data item from stack]
Decrement Top pointer

Stack Pseudocode

Push

Procedure Push
        IF Top = MaxStackSize THEN
                OUTPUT “stack is full”
        ELSE
                Add 1 to Top
                Stack[Top] = New data item
        END IF
End Procedure

Pop

Procedure Push
        IF Top = 0 THEN
                OUTPUT “stack is empty”
        ELSE
                Popped item = Stack[Top]
                Subtract 1 from Top
        END IF
End Procedure