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

double

发布于 2018-07-31 17:43:53

4530

发布于 2018-07-31 17:43:53

文章被收录于专栏：算法channel算法channel

程序员必看

回顾

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

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

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

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

栈的核心问题

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

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

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

栈的数组实现

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

代码实现

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}

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

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

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

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

代码实现

重点理解 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        return new ReverseArrayIterator();
51    }
52
53    // an iterator, doesn't implement remove() since it's optional
54    private class ReverseArrayIterator implements Iterator<String> {
55        private int i = n-1;
56        public boolean hasNext()  { return i >= 0;                              }
57        public void remove()      { throw new UnsupportedOperationException();  }
58
59        public String next() {
60            if (!hasNext()) throw new NoSuchElementException();
61            return items[i--];
62        }
63    }
64
65
66
67   /***************************************************************************
68    * Test routine.
69    ***************************************************************************/
70    public static void main(String[] args) {
71        ResizingArrayStackOfStrings stack = new ResizingArrayStackOfStrings();
72        while (!StdIn.isEmpty()) {
73            String item = StdIn.readString();
74            if (!item.equals("-")) stack.push(item);
75            else if (!stack.isEmpty()) StdOut.print(stack.pop() + " ");
76        }
77        StdOut.println("(" + stack.size() + " left on stack)");
78    }
79}

总结

以上总结了栈的两种基本实现方法，都是借助数组实现，一种是静态的，另一种可以动态扩容。这是最基本的实现思路，可以仔细体会下，能写出这些代码来，如果在面试中问到栈的知识，告诉面试官这些东西，会给你加不少分。

基于数组实现的栈结构都不是理想的，因为动态扩容时，每次都要复制老元素到新的位置上，这是耗费时间的。有没有更高效的实现方法呢？

请看接下来的推送。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-07-15，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法