6栈（如何实现浏览器的前进和后退）

时间：2019-03-25 10:41:56 阅读：171 评论：0 收藏：0 [点我收藏+]

我们可以用栈实现浏览器的前进后退功能

那么栈又是什么？

栈就像一叠盘子，从下一个一个往上放。后进先出，先进后出，就是典型栈的结构。

从操作特性上来看，栈是十分受限制的一种数据结构，只有一端能够操作，但因为只暴露了一端的操作接口，便不容易出错，更可控。因此当数据集合满足先进后出，后进先出的特点时，就应该选择栈。

顺序栈：用数组实现的栈

链式栈：用链表实现的栈

Java实现的顺序栈：

 1  // 基于数组实现的顺序栈
 2         public class ArrayStack {
 3           private String[] items;  // 数组
 4           private int count;       // 栈中元素个数
 5           private int n;           // 栈的大小
 6         
 7           // 初始化数组，申请一个大小为 n 的数组空间
 8           public ArrayStack(int n) {
 9             this.items = new String[n];
10             this.n = n;
11             this.count = 0;
12           }
13         
14           // 入栈操作
15           public boolean push(String item) {
16             // 数组空间不够了，直接返回 false，入栈失败。
17             if (count == n) return false;
18             // 将 item 放到下标为 count 的位置，并且 count 加一
19             items[count] = item;
20             ++count;
21             return true;
22           }
23           
24           // 出栈操作
25           public String pop() {
26             // 栈为空，则直接返回 null
27             if (count == 0) return null;
28             // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
29             String tmp = items[count-1];
30             --count;
31             return tmp;
32           }
33         }

不管顺序栈还是链表栈，存储数据是只需要一个大小为n的数组就够了，而出栈入栈的操作，只需要一两个临时变量空间，因此空间复杂度为O(1)。

这里要注意，空间复杂度并不是指原本存储数据的空间，而是指算法执行时还需要额外的存储空间。

出栈入栈的时间复杂度均为O(1)。

支持动态扩容的顺序栈

前面讲的数组若要实现动态扩容便是将数组数据复制到更大的内存去，对于动态扩容的顺序栈，我们只需要底层是一个动态扩容的数组。

对于动态扩容的数组平时开发用到不多，但我们主要对其进行复杂度分析。

它出栈复杂度都是O(1)。

对于入栈(push)，最好情况时间复杂度是O(1),最坏时间复杂度是O(n)。那么它的均摊时间复杂度是多少呢？

便于分析假设

栈空间不够时，重新申请原来两倍大小的空间。
没有出栈操作
不涉及内存搬移的入栈操作为simple_push，时间复杂度为O(1)。

假设当前栈大小为K，若栈已满，push需要申请两倍内存，并进行K个数据搬移，再进行push,操作复杂度为O(K)。但有2K的空间后，接下来K-1次push都为simple-push，时间复杂度为O(1)。如果还有push，再次循环下去。

讲需要数据搬移的push均摊下到k-1次的simple的入栈，便可知push的均摊时间复杂度为O(1)。

栈在函数调用的应用

操作系统给每个线程分配了一块独立的内存空间，这个内存会被组织成”栈”，用来存放临时变量。

 1 int main() {
 2            int a = 1; 
 3            int ret = 0;
 4            int res = 0;
 5            ret = add(3, 5);
 6            res = a + ret;
 7            printf("%d", res);
 8            reuturn 0;
 9         }
10         
11         int add(int x, int y) {
12            int sum = 0;
13            sum = x + y;
14            return sum;
15         }
16