Stack is a dynamic data set in which the element deleted from the set is the latest inserted: last-in-first-out, or LIFO policy. The insert operation on stack is often called PUSH, and the delete operation is often called POP.
A sack can be implemented by an array S[1..n] with an attribute top[S] that indexes the most recently inserted element. When top[S] = 0, the stack is empty. If an empty stack is popped, we say the stack underflows. When top[S] > n, the stack overflows. The following are stack algorithms:
Stack-Empty(S)
1 if
top[S] = 0
2 return TRUE
3 else
4 return FALSE
Push(S, x)
1 top[S]++
2 S[top[S]]
= x
Pop(S)
1 if
Stack-Empty(S)
2 throw "underflow"
3 else
4 top[S]—
5 return
S[top[S]+1]
Each of above algorithms runs in O(1) time.
The queue implements a first-in-first-out, or FIFO policy. The insert operation on a queue is called ENQUEUE, and the delete operation is called DEQUEUE.
A queue of at most (n-1) elements can be implemented using an array Q[1..n]. The queue has an attribute head[Q] that points to the index of its head. The attribute tail[Q] indexes the next location at which the new element will be inserted. The order is circular, i.e. the location 1 immediately follows the location n. For example:
1 2 3 4 5
13 11 12 Q[1..5]
tail head
The following are basic queue operations:
Enqueue(Q,x)
1 /* head
and tail cannot point to the same location,
hence only (n-1) elements can be stored */
2 if
tail[Q] + 1 = head[Q]
3 throw "overflow"
4 Q[tail[Q]]
= x
5 tail[Q]
= (tail[Q]+1) % (n+1) + 1 // wrap
around
Dequeue(Q)
1 if
head[Q]=tail[Q]
2 throw "underflow"
3 x =
Q[head[Q]]
4 head[Q]
= (head[Q]+1) % (n+1) + 1 // wrap
around
5 return
x
Both operations run in O(1) time.
A linked list is a data structure in which objects are arranged in linear order. Each object points to the location of the next object. In a doubly linked list each object also points to the location of the previous object.
More formally, for a doubly linked list L, head[L] points to the first element of the list. Given an element x from L, prev[x] points to its predecessor, next[x] points to its successor. If next[x] = NIL, x is the last element in L. If prev[x] = NIL, x is the first element in L.
The following algorithm finds the first element with key k in the list L:
List-Search(L,k)
1 x =
head[L]
2 while
x <> NIL and key[x] <> k
3 x = next[x]
4 return
x
The above algorithm runs in Q(n) time in the worst case, since it may have to search the entire list.
The following algorithm inserts an element x with a key set to the front of the list.
List-Insert(L,x)
1 next[x]
= head[L]
2 if
head[L] <> NIL
3 prev[head[L]] = x
4 head[L]
= x
5 prev[x]
= NIL
The running time of the insert algorithm is O(1).
The following algorithm deletes an element x from the linked list. (It assumes the pointer to x is known, otherwise use List-Search to find x according to some key).
List-Delete(L,x)
1 if
prev[x] <> NIL
2 next[prev[x]] = next[x]
3 else
4 head[L] = next[x]
5 if
next[x] <> NIL
6 prev[next[x]] = prev[x]
This algorithm runs in O(1), however it would require Q(n) time if it needs to search for an element.
The deletion algorithm would be simpler if we can ignore testing for the boundary conditions. This ca be achieved by using sentinels, dummy objects to simplify boundary conditions. Assume we have an object nil[L] that represents NIL, but has all the fields of other list elements. For example, for a circular, doubly linked list with a sentinel:
next[nil[L]] = head[L]
prev[nil[L] = tail[L]
The code for List-search is now simplified:
List-Delete'(L,k)
1 next[prev[x]]
= next[x]
2 prev[next[x]]
= prev[x]
Similarly, the insertion algorithm is simplified:
List-Insert'(L,x)
1 next[x]
= next[nil[L]]
2 prev[next[nil[L]]]
= x
4 next[nil[L]]
= x
5 prev[x]
= nil[L]
Sentinels rarely reduce asymptotic time bounds, but they can reduce constant factors. They should be used carefully when causing inefficient memory usage as in applications with many small lists.
Trees can be represented using linked data structures. For example, in case of binary trees we use fields p, left, and right to store pointers to the parent, left child, and right child of each node of the binary tree T. The root of the tree is root[T] (x: p[x] = NIL).
To represent trees with unbounded branching, we use binary tree representation. In this scheme, each node still contains a parent pointer, and root[T] points to the root of T. Instead of having a pointer for each child of a node, each node x has only two pointers:
If node x has no children, then left-child[x] = NIL. If node x is the rightmost child of its parent, then right-sibling[x] = NIL.