Stack (ADT)

A "PEZ Dispenser" container: Last in; First out (LIFO)

Examples:

• Undo in Text Editor

Functions

• int size() — Returns how many items are in the stack.
• bool isEmpty() — Returns whether the stack is empty (i.e. size is 0).
• void push(Object o) — Puts an object $o$ at the top of the stack.
• Object pop() — Removes the top object from the stack and returns it.
• Object top() — Peeks at the top item without removing it.

Implementations

Array-based (Fixed)

• Add elements from left to right
• Use a variable to keep track of the last element (size)

class ArrayStack {
private:
  int t;
  Object* S;
  int sz;

public:
  Stack(int sz = 1000) : t(0), S(new Object[sz]), sz(sz) {}

  int size() { return t+1; }

  bool isEmpty() { return t==0; }

  Object pop() {
    if (isEmpty()) throw new EmptyStackException();
    else return S[t-- + 1];
  }

  void push(const Object& o) {
    if (t == sz-1) throw FullStackException();
    else S[t++] = o;
  }
};

What if we didn't want to throw an exception when the stack is full?

1. Increment the size by a constant
2. double the size when it is full

Array-based (Doubling)

void ArrayStack::push(o) {
  if (t == sz-1) {
    Object* T = new Object[sz*2];
    for (int i=0; i<sz; ++i) T[i] = S[i];    // copy items to new array
    sz *= 2;
    delete S
    S = T;
  }
  S[t++] = o;
}

Linked-List

class ListStack {
private:
  int t;
  Node* top;

public:
  class Node {
  private:
    Node* n;
    Object elem;

  public:
    Node(const Object& o, Node* nxt = 0, ) : elem(o), n(nxt) {}
    Node* next() { return n; }
    Object element() { return elem; }
  };

  Stack(int sz = 1000) : top(0), t(0) {}

  int size() { return t; }

  bool isEmpty() { return t==0; }

  Object pop() {
    if (t == 0) throw EmptyStackException();
    Object elem = tmp->element();
    Node* tmp = top;
    top = top->next();
    delete tmp;
    --t;
    return elem;
  }

  void push(const Object& o) {
    top = new Node(o, top);
    ++t;
  }
};

Analysis

See Amortized Time and Asymptotic Analysis for more information.

	Array (fixed)	Array (doubling)		List
push()	$O(1)$	worst:	$O(n)$	$O(1)$
		best:	$O(1)$
		avg:	$O(1)$
pop()	$O(1)$	$O(1)$		$O(1)$
size()	$O(1)$	$O(1)$		w/ aux var:	$O(1)$
				w/o aux var:	$O(n)$

From now on, we'll always assume that size() and isEmpty() always perform in $O(1)$ time.