2017-01-03

# stacks and queues

## stack

stack: examine the item most recently added (last in; first out)
queue: examine the item least recently added (first in; first out)

Linked-list:

• every operation takes constant time
• use extra time and space to deal with links

Resizing array:

• evray operation takes constant amortized time, total time is much less
• less wasted space

### linked-list representation

in section 1.3.

Every operation takes constant time in the worst case.
A stack with N items use $$\sim 40N$$

#### Node()

private Node first=null;
private class Node
{
String item;
Node next;
}


#### pop()

// save item to return
String item = first.item;
// delete first node
first = first.next;
// return saved item
return item;


#### push()

// save a link to the list
Node oldfirst = first;
// create a new node for the beginning
first = new Node();
// set the instance variables in the new node
firt.item = newitem;
first.next = oldfirst;


### array implementation

• use array s[ ] to store N items on stack
• push(): add new item as s[N]
• pop(): remove item from s[N-1]

Use between $$\sim 8N$$ (when full) and $$\sim 32N$$ (when one-quarter full) bytes to represent a stack with N items.
Defect: stack overflows when N exceeds capacity.

## resizing arrays

How to grow and shrink array?

First try:

• push(): increase size of array s[ ] by 1.
• pop(): decrease size of array s[ ] by 1.

Too expensive.

• need to copy all item to a new array.
• inserting first N items takes time proportional to $$1+2+…+N \sim N^2/2$$

To grow array, if array is full, create a new array of twice the size, and copy items. Time proportional to N.

public ResizingArrayStackOfString()
{ s = new String; }

public void push(String item)
{
if (N == s.length) resize(2*s.length);
s[N++] = item;
}

private void resize(int capacity)
{
String[] copy = new String[capacity];
for (i=0; i<N; i++)
copy[i] = s[i];
s = copy;
}


To shrink the array: halve size of array s[ ] when array is one-quarter full.

public String pop()
{
String item = s[--N];
s[N] = null;
if (N>0 && N == s.length/4) resize(s.length/2);
return item
}



Every operation takes constant amortized time.

## queues

maintain pointer to first and last nodes in a linked list;
insert/remove from opposite ends.

• insert at end of linked list
• remove from front of linked list

### linked-list

#### dequeue

same code as linked-list stack pop()

String item = first.item;
first = first.next;
if (isEmpty()) last = null;
return item;


#### enqueue

// save a link to the last node
Node oldlast = last;
// create a new node for the end
Node last = new Node();
last.item = "not";
last.next = null;
// linke the new node to the end of the list
if (isEmpty()) first = last;
else            oldlast.next = last;


#### full

public boolean isEmpty()
{ return first == null; }


### resizing array

• use array q[ ] to store items
• enqueue(): add new item at q[tail]
• dequeue(): remove item from q[head]
• update head and tail modulo the capacity
• add resizing array

## generics

Want to implement StackOfURLs, StackOfInts, …

Avoid casting in client.

public class Stack<Item>
{
private class Node
{
Item item;
Node next;
}
// ...
public void push(Item item)
// ...
public Item pop()
// ...
}


Generic array creation is not allowed in java. Use cast

public FixedCapacityStack(int capacity)
{ s = (Item[]) new Object[capacity]; }


declare and initialize a Stack of integers

Stack<Integer> stack = new Stack<Integer>();
// in java 7
Stack<Integer> stack = new Stack<>();


## iterators

Support iteration over stack items by client, without revealing the internal representation of the stack. Make stack implement the Iterable interface.

Iterable: has a method that returns an Iterator

Iterator: has methods hasNext() and next()

public interface Iterable<Item>
{
Iterator<Item> iterator();
}

public interface Iterator<Item>
{
boolean hasNext();
Item next();
// void remove();
}
// foreach statement(shorthand)
for (String s : stack)
StdOut.println(s);


Iterator in linked-list

import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>
{
...
public Iterator<Item> iterator()
{ return new ListIterator(); }

private class ListIterator implements Iterator<Item>
{
private Node current = first;

public boolean hasNext()
{ return current != null; }
public void remove()
{ /* not supported */ }
public Item next()
{
Item item = current.item;
current = current.next;
return item;
}
}
}


Array iterator

import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>
{
...
public Iterator<Item> iterator()
{ return new ReverseArrayIterator(); }

private class ReverseArrayIterator implements Iterator<Item>
{
private int i = N;

public boolean hasNext()
{ return i > 0; }
public void remove()
{/* not supported */ }
public Item next()
{ return s[--i];    }

}
}


### bag API

Adding items to a collection and iterating (order doesn’t matter)
Implementation: Stack without pop or queue without dequeue.

• Bag(): create an empty bag
• void add(Item x): insert a new item onto bag
• int size(): number of items in the bag
• Iterable<Item> iterator(): iterator for all items in bag

## applications

dangerous to use unfamiliar library.

java.util.list

java.util.Stack

java.util.Queue


