下压栈(LIFO)

算法1.1 可动态调整数组大小的实现

  1. public class ResizingArrayStack<Item> implements Iterable<Item> {
  2.     private Item[] a = (Item []) new Object[1];//元素栈
  3.     private int N;//元素个数
  5.     public boolean isEmpty() {
  6.         return N == 0;
  7.     }
  9.     public int size() {
  10.         return N;
  11.     }
  13.     private void resize(int max) {
  14.         Item[] temp = (Item []) new Object[max];
  15.         for(int i = 0; i < max; i++) {
  16.             temp[i] = a[i];
  17.         }
  18.         a = temp;
  19.     }//调整数组大小
  21.     public void push(Item item) {
  22.         if(N == a.length) resize(2*a.length);
  23.         a[N++] = item;
  24.     }//添加元素到栈顶
  26.     public Item pop() {
  27.         Item item = a[--N];
  28.         a[N] = null;//防止对象游离
  29.         if(N > 0 && N == a.length/4) resize(a.length/2);
  30.         return item;
  31.     }//从栈顶删除元素
  33.     @Override
  34.     public Iterator<Item> iterator() {
  35.         return new ReverseArrayIterator;
  36.     }
  38.     private class ReverseArrayIterator implements Iterator<Item> {
  39.         private i = N;
  40.         @Override
  41.         public boolean hasNext() {
  42.             return i > 0;
  43.         }
  44.         @Override
  45.         public Item next() {
  46.             return a[--i];
  47.         }
  48.         @Override
  49.         public void remove() {}
  50.     }
  51. }

要点

  1. 可变数组下压栈的主类和内部类需要分别实现Iterable,Iterator接口,从而实现LIFO逆序迭代,否则会按照数组FIFO迭代;
  2. algs4书中对于remove()总为空,避免在迭代中穿插修改数据结构的操作
  3. 为保证数组缩减后有一半的空间利用率,判断条件应该是N == a.length/4
  4. 删除栈顶元素时,实际上被弹出元素的引用仍保存在数组中,但该元素永远不会被访问,直到下次push()后,原有引用指向新元素.Java垃圾收集器才会回收空间,期间造成空间浪费,使用a[N] = null避免元素游离.

特点

  1. 算法1.1的每项操作用时与集合大小无关:操作始终只针对栈顶元素;
  2. 空间需求总是不超过集合大小乘一个常数;
  3. 栈永远不会溢出,使用率也不会低于四分之一,除非栈为空时,数组大小为1;

算法1.2 链表实现

  1. import edu.princeton.cs.algs4.StdIn;
  2. import edu.princeton.cs.algs4.StdOut;
  4. import java.util.Iterator;
  6. public class Stack<Item> implements Iterable<Item> {
  7.     private Node first;
  8.     private int N;
  9.     private class Node {
  10.         Item item;
  11.         Node next;
  12.     }
  14.     public boolean isEmpty(){ return N == 0;}
  15.     public int size(){ return N; }
  17.     public void push(Item item){
  18.         Node oldFirst = first ;
  19.         first = new Node();
  20.         first.item = item;
  21.         first.next = oldFirst;
  22.         N++;
  23.     }
  25.     public Item pop(){
  26.         Item item;
  27.         item = first.item;
  28.         first = first.next;
  29.         N--;
  30.         return item;
  31.     }
  33.     @Override
  34.     public Iterator<Item> iterator(){
  35.         return new ListIterator();
  36.     }
  38.     private class ListIterator implements Iterator<Item>{
  39.         private Node current = first;
  40.         @Override
  41.         public boolean hasNext(){ return current != null;}
  42.         @Override
  43.         public Item next(){
  44.             Item item = current.item;
  45.             current = current.next;
  46.             return item;
  47.         }
  48.         @Override
  49.         public void remove(){}
  50.     }
  51. }

要点

  1. 实例变量:头结点first
  2. 完成内部类Node;
  3. isEmpty()可以判断N == 0或first == null;
  4. 迭代实现同上

特点

  1. 可以处理任意类型数据;
  2. 所需空间总是和集合大小成正比;
  3. 操作所需时间和集合大小无关(链式结构);

关于内部类实现泛型接口*

算法内部类
  1. private class ListIterator implements Iterator<Item>{}
  2. //不是private class ListIterator<Item> implements Iterator<Item>

算法外部类
  1. public class Stack<Item> implements Iterable<Item>

当类实现泛型接口时，不能确定接口中的泛型,这时就要求这个类也必须定义泛型，而且泛型名称要一致,因此主类Stack后也要定义泛型;当内部类实现和主类泛型类型一致的接口(本算法中),此时泛型已经可以由主类的定义判断,则内部类的泛型无需在定义泛型,如果重复定义会提示错误.