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[1]; }

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[0].BY_POLAR_ORDER);  

hull.push(p[0]);
hull.push(p[1]);

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]);
}