Computer Algorithms I CS 305 Class Notes

Lecture Notes for Computer Algorithms I

6 November 2003 - Stack Implementations

A stack can be implemented with an array, a linked list, or something else.
An array implementation of stacks.
1. This why we defined stacks.
  1. An array implementation has minimal overhead.
    1. Almost all storage is devoted to data.
  2. Access is constant time with a small constant.
2. Data elements.
  1. The array holding the stack elements.
  2. An int giving the maximum size of the array (and the stack).
    1. This value is known as the stack capacity.
  3. An int giving the current number of elements in the array.
    1. This value is known as the stack size.
3. Invariants
  1. 0 <= stack size <= stack capacity
    1. This invariant allows for zero-length stacks, which are not too useful.
    2. Add the invariant 0 < stack capacity if that bothers you.
4. Operations
  1. create() - create the array, initialize stack size.
    1. Stack capacity may come in as a parameter.
  2. empty() - 0 == stack size
  3. push() - check for overflow, then add the element.
```
if stack size == stack capacity
  stack overflow
data[stack size++] = new value
```
  4. pop() - check for underflow, then remove the element.
```
if stack size == 0
  stack underflow
data[--stack size]
```
    1. Assuming the top value is not returned.
  5. top() - check for underflow, then return the element.
```
if stack size == 0
  stack underflow
return data[stack size - 1]
```
5. Adding dynamic behavior.
  1. A non-dynamic array impelementation of stacks can run out of space.
    1. The array could fill with data, causing stack overflows.
  2. Using non-dynamic stacks can be a pain.
    1. Either over-estimate the capacity, wasting space, or run the risk of stack overflow (which may also happen if the over-estimate's wrong).
  3. How can we eliminate stack overflow when using arrays?
    1. When the array's full, allocate a larger array.
```
if stack size == stack capacity
  stack capacity += 1000
  new array = new ElementType [stack capacity]
  copy(new array, array)
  new array = array
  delete array
```
    2. The increase value may also be specified by the client.
    3. You can also double the capacity: stack capacity *= 2.
      1. This results in a log vs. linear number of re-allocations.
      2. It also better fits the expectation that program that use a lot of data are going to keep on using a lot of data.
    4. This can also work in the other direction.
      1. When there's too much empty space, shrink the array to recover some if it.
        if stack capacity/stack size < 0.5 stack capacity /= 2 new array = new ElementType [stack capacity] copy(new array, array) array = new array delete [] array
      2. This is usually only valuable in resource-constrained environments.
A linked-list implementation of stacks.
1. This seems dumb.
  1. After all, a stack is a restricted linked-list to allow for a simpler, more efficient implementation than would be possible with linked lists.
2. But linked lists are much more cheaply and simply dynamic than are arrays.
  1. Eliminate stack overflow without expensive copying.
3. Data elements.
  1. A regular, simplified linked list implementation should the trick.
    1. Simplified because there's no traversals, and access occurs only at one end.
4. Invariants
  1. The usual linked-list invariants will work here too.
5. Operations
  1. create() - initialize the dummy head.
    1. head.next = null
  2. empty() - null == head.next
  3. push()
```
head.next = new ElementNode(value, head.next)
```
  4. pop() - check for underflow, then remove the element.
```
if head.next == null
  stack underflow
old = head.next
head.next = old->next
delete old
```
    1. Assuming the top value is not returned.
  5. top() - check for underflow, then return the element.
```
if head.next == null
  stack underflow
return head.next->value
```
6. Improving dynamic behavior.
  1. Doing a new or delete on each push or pop can get expensive.
    1. new or delete usually result in system calls.
  2. The free-list trick eliminates extra new and delete calls.
```
push(v)
  if free_list.next == null
    free_list.next = new ElementNode(v, null)
  node = free_list.next
  free_list.next = node->next
  node->next = head.next
  head.next = node

pop()
  if null == head.next
    stack underflow
  node = head.next
  head.next = node->next
  node->next = free_list.next
  free_list.next = node
```

This page last modified on 13 November 2003.