Stack

From GPWiki
Jump to: navigation, search

A stack is a container that allows elements to be pushed in and popped out in LIFO (last in, first out) fashion. Depending on the implementation, only the top element can be accessed or all elements can be accessed.

Functions

A stack requires at least 2 publicly accessible functions called 'Push' and 'Pop' to be considered a Stack. A 'Push' is like an insertion of a piece of data. Once the piece of data is 'pushed' it is said to be "In the stack". The stack will remember the order of insertions. A 'Pop' will remove and return the latest piece of data to be inserted. i.e. LIFO fashion.

Optional functions are sometimes added as a convenience to the programmer. An incomplete list of possible optional function are:
Peek: Is like a 'Pop' in that it returns the latest piece of data to be inserted, but unlike a 'Pop' it does not remove it from the stack. Another peek option may allow you to see other pieces of data in a stack.
toArray: This would return a standard array containing everything that is currently in a stack.

Implementations

There are many ways to implement a stack. There is no 'best' way to implement a stack. The optimal way to implement a stack often depends on how you plan on using the stack.

Some languages, notably .net, have the stack class already implemented.

Array

The implementation of a stack goes like this: An array (possibly dynamic) is allocated, and a 'current element' pointer is created pointing to the bottom (one side, does not matter a lot which one) of the stack.

A push operation consists of writing the pushed element to the location indicated by the 'current element' pointer, and incrementing (or decrementing, for downward growing stacks) that pointer.

A pop operation consists of decrementing (or incrementing, as long as this goes the opposite way of the push operation) the 'current element' pointer, and returning the element the pointer used to point at.

Linked List

A Linked List offers another way to implement a stack. Basic knowledge of a Linked List required first. To change a single linked list from a standard single linked list would require minor changes. To implement a 'Push' one would simply use an "Insert Head" function. To implement a 'pop' one would use a "Remove Head" function.

Uses

While this data structure must sound pretty trivial, you can do neat things with it. Most notably, the whole idea of recursion (of functions) requires some kind of stack, and can be simulated using a stack.