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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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()	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}	worst:	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}
		best:	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}
		avg:	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}
pop()	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}		Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}
size()	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}		w/ aux var:	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}
				w/o aux var:	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)}

From now on, we'll always assume that size() and isEmpty() always perform in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} time.