Stack

From Algorithmist

This is a stub or unfinished. Contribute by editing me.

A collection of items in which only the most recently added item may be accessed or removed; this latest added item is called the top. Basic operations are push (add an item to the stack) and pop (remove the top from the stack). Often top and isEmpty are available, too. Also known as "last-in, first-out" or LIFO. Compare queue and deque.

[edit] Implementation

[edit] Array

A stack can easily be implemented as an array. The first element of the array would be the "bottom" and the top's location would fluctuate as new items are added and old ones removed. An auxiliary variable is needed to keep track of what position in the array is the top.

The following example should clarify how to use an array as a stack. The asterisk marks the top of the stack, the left bar marks the bottom. Pushing and popping are merely manipulating the variable top and accessing the array.

(top == -1)
|* 0  0  0  0  0

push 1 (top -> 0)
|  1* 0  0  0  0

push 9 (top -> 1)
|  1  9* 0  0  0

pop (top -> 0)
|  1* 0  0  0  0

push 2 (top -> 1)
|  1  2* 0  0  0

push 5 (top -> 2)
|  1  2  5* 0  0

[edit] Linked List

Sometimes a linked list is employed in creating a stack. At the cost of slightly more memory (to keep track of links), you gain the flexibility of a stack of arbitrary size, whereas arrays are usually quite fixed but efficient. The head of a singly list linked is also the top of the stack. The following pseudocode functions show how to use a linked list as a stack, with listhead being a pointer.

function push(item, listhead)
    item->next = listhead
    listhead = item
end function

function pop(listhead)
    listhead = listhead->next
    return listhead
end function