算法笔记二

Stack

Implement

• use Linkedlist
• use Array

Tradeoffs: Array VS Linkedlist

• Linkedlist
  • Every operation takes constant time in the worst case.
  • Uses extra time and space to deal with links.

• Array
  • Every operation takes constant amortized time.
  • Less wasted space.

public class StackOfStrings{

    StackOfStrings()

    void push(String item)

    String pop()

    boolean isEmpty()

    int size()
}

public class LinkedStackOfStrings{
    private Node first = null;

    private class Node{
        String item;
        Node next;
    }

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

    public void push(String item){
        Node oldfirst = first;
        first = new Node;
        first.item = item;
        first.next = oldfirst;
    }

    public String pop(){
        String item = first .item;
        first = first.next;
        return item;
    }
}

public class FixedCapacityStackOfStrings{
    private String[] s;
    private int N = 0;

    public FixedCapacityStackOfStrings(int capacity){
        s = new String[capacity];
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public void push(String item){
        s[N++] = item;
    }

    public String pop(){
        return s[--N];
    }
}

Overflow and Underflow

• Underflow : throw exception if pop from an empty stack
• Overflow : use resizing array for array implementation

Null items: We allow null items to be inserted.

Loitering: Holding a reference to an object when it is no longer needed.

public String pop(){
    String item = s[--N];
    s[N] = null;
    return item;
}

Problem How to grow and shrink array

• push(): increse by 1 too enpensive O(N^2)
• pop() : decrese by 1 too expensive

//grow
public ResizingArrayStackOfStrings(){
    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(int i=0;i<N;i++){
        copy[i] = s[i];
    }
    s = copy;
}

how to shrink array

First try

• push(): double size of array s[] when array is full
• pop():halve size of array[] when array is one-half full

Too expensive in worst case

• Consider push-pop-push-pop-… sequence when array is full.
• Each operation takes time proportional to N.

Efficient solution

• push(): double size of array s[] when array is full
• pop(): halve size of array s[] when array is one-quarter full

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

Invariant: Array is between 25% and 100% full.

Queue

public class QueueOfStrings{

    QueueOfStrings()

    void enqueue(String item)

    String dequeue()

    boolean isEmpty()

    int size()
}

public class LinkedQueueOfStrings{
    private Node first,last;

    private class Node{ // inner class
        String item
        Node next;
    }

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

    public void enqueue(String item){
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if(isEmpty()) 
            first = last;
        else
            oldlast.next = last;
    }

    public String dequeue(){
        String item = first.item;
        first = first.next;
        if(isEmpty())
            last = null;
        return item;
    }
}

Generics

• String 类型的队列和栈

• 其他类型的 StackOfURLs,StackOfInts,StackOfVans.

public class Stack<Item>{
    private Node first = null;  //Item : generic type name

    private class Node{
        Item item;
        Node next;
    }

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

    public void push(Item item){
        Node oldfirst = first;
        first = new Node;
        first.item = item;
        first.next = oldfirst;
    }

    public Item pop(){
        Item item = first .item;
        first = first.next;
        return item;
    }
}

public class FixedCapacityStackOf<Item>{
    private Item[] s;
    private int N = 0;

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

    public boolean isEmpty(){
        return N == 0;
    }

    public void push(Item item){
        s[N++] = item;
    }

    public Item pop(){
        return s[--N];
    }
}

• 自动装箱 primitive type -> object type

• Syntactic Sugar (糖衣语法2333):计算机语言中添加的某种语法，这种语法对语言的功能并没有影响，但是更方便程序员使用。通常来说使用语法糖能够增加程序的可读性，从而减少程序代码出错的机会。

Stack<Integer> s = new Stack<Integer>();
s.push(17);           //s.push(new Integer(17));
int a = s.pop();      //int a = s.pop().intValue();

• Bottom Line(要旨，基本论点,底价): Client code can use generic stack for any type of data.

Iterators

• Iterable has s method that returns an Iterator.

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

• Iterator has methods hasNext() and next()

public interface Iterator<Item>{
    boolean hasNext();
    Item next();
    void remove(); //optional :use at your own risk
}

• Iterable :Java supports elegant client code.
  • foreach statement(shorthand)
  • equivalent code(longhand)

for(String s:stack){
    StdOut.println(s)
}

Iterator<String> i = stack.iterator();
while(i.hasNext()){
    String s = i.next();
    StdOut.println(s);
}

Stack iterator:linked-list implementation

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 = null;

        public boolean hasNext(){
            return current != null;
        }

        public void remove(){
            /* not supported */
        }

        public Item next(){
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

Stack iterator:array implementation

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 support */
        }

        public Item next(){
            return s[--i];
        }
}

Bag

• Main application. Adding items to a collection and iterating (when oeder doesn’t matter)
• Implementation. Stack(without pop) or queue(without dequeue)

public class Bag<Item> implements Iterable<Item>{
    Bag()
    
    void add(Item x)

    int size()

    Iterable<Item> iterator()

}

Application

未完待续…