Dijkstra’s two stack algorithm

# elementary sorts

## sorting introduction

Goal: sort any type of data (Double, String or java.io.File), without any information about the type of an item’s key.

Use callback = reference to executable code.

• client passes array of objects to sort() function
• the sort function calls back object’s compareTo() method as needed.

Call back implementation

• Java: interfaces
• C: function pointers
• C++: class-typle functions
• python, Javascript: first-class functions
// client
...
Insertion.sort(files);
...
// object implementation
public class File implements Comparable<File>
{
public int compareTo(File b) {...}
}
// sort implementation
public static void sort(Comparable[] a)
{
...
if (a[i].compareTo(a[j-1]) < 0 )
...
}


### comparable API

Implement compareTo() so that v.compareTo(w):

• is a total order
• returns a negative integer, zero or positive integer
• throw an exception if incompatible types(or either is null)

### example

public class Date implements Comparable<Date>
{
private final int month, day, year;
public Date(int m, int d, int y)
{
month = m;
day = d;
year = y;
}
public int compareTo(Date that)
{
if (this.year < that.year ) return -1;
if (this.year > that.year ) return +1;
if (this.month < that.month) return -1;
if (this.month > that.month) return +1;
if (this.day < that.day ) return -1;
if (this.day > that.day ) return +1;
return 0;
}
}


### two useful functions

// less
private static boolean less(Comparable v, Comparable w)
{ return v.compareTo(w) < 0; }
// exchange
private static void exch(Comparable[] a, int i, int j)
{
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}


## selection sort

1. In iteration i, find index min of smallest remaining entry.
2. Swap a[i] and a[min]

Quadratic time $$\sim N^2/2$$

int N = a.length;
for (i = 0; i<N; i++)
{
int min = i;
for (j = i+1；j<N; j++)
{
if (less(a[j],a[i])
min = j;
}
exchange(a, min, i);
}



## insertion sort

1. In iteration i, swap a[i] with each larger entry to its left.

Best case: linear， linear for partially-sorted arrays;
Worst case: $$\sim N^2/2$$ but slower than selection sort

int N = a.length;
for (int i = 0; i < N; i++)
for (int j = i; j > 0; j--)
if (less(a[j], a[j-1]))
exch(a, j, j-1);
else break;


## shellsort

Move entries more than one position (h positions) at a time by h-sorting the array.

### h-sorting

Insertion sort, with stride length h
h is an increment number like 7, 4, 1
A hm-sorted array remains hm-sorted after hn-sorted it.

### increment sequence

$$3x+1$$
Sedgewick: 1,5,19,41,109,209…

### code

worse case: $$O(N^{3/2})$$

int h = 1;
while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, ...

while (h >= 1)
{ // h-sort the array.
for (int i = h; i < N; i++)
{
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
exch(a, j, j-h);
}
h = h/3;
}


## shuffling

• generate a random real number for each array entry
• sort the array

Goal: rearrange array so that results is a uniformly random permutation in linear time.

### Knuth shuffle

• in iteration i, pick integer r between 0 and i uniformly at random
• swap a[i] and a[r]
int N = a.length;
for (i = 0; i < N; i++)
{
int r = StdRandom.uniform(i+1); // [0,i)
exch(a,i,r);
}


## convex hull

The convex hull of a set of N points it the smallest perimeter fence enclosing the points.
Output: sequence of vertices in counterclockwise order.

### Graham scan

1. choose point p with smallest y-coordinate
2. sort points by polar angle with p
3. consider points in order; discard unless it create ccw turn

challenges:

1. Find point p with smallest y-coordinate:
Define a total order, comparing by y-coordinate
2. Sort points by polar angle with respect to p
Define a total order for each point p
3. Determine whether $$p_1 \rightarrow p_2 \rightarrow p_3$$ is a counterclockwise turn
Computational geometry
4. sort efficiently
Mergesort in $$N\log N$$ time
5. handle degeneracies(three or more points on a line)
Require care, but not hard

### ccw

for 3 points a, b, c, signed area $$Area(a,b,c)$$:
$2\times Area(a,b,c) = \left\vert \begin{array}{ccc} a_{x} & a_{y} & 1 \\ b_{x} & b_{y} & 1\\ c_{x} & c_{y} & 1 \end{array} \right\vert = (b_x -a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x)$

• Area > 0: $$a \rightarrow b \rightarrow c$$ is counterclockwise
• Area < 0: $$a \rightarrow b \rightarrow c$$ is clockwise
• Area = 0: $$a \rightarrow b \rightarrow c$$ is collinear

### code

Arrays.sort(p, Point2D.Y_ORDER);
Arrays.sort(p, p.BY_POLAR_ORDER);

hull.push(p);
hull.push(p);

for (i = 2; i<N; i++)
{
Point2D top = hull.pop;
while (Point2D.ccw(hull.peek(), top, p[i]) <= 0 )
top = hull.pop;
hull.push(top);
hull.push(p[i]);
}