Elementary Data Structures

Stacks and queues

• In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO, policy.
• In a queue, the element deleted is always the one that has been in the set for the longest time: the queue implements a first-in, first-out, or FIFO, policy

Stacks

• The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP.
• We can implement a stack of at most n elements with an array . The array has an attribute that indexes the most recently inserted element.
• When , the stack contains no elements and is empty. We can test to see whether the stack is empty by query operation STACK-EMPTY. If we attempt to pop an empty stack, we say the stack underflows, which is normally an error.If exceeds , the stack overflows.

  STACK-EMPTY（S） 
  1 if S.top==0 
  2    return TRUE 
  3 else return FALSE 
  PUSH（S,x） 
  1 S.top = S.top + 1 
  2 S[S.top]=x
  POP（S） 
  1 if STACK-EMPTY（S） 
  2    error “underflow”
  3 else S.top = S.top -1 
  4    return S［S.top + 1］

  takes time.

Queues

• We call the INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE

• The queue has a head and a tail

• When , the queue is empty.If we attempt to dequeue an element from an empty queue, the queue underflows

• When or both and , the queue is full, and if we attempt to enqueue an element, then the queue overflows

  ENQUEUE（Q,x） 
  1 Q[Q.tail] = x
  2 if Q.tail == Q.length 
  3    Q.tail = 1 
  4 else Q.tail = Q.tail + 1 
  DEQUEUE（Q） 
  1 x= Q[Q.head]
  2 if Q.head == Q.length 
  3    Q.head = 1 
  4 else Q.head = Q.head +1 
  5 return x

  takes time. # Linked lists

• A linked list is a data structure in which the objects are arranged in a linear order.Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.

• Doubly linked list is an object with an attribute key and two other pointer attributes: next and prev .

• If , the element has no predecessor and is therefore the first element, or head, of the list. If , the element has no successor and is therefore the last element, or tail, of the list.

• An attribute points to the first element of the list. If , the list is empty.

• If a list is singly linked, we omit the prev pointer in each element

• If a list is sorted, the linear order of the list corresponds to the linear order of keys stored in elements of the list

• In a circular list, the prev pointer of the head of the list points to the tail, and the next pointer of the tail of the list points to the head.

Searching a linked list

LIST-SEARCH（L,k） 
1 x = L.head 
2 while x ≠ NIL and x.key ≠ k 
3       x = x.next 
4 return x

takes time

Inserting into a linked list

LIST-INSERT（L, x） 
1 x.next = L.head 
2 if L.head ≠ NIL 
3    L.head.prev = x
4 L.head = x 
5 x.prev = NIL

takes time

Deleting from a linked list

LIST-DELETE（L,x） 
1 if x.prev ≠ NIL 
2    x.prev.next = x.next 
3 else L.head = x.next 
4 if x.next ≠ NIL 
5    x.next.prev = X.prev

takes time.

Sentinels

• The attribute points to the head of the list, and points to the tail. Similarly, both the next attribute of the tail and the prev attribute of the head point to .
• An empty list consists of just the sentinel, and both and point to .

LIST-SEARCH'（L,k） 
1 x = L.nil.next 
2 while x ≠ L.nil and x.key ≠ k 
3       x= x.next 
4 return x
LIST-INSERT'（L, x） 
1 x.next = L.nil.next 
2 L.nil.next.prev = x 
3 L.nil.next = x 
4 x.prev = L.nil
LIST-DELETE'（L, x） 
1 x.prev.next = x.next 
2 x.next.prev = x.prey

• Sentinels rarely reduce the asymptotic time bounds of data structure operations, but they can reduce constant factors.
• We should use sentinels judiciously. When there are many small lists, the extra storage used by their sentinels can represent significant wasted memory.

Implementing pointers and objects

A multiple-array representation of objects

We can represent a collection of objects that have the same attributes by using an array for each attribute

A single-array representation of objects

• Each attribute of the object corresponds to an offset in the range from 0 to , and a pointer to the object is the index . In Figure 10.6, the offsets corresponding to key, next, and prev are 0, 1, and 2, respectively. To read the value of , given a pointer , we add the value of the pointer to the offset 2, thus reading ..

Allocating and freeing objects

• In some systems, a garbage collector is responsible for determining which objects are unused.
• We shall now explore the problem of allocating and freeing (or deallocating) homogeneous objects using the example of a doubly linked list represented by multiple arrays
• Then objects represent elements currently in the dynamic set, and the remaining objects are free
• We keep the free objects in a singly linked list, which we call the free list. The free list uses only the next array, which stores the next pointers within the list.

ALLOCATE-OBJECTO 
1 if free ==NIL 
2    error “out of space”
3 else x = free 
4    free = x.next 
5 return x 
FREE-OBJECT（x） 
1 x.next = free 
2 free = x

Representing rooted trees

Binary trees

We use the attributes , and to store pointers to the parent, left child, and right child of each node in a binary tree . If , then is the root. If node has no left child, then , and similarly for the right child. The root of the entire tree is pointed to by the attribute . If , then the tree is empty.

Rooted trees with unbounded branching

• Instead of having a pointer to each of its children, however, each node x has only two pointers
  • points to the leftmost child of node , and
  • points to the sibling of immediately to its right.
• The left-child, right-sibling representation has the advantage of using only space for any -node rooted tree.