本文记录java中栈（集合类数据类型）的实现。使用java中的数组实现，要有数据类型通用性，栈的大小可调整，能够迭代。

实现描述

  • 数据类型是泛型
  • 使用数组实现，数组大小可变

  • 具有迭代性(集合类数据类型的基本操作之一就是能够使用java的foreach语句通过迭代遍历并处理集合中的每个元素)

    1. 集合数据类型必须实现一个iterator()方法并返回一个Iterator对象。
    2. Iterator类必须包含两个方法：hasNext()(返回一个布尔值)和next()(返回集合中的一个泛型元素)。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Iterator;
public interface Iterable<item> {
  Iterator<Item> iterator();
}

// 下面这个相当于 java.util.Iterator
// pulic interface Iterator<Item> {
//   boolean hasNext();
//   Item next();
//   void remove();
// }

public class ResizingArrayStack<Item> implements Iterable<Item> {
  private Item[] a = (Item[]) new Object[1];
  private int N = 0;
  public boolean isEmpty() {
    return N == 0;
  }
  public int size() {
    return N;
  }
  private void resize(int max) {
    Item[] temp = (Item[]) new Object[max];
    for (int i = 0; i < N; i++) {
      temp[i] = a[i];
    }
    a = temp;
  }
  public void push(Item item) {
    if (N == a.length) {
      resize(2 * a.length);
    }
    a[N++] = item;
  }
  public Item pop() {
    Item item = a[--N];
    a[N] = null;
    if (N > 0 && N == a.length / 4) {
      resize(a.length / 2);
    }
    return 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 Item next() {
      return a[--i];
    }
    public void remove() {

    }
  }
}

上述实现的特性

满足上述描述的实现几乎达到了任意集合类数据类型的实现的最佳性能：

  • 每项操作的用时都与集合大小无关
  • 空间需求总是不超过集合大小乘以一个常数

参考

  • 《算法》p86-p88