CSCE 221 Chapter 4

« previous | Tuesday, January 18, 2010 | next »

Stacks

Stacks are #Abstract Data Structures

• Last in are first out (LIFO)
• Best example: Undo in text editor
• push() adds item to top of stack
• pop() removes top item

Abstract Data Structures

Example: stock trades

Supported options: buy, sell, cancel (implementations are not described, so we can't tell how long it takes to buy something)

Array-based Stack

• add elements from left to right
• variable keeps track of last element

Traversing Code Example

Algorithm size() {
  return t+1;
}

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

Algorithm push(o) {
  if (t == S.length - 1) throw FullStackException();
  else S[t++] = o;
}

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

1. Increment size by a constant $C$
2. Double the size when it is full $2^{k}$

Measuring Performance

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

Amortized time

same thing as average time per operation

$T_{a}={\frac {f\left(n\right)}{n}}$

Where $f\left(n\right)$ returns the number of operations (or time) for $n$ elements.

Plot average time on a graph

Big-O Notation

Find the cost of the doubling method

Suppose we have $n$ items we want to add to the stack. How many doublings ($k$) will occur in terms of the array size?

${\begin{aligned}2^{k}&=n\\k\log {2}&=\log {n}\\k&=O\left(\log {n}\right)\end{aligned}}$

We can ignore log(2) since it is a constant, and Big-O only focuses on dominating terms.

Example

Suppose that $t(n)$ is the time taken for an array of $n$ elements.

The amortized time (cost) for the operation in question would be ${\tfrac {t(n)}{n}}$

If we plot $\left(n,{\frac {t(n)}{n}}\right)$ on a graph, we can see how time relates to the input size.

Queue

Another abstract data structure

• First in, first out (FIFO)
• Best example: waiting in lines
• enqueue() adds item to end of line
• dequeue() removes item from front of line

Array-based implementation

Use an array of size $n$ in a circular fashion:

• enqueue on the right/end
• dequeue from the left/front

Two pointers: front and end

if ((end + 1) % size == front), then queue is full

Algorithm size() {
  return (N - f + e) % N
}

Algorithm isEmpty() {
  return (e==f)
}

Algorithm enqueue(o) {
  if (size() == N-1) {
   throw FullQueueException
  } else {
    Q[r] = o
    r = (r + 1) % N
  }
}

Measuring Performance

	FullQueueException	Array (doubling)	Array (increment by constant)
enqueue()	$O\left(1\right)$	worst: $O\left(n\right)$ avg: $O\left(1\right)$	worst: $O\left(n\right)$ avg: $O\left(n\right)$

Double-Ended Queue ("Deque")

Basically a combination of stack and queue:

• insertFirst(o)
• insertLast(o)
• removeFirst()
• removeLast()
• first()
• last()
• size()
• isEmpty()

Summary

	Stack (array-based, fixed size)	Stack (growable)	Stack (singlist-based: ins/rem-lft)
pop	$O(1)$	$O(1)$	$O(1)$
push	$O(1)$	$O(n)$ worst $O(1)$ best	$O(1)$
	Queue (array-based, fixed size)	Queue (growable)	Queue (singlist-based: ins-rgt, rem-lft)
dequeue	$O(1)$	$O(1)$	$O(1)$
enqueue	$O(1)$	$O(n)$ worst $O(1)$ best	$O(1)$
	Deque (array-based, fixed size)	Deque (growable)	Deqeue (singlist-based)
removeFirst	$O(1)$	$O(1)$	$O(1)$
removeLast	$O(1)$	$O(1)$	$O(n)$
insertFirst	$O(1)$	$O(n)$ worst $O(1)$ best	$O(1)$
insertLast	$O(1)$	$O(n)$ worst $O(1)$ best	$O(1)$