|
1 | | -~ todo |
| 1 | +# 栈：一吃多就会吐的家伙~ |
| 2 | + |
| 3 | +## 前言 |
| 4 | + |
| 5 | +前两篇文章中我们学习了线性表中的数组和链表，数组和链表是最基础的数据结构，很多数据结构的实现都是基于数据或链表的。那么今天我们一起学习一个非常简单的数据结构—**栈**。栈使用是非常广泛的，比如我们Java中函数的调用、浏览器中的前进与后退功能等都会用到栈。 |
| 6 | + |
| 7 | +## 什么是栈 |
| 8 | + |
| 9 | +先画张图，看看栈长什么样。如下图所示： |
| 10 | + |
| 11 | + |
| 12 | + |
| 13 | +从图中看到栈是有些特殊，对于栈的操作被限制只能在栈的一端（栈顶）进行，也就是不允许在栈的中间进行数据操作，只能在栈顶进行数据操作（也就是插入和删除数据）。 |
| 14 | + |
| 15 | +> 思考：“受限制”的栈有什么用呢？ |
| 16 | +
|
| 17 | +特定的数据结构肯定有其特定的使用场景，相比于数组或者链表而言，栈虽然没有怎么灵活（只能在栈的一端进行数据操作），但是对于新增或者删除数据的时候，因为栈只涉及到一端，效率肯定不低。 |
| 18 | + |
| 19 | +如何去理解栈呢？其实也非常简单，一句话可以概况栈的特性：**先进后出**，俗称“**吃多了吐**”。哈哈~ |
| 20 | + |
| 21 | +## 栈的基本操作 |
| 22 | + |
| 23 | +栈有不同的实现方式，基于数组实现的栈，被叫做**顺序栈**。基于链表实现的栈，被叫做**链式栈**。不管用什么方式实现的栈，其原理都是一样的，不用担心！ |
| 24 | + |
| 25 | +栈的操作主要就两个：入栈（push）和出栈（pop）。 |
| 26 | + |
| 27 | +- 顺序栈 |
| 28 | + |
| 29 | +下面我们先基于数组来实现一个顺序栈，代码如下： |
| 30 | + |
| 31 | +```java |
| 32 | +public class MyStack<E> { |
| 33 | + private Object[] data = null; // 数组 |
| 34 | + private int maxSize = 0; //栈容量 |
| 35 | + private int top = -1; //栈顶指针 |
| 36 | + |
| 37 | + // 初始化构造方法 |
| 38 | + MyStack(int initialSize) { |
| 39 | + if (initialSize >= 0) { |
| 40 | + this.maxSize = initialSize; |
| 41 | + data = new Object[initialSize]; |
| 42 | + top = -1; |
| 43 | + } else { |
| 44 | + throw new RuntimeException("初始化大小不能小于0: " + initialSize); |
| 45 | + } |
| 46 | + } |
| 47 | + |
| 48 | + // 初始化构造方法 默认栈容量为10 |
| 49 | + public MyStack() { |
| 50 | + this(10); |
| 51 | + } |
| 52 | + |
| 53 | + //入栈操作 |
| 54 | + public boolean push(E e) { |
| 55 | + //首先判断一下栈是否已经满了 |
| 56 | + if (top == maxSize - 1) { |
| 57 | + // 扩容 |
| 58 | + resize(); |
| 59 | + } |
| 60 | + data[top] = e; |
| 61 | + top++; |
| 62 | + return true; |
| 63 | + } |
| 64 | + |
| 65 | + //出栈操作 |
| 66 | + public E pop() { |
| 67 | + //首先查看一下栈是否为空 |
| 68 | + if (top == -1) { |
| 69 | + throw new RuntimeException("栈为空"); |
| 70 | + } else { |
| 71 | + //将栈顶元素返回后维护一下栈顶指针 |
| 72 | + return (E) data[top--]; |
| 73 | + } |
| 74 | + } |
| 75 | + |
| 76 | + //查看栈顶元素 |
| 77 | + public E peek() { |
| 78 | + if (top == -1) { |
| 79 | + throw new RuntimeException("栈为空"); |
| 80 | + } else { |
| 81 | + // 查看栈顶元素并不移除所以说不需要维护栈顶指针 |
| 82 | + return (E) data[top]; |
| 83 | + } |
| 84 | + } |
| 85 | + |
| 86 | + // 查看栈是否为空 |
| 87 | + public boolean isEmpty() { |
| 88 | + return maxSize == 0; |
| 89 | + } |
| 90 | + |
| 91 | + // 扩容操作 |
| 92 | + public void resize() { |
| 93 | + // 创建一个新数组 |
| 94 | + Object[] newArray = new Object[data.length * 2]; |
| 95 | + System.arraycopy(data, 0, newArray, 0, data.length); |
| 96 | + data = newArray; |
| 97 | + } |
| 98 | + |
| 99 | + |
| 100 | +} |
| 101 | + |
| 102 | +``` |
| 103 | + |
| 104 | +在顺序栈中，数组的第一个元素最为栈底，最后一个元素最为栈顶。当top=-1的时候，此时栈为空。 |
| 105 | + |
| 106 | +每当新增数据入栈push的时候，maxSize加一，同理删除元素出栈pop的时候，maxSize减一。因为是基础数组的实现，所以顺序栈会涉及一个扩容的情况。 |
| 107 | + |
| 108 | +- 链式栈 |
| 109 | + |
| 110 | +我们再来看看基于链表来实现一个链式栈，代码如下： |
| 111 | + |
| 112 | +```java |
| 113 | +public class MyStack<E> { |
| 114 | + StackNode<E> top = null; //栈顶 |
| 115 | + |
| 116 | + private class StackNode<E>{ |
| 117 | + E data; |
| 118 | + StackNode next; |
| 119 | + StackNode(E data) { |
| 120 | + this.data=data; |
| 121 | + } |
| 122 | + } |
| 123 | + |
| 124 | + /** |
| 125 | + * 入栈 |
| 126 | + * 首先将要push的数据的next赋值为栈顶top |
| 127 | + * 然后将栈顶指针指向新push进来的节点 |
| 128 | + * @param data |
| 129 | + */ |
| 130 | + public void push(E data) { |
| 131 | + StackNode<E> newNode = new StackNode<E>(data); |
| 132 | + newNode.next = top; |
| 133 | + top = newNode; |
| 134 | + } |
| 135 | + |
| 136 | + /** |
| 137 | + * 出栈 |
| 138 | + * @return |
| 139 | + */ |
| 140 | + public E pop() { |
| 141 | + if(this.isEmpty()) { |
| 142 | + throw new RuntimeException("栈为空"); |
| 143 | + } |
| 144 | + E data = top.data; |
| 145 | + top = top.next; |
| 146 | + return data; |
| 147 | + } |
| 148 | + |
| 149 | + /** |
| 150 | + * 查看栈顶元素 |
| 151 | + * @return |
| 152 | + */ |
| 153 | + public E peek() { |
| 154 | + if(isEmpty()) { |
| 155 | + throw new RuntimeException("栈为空"); |
| 156 | + } |
| 157 | + return top.data; |
| 158 | + } |
| 159 | + |
| 160 | + // 判断栈是否为空 |
| 161 | + public boolean isEmpty() { |
| 162 | + return top == null; |
| 163 | + } |
| 164 | +} |
| 165 | +``` |
| 166 | + |
| 167 | +在链式栈中，单链表的头部最为栈顶，因为栈的特性是先进后出，所以不需要头节点的。每当新增数据入栈push的时候，需要让新的结点指向原栈顶，然后再让top指向新增的这个结点。同理删除元素出栈pop的时候，只需要栈顶的 top 指向栈顶元素的 next 指针即可完成删除。 |
| 168 | + |
| 169 | +## 总结 |
| 170 | + |
| 171 | +栈作为一个受限制的线性表，只允许对栈顶的数据进行操作，也就是所谓的：先进后出，后进先出。不管是顺序栈还是链式栈，新增或者删除数据时都只能在栈顶进行，故时间复杂度都是O(1)，查找数据的时候都需要进行全局遍历，故时间复杂度都是O(n)。顺序栈基于数组实现，初始化时大小便已经固定，后续需要考虑扩容的情况，而链式栈基于链表实现，不需要考虑扩容。 |
0 commit comments