VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > Python基础教程 >

  • 程序员必看：实现栈有这两种策略，有完整分析和代码实现

程序员必看

1
回顾

普林斯顿大学的程序员必知的算法和数据结构已经推送两篇：

1. 程序员必知的算法和数据结构：2500字性能总结

2. 1800字普林斯顿大学课程浓缩笔记：程序员必知的算法之查找和排序算法

 

这两篇中分别总结了程序的时间性能度量指标，典型的时间复杂度类型，Java中类型的空间消耗的量化情况。后一篇考虑计算机中最重要的基础算法查找和排序算法，这篇可以说是浓缩篇，虽只有1800字，但是绝对的精华。

 

2
栈的核心问题

今天来认识一对非常重要的数据结构：栈(stack)和队列(queue)，分为两篇，接下来另一篇推送队列。

 

相比大家对栈(stack)的基本知识都已经了解了，我们在此直接进入核心问题：栈这个数据结构和行为是怎么实现的？

 

首先认识一下，栈的基本行为，基本包括如下四个方法：

 

 

3
栈的数组实现

用数组表示栈结构是最简单的主意，维护一个实例变量 n， 表示栈中元素的个数；维护一个数组 items[] 存储 n 个元素，栈顶元素存储在 items[n-1] , 栈底元素存储在 items[0]. 这种存储策略方便地实现了栈的后进先出性质。

 

 

4
代码实现

ArrayStackOfStrings 的代码实现包括继承可迭代接口，编写4个基本方法，都很简洁，内部借助数组和个数，内部类 ReverseArrayIterator 实现可迭代接口。

 1import java.util.Iterator;
 2import java.util.NoSuchElementException;
 3   //继承可迭代接口
 4public class ArrayStackOfStrings implements Iterable<String> {
 5    private String[] items;  // 内部存储数组
 6    private int n;           // 栈内元素个数
 7
 8    public ArrayStackOfStrings(int capacity) {
 9        items = new String[capacity];
10    }
11
12    public boolean isEmpty() {
13        return n == 0; 
14    }
15
16    public boolean isFull() {
17        return n == items.length; 
18    }
19
20    public void push(String item) {
21        items[n++] = item; //直接在数组最后添加元素
22    }
23
24    public String pop() {
25        return items[--n]; //直接在数组最后移除元素
26    }
27
28    public Iterator<String> iterator() {
29        return new ReverseArrayIterator();
30    }
31
32    // 自定义的迭代器，不实现Remove接口
33    private class ReverseArrayIterator implements Iterator<String> {
34        private int i = n-1;
35        public boolean hasNext()  { return i >= 0; }
36        public void remove()      { throw new UnsupportedOperationException();  }
37           //可以看出栈的遍历是从索引n-1开始
38        public String next() {
39            if (!hasNext()) throw new NoSuchElementException();
40            return items[i--];
41        }
42    }
43
44       //测试
45    public static void main(String[] args) {
46        int capacity = Integer.parseInt(args[0]);
47        ArrayStackOfStrings stack = new ArrayStackOfStrings(capacity);
48        while (!StdIn.isEmpty()) {
49            String item = StdIn.readString();
50            if (!item.equals("-")) {
51                stack.push(item); 
52            }
53            else {
54                StdOut.print(stack.pop() + " ");
55            }
56        }
57        StdOut.println();
58    } 
59} 

 

5
能动态扩容的栈的实现方法

 

上面实现方法数组个数，即容量写死了，所以一旦数组个数超过容量，将会抛出异常。

 

为了实现数组元素个数的动态扩容，本方法实现的功能即可做到。

 

相比上面方法，此方法在 push 时候，考虑是否容积足够，如果不够，则开辟元素个数加倍的空间。相似的，如果 pop 时候，如果容积够大，对容积减半。

 

 

6
代码实现

 

重点理解 resize()函数，做的事情不仅个数加倍，还要copy原来的元素到新的内存区域，因此此处效率不高。

 1import java.util.Iterator;
 2import java.util.NoSuchElementException;
 3
 4public class ResizingArrayStackOfStrings implements Iterable<String> {
 5    private String[] items;     // 同上
 6    private int n = 0;          // 同上
 7
 8    // create an empty stack
 9    public ResizingArrayStackOfStrings() {
10        items = new String[2]; //开始初始容积为2
11    }
12
13    public boolean isEmpty() {
14        return n == 0;
15    }
16
17    public int size() {
18        return n;
19    }
20
21
22    // resize the underlying array holding the elements
23    private void resize(int capacity) {
24        assert capacity >= n;
25        String[] temp = new String[capacity];
26        for (int i = 0; i < n; i++)
27            temp[i] = items[i];
28        items = temp;
29    }
30
31    // push a new item onto the stack
32    public void push(String item) {
33        if (n == items.length) resize(2*items.length);  // double array length if necessary
34        items[n++] = item;                              // add item
35    }
36
37    // delete and return the item most recently added
38    public String pop() {
39        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
40        String item = items[n-1];
41        items[n-1] = null;        // to avoid loitering
42        n--;
43        // shrink size of array if necessary
44        if (n > 0 && n == items.length/4) resize(items.length/2);
45        return item;
46    }
47
48
49    public Iterator<String> iterator() {
50