我们会介绍两个全新的线性数据结构，栈与队列。
栈Stack
栈也是一种线性结构;相比数组，栈对应的操作是数组的子集;只能从一端添加元素，也只能从一端取出元素(这一端称之为栈顶)
添加元素和取出元素都只能从栈顶位置开始存取。栈是一种后进先出的数据结构。Last ln First Out (LIFO);
在计算机的世界里，栈拥有着不可思议的作用
栈的应用: 无处不在的Undo操作(撤销)
- 比如你打字: 沉迷学习无法自拔，然后将无法打成不法。
撤销就是将这个不法出栈，然后将后续的正确字都入栈。
- 程序调用的系统栈(对于理解递归有作用)
函数A运行到一半，调用函数B; B运行到一半，调用函数C;
A2指函数A运行到了第二行，B2指函数B运行到了第二行。当函数C顺序执行完毕之后，该执行哪一个函数呢，拿出栈顶B2继续执行。
当B函数执行完毕之后，拿出栈顶A2，执行A函数，执行完之后，发现栈为空，整个程序执行完毕。
子过程，子逻辑的调用，对于理解递归有作用。
栈的实现
Stack<E>
void push(E e); // 向栈中加入元素
E pop(); // 弹出栈顶元素
E peek( ); // 查看栈顶元素
int getSize(); // 获取栈中元素个数
boolean isEmpty(); // 判断栈是否为空
从用户的角度看，支持这些操作就好。具体底层实现，用户不关心，实际底层有多种实现方式。
Interface Stack<E> implement ArrayStack<E>
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
将我们栈中的常用方法作为一个接口，然后让我们上次实现的动态数组来实现这个接口。
/**
* 获取数组最后一个元素(方便我们的栈实现)
*
* @return
*/
public E getLast(){
return get(size-1);
}
/**
* 获取数组第一个元素
*
* @return
*/
public E getFirst(){
return get(0);
}
为Array添加两个方法方便我们的栈实现。
package cn.mtianyan;
public class ArrayStack<E> implements Stack<E> {
Array<E> array;
public ArrayStack(int capacity){
array = new Array<>(capacity);
}
public ArrayStack() {
array = new Array<>();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop() {
return array.removeLast();
}
@Override
public E peek() {
return array.getLast();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack ：");
res.append("[ ");
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize()-1){
res.append(", ");
}
}
res.append("] top");
return res.toString();
}
}
栈的设计中，用户只关注栈顶元素存取和栈长度。因此不需要提供其他对外方法。
package cn.mtianyan;
public class ArrayStackTest {
public static void main(String[] args) {
ArrayStack<Integer> arrayStack = new ArrayStack<>();
for (int i = 0; i < 5; i++) {
arrayStack.push(i);
System.out.println(arrayStack);
}
arrayStack.pop();
System.out.println(arrayStack);
}
}
运行结果:
栈的复杂度分析
ArrayStack<E>
void push(E e) // O(1) 均摊
E pop() // O(1) 均摊
E peek() // O(1)
int getSize() // O(1)
boolean isEmpty() // O(1)
这里的push和pop操作在最后面进行，有可能触发resize，但均摊来算是O(1)的。
栈的应用
undo操作-编辑器; 系统调用栈-操作系统;
应用: 括号匹配 - 编译器 LeetCode 问题(leetcode-cn.com) 美版的功能更丰富
https://leetcode-cn.com/problems/valid-parentheses/description/
许多公司真实的面试题。
栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素
只要是左侧的括号，就压入栈内。
如上图所示，只要是左侧就压入栈。面对字符时右括号，开始查看当前栈顶元素是否可以和该右括号匹配，匹配则出栈。
直到所有字符扫描完毕，栈为空则匹配成功。
失败的例子:
左侧括号全部入栈后，遇到的右括号无法和栈顶匹配,匹配失败。Leetcode会生成相应的语言的答题模板
class Solution {
public boolean isValid(String s) {
}
}
这一小节我们使用import java.util.Stack;,但实际我们自己编写的Stack和java中的这个接口是一致的，下节课教大家在LeetCode用我们自己编写的Stack。
package cn.mtianyan;
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i); // String中的第i个字符
if (c == '(' || c == '[' || c == '{'){
stack.push(c);
}else{
if (stack.isEmpty())
return false;
char topChar = stack.pop();
if (c ==')' && topChar !='(')
return false;
if (c ==']' && topChar !='[')
return false;
if (c=='}' && topChar != '{')
return false;
}
}
return stack.isEmpty();
}
}
注意topChar时的pop操作，完成了取出栈顶元素和保存栈顶元素两个操作。
附加Python版本实现:
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for c in s:
if(c=='(' or c=='[' or c=='{'):
stack.append(c)
else:
if(len(stack) == 0):
return False
top_c = stack.pop()
if (c ==')' and top_c != '('):
return False
if (c ==']' and top_c !='['):
return False
if (c=='}' and top_c != '{'):
return False
return len(stack)==0;
if __name__ == '__main__':
s = Solution()
print(s.isValid("(]"))
Python版实现要注意list没有push方法，应该使用append方法代替; 注意栈为空(没有待匹配字符直接return False) Python中False是大写，python中获取长度使用len()方法。pop方法还是一样的。
关于LeetCode的更多说明
本地测试,Java版直接添加main函数
public static void main(String[] args) {
System.out.println(new Solution().isValid("()[]{}"));
System.out.println(new Solution().isValid("([)]"));
}
运行结果:
提交时即使添加了main函数也不会报错的。但是请注意不要将自己Package的语句也加入，会报错。
方法必须是public的，因为它会在类外创建自己的Main使用你的方法。
如果我们本地有自己的类接口等，我们可以通过内部类(可以使public也可以是private)来在LeetCode上使用。
class Stack(object):
"""栈"""
def __init__(self):
self.items = []
def is_empty(self):
"""判断是否为空"""
return self.items == []
def push(self, item):
"""加入元素"""
self.items.append(item)
def pop(self):
"""弹出栈顶元素"""
return self.items.pop()
def peek(self):
"""返回栈顶元素"""
return self.items[len(self.items) - 1]
def size(self):
"""返回栈的大小"""
return len(self.items)
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = Stack()
for c in s:
if c == '(' or c == '[' or c == '{':
stack.push(c)
else:
if stack.size() == 0:
return False
top_c = stack.pop()
if c == ')' and top_c != '(':
return False
if c == ']' and top_c != '[':
return False
if c == '}' and top_c != '{':
return False
return stack.size() == 0
if __name__ == '__main__':
s = Solution()
print(s.isValid("(]"))
print(s.isValid("()"))
Python中不能使用内部类，而是应该该类与class Solution并列。这种提交方式，既可以检验我们的解题，对于我们自己编写的Array Stack也进行检验，值得推荐。
可以看到LeetCode的相关话题。点击可以找到栈相关的题目，可以进行专项练习。
学习方法的疑问:
强烈推荐bobo老师的学习方法指导: https://zhuanlan.zhihu.com/p/35878826
一个课程知识学好几遍，而不是硬扛着一遍强行看完。不懂的先留着，比如我就有一个自己的胡思乱想笔记，记录自己每个阶段遗留问题，日后这些遗留问题在自己学到更深度的知识的时候自然会解决。
这39个问题看看自己感兴趣的，大概了解一下栈能解决什么问题。不是非得把问题做完，才能开始下一节。
不要完美主义。掌握好“度”;学习本着自己的目标去。
对于这个课程，大家的首要目标，是了解各个数据结构的底层实现原理,以及应用。学习到后面，再回头来看。
队列 Queue
队列也是一种线性数据结构; 相比数组，队列对应的操作是数组的子集
只能从一端 (队尾) 添加元素，只能从另一端 (队首) 取出元素
就像一个银行的柜台，从队尾进入元素，在队首有柜台处理，处理了就可以出队。
出队从队首出队，1然后2。
队列是一种先进先出的数据结构(先到先得); First In First Out (FIFO)
Queue<E>
void enqueue(E e); // 入队
E dequeue(); // 出队
E getFront(); // 获取队首元素
int getSize(); // 获取队列元素多少
boolean isEmpty(); // 是否为空
Interface Queue<E> implement ArrayQueue<E>
void enqueue(E e); // 入队
E dequeue(); // 出队
E getFront(); // 获取队首元素
int getSize(); // 获取队列元素多少
boolean isEmpty(); // 是否为空
package cn.mtianyan;
public interface Queue<E> {
void enqueue(E e); // 入队
E dequeue(); // 出队
E getFront(); // 获取队首元素
int getSize(); // 获取队列元素多少
boolean isEmpty(); // 是否为空
}
package cn.mtianyan;
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(int capacity) {
this.array = new Array<>(capacity);
}
public ArrayQueue() {
this.array = new Array<>();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void enqueue(E e) {
array.addLast(e);
}
@Override
public E dequeue() {
return array.removeFirst();
}
/**
* 获取队首元素
*
* @return
*/
@Override
public E getFront() {
return array.getFirst();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue ：");
res.append("front [ ");
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize()-1){
res.append(", ");
}
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>();
for (int i = 0; i < 5; i++) {
queue.enqueue(i);
System.out.println(queue);
}
queue.dequeue();
System.out.println(queue);
}
}
运行结果:
数组队列的复杂度分析
ArrayQueue<E>
void enqueue(E e); // 入队 O(1) 均摊
E dequeue(); // 出队 O(n)
E getFront(); // 获取队首元素 O(1)
int getSize(); // 获取队列元素多少 O(1)
boolean isEmpty(); // 是否为空 O(1)
这里入队是从队尾，有可能触发resize，因此均摊下来是O(1)。出队是在队首，数组实现每次都要挪动所有元素,O(n)。
获取队首元素，get(0)，O(1)。剩下两个也是常数级别完成，O(1); 使用循环队列实现即可。
可不可以在把a删除之后，不挪动bcde呢？
剩下的元素仍然保持着先后顺序，我们可以记录一下当前的队首是谁？
(front++)就可以了，tail位置不用变。
front == tail 队列为空。只要队列不为空，front 就不可能等于 tail
入队时不需要考虑front，只需要tail++;出队时，tail不变，front++就可以了。
当tail指向队尾末，再++就会移到越界区域时，前面还有空余空间，把元素填充到前面去。
把数组看成一个环，容量是8，索引0-7。当指向7之后的位置，就变成0了，tail = (7+1)%8 即可。
此时如果再放入元素，tail往后移，front = tail 了，但此时队列为满。
front == tail 队列为空; tail+ 1==front 队列满; 此时就可以扩容了。准确的是(tail +1)%capacity == front队列满
对于整个的capacity中，故意的浪费了一个空间。循环队列类似于钟表时针转动到12.
循环队列代码的基本实现
package cn.mtianyan;
import java.util.Arrays;
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front, tail; // 队首和下一个空位置索引
private int size; // 可以没有size，自己尝试
public LoopQueue(int capacity) {
data = (E[]) new Object[capacity+1]; // 因为会有一个浪费
front = 0;
tail = 0;
size = 0;
}
public LoopQueue() {
this(10);
}
public int getCapacity(){
return data.length-1;
}
@Override
public void enqueue(E e) {
if (isFull()){
resize(getCapacity()*2);
}
data[tail] = e;
tail = (tail+1) % data.length;
size++;
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity +1];
for (int i = 0; i < size; i++) {
newData[i] = data[(i+front) % data.length]; // 此时在newData中队首对齐回来，data中就得有一个front的偏移量
}
data = newData;
front = 0;
tail = size;
}
@Override
public E dequeue() {
if (isEmpty()){
throw new IllegalArgumentException("Cannot dequeue from an empty queue");
}
E ret = data[front];
data[front] = null;
front = (front+1) % data.length;
size--;
if(size == getCapacity()/4 && getCapacity()/2 != 0){
resize(getCapacity()/2);
}
return ret;
}
@Override
public E getFront() {
if (isEmpty()){
throw new IllegalArgumentException("Cannot dequeue from an empty queue");
}
return data[front];
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return front == tail;
}
public boolean isFull(){
return (tail +1)%data.length ==front; // 下一个tail指向front
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("LoopQueue: size = %d, capacity = %d\n",size,getCapacity()));
res.append("front [");
for (int i = front; i != tail; i = (i+1)%data.length) {
res.append(data[i]);
if ((i+1)%data.length !=tail) // 最后一个元素不要加，
res.append(", ");
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<>();
for (int i = 0; i < 5; i++) {
queue.enqueue(i);
System.out.println(queue);
if(i %3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
运行结果:
这里的resize和toString中我们使用了两种不同的遍历方式。一种是size次，元素取值时index偏移量;一种是头不等于尾，i按照循环取值规则向后++。
用户在使用数据结构时，只需要了解接口中设计的方法，其他内部实现对于用户进行了隐藏，比如内部的capacity+1等操作。
循环队列的出队复杂度也变成了O(1),具体的性能对比我们下一节来对比。
循环队列的复杂度分析
ArrayQueue<E>
void enqueue(E e); // 入队 O(1) 均摊
E dequeue(); // 出队 O(1) 均摊
E getFront(); // 获取队首元素 O(1)
int getSize(); // 获取队列元素多少 O(1)
boolean isEmpty(); // 是否为空 O(1)
出队操作可能触发缩容。具体O(n)比O(1)慢多少。
对10万个元素入队出队看时间。
package cn.mtianyan;
import java.util.Random;
public class Main {
/**
* 测试使用q运行optCount个enqueue和deQueue操作所需时间。单位: 秒
*
* @param q
* @param opCount
* @return
*/
private static double testQueue(Queue<Integer> q,int opCount){
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++) {
q.enqueue(random.nextInt(Integer.MAX_VALUE)); // 生成从0到int最大值
}
for (int i = 0; i < opCount; i++) {
q.dequeue();
}
long endTime = System.nanoTime(); // 纳秒
return (endTime - startTime)/ 1e9;
}
public static void main(String[] args) {
int opCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue出队入队"+opCount+"次的时间: "+time1+"秒");
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("loopQueue出队入队"+opCount+"次的时间: "+time2+"秒");
}
}
运行结果:
对于100万的运行结果:
两者的差距主要在出队的过程中。对于ArrayQueue来说，每出一次队，队首后面的所有元素都得挪动一次。出队操作复杂度是O(n),相应而言，对于ArrayQ，整个testQueue的复杂度就是O(n^2)，因为每次O(n)，for循环有n次。对于LoopQueue的testQueue: 每次都是O(1)，for循环有n次，因此testQueue()为O(n)。
性能对比:
| Queue类型 | 循环次数 | 时间 | 倍数 |
|---|---|---|---|
| LoopQueue | 10万 | 0.01 | 1(基准) |
| ArrayQueue | 10万 | 2.85 | 285 |
| LoopQueue | 100万 | 0.06 | 1(基准) |
| ArrayQueue | 100万 | 285.46 | 4758 |
这是对于O(n)以及O(n^2) 的性能对比，可以看出性能差异巨大。对于同一种Queue实现，我们依然可以根据(0.06/0.01)=6 数据量扩大十倍，时间复杂度扩大了6倍,验证O(n); (285.46/2.85)=100，数据量扩大10倍，时间复杂度扩大了100倍，验证O(n^2)。
更合理的测试方法是对于testQueue也进行多次，取平均值。和JVM也会有关。
同一台电脑，我改为java10运行。不知为什么比java8的运行速度慢了很多。
队列的应用: 排队，操作系统任务排队。队首的定义，存在广义队列，后面会学。此处我们学到的普通队列，在后面的广度优先遍历，二叉树时也可以学到。
下一章，我们将讲解链表。
网友评论