Stack

From Algorithmist
Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

Stack is an Abstract Data Type (ADT) in which INSERT and DELETE operation is prespecified. In a stack, only the most recently added item may be accessed or removed. Stack maintains last-in, first-out (LIFO) policy. The INSERT operation on a stack is called PUSH and the DELETE operation is called POP.

Implementation[edit]

Array[edit]

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

Linked List[edit]

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