目录
1. 栈
1.1. 栈简介
1.2. 栈的常见应用常见应用场景
1.2.1. 实现浏览器的回退和前进功能
1.2.2. 检查符号是否成对出现
1.2.3. 反转字符串将字符串中的每个字符先入栈再出栈就可以了。
1.2.4. 维护函数调用
1.3. 栈的实现
2. 队列
2.1. 队列简介
2.2. 队列分类
2.2.1. 单队列
2.2.2. 循环队列
2.3. 常见应用场景
1. 栈
1.1. 栈简介
栈 (stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。
栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈 ，用链表实现的栈叫作 链式栈 。
1.2. 栈的常见应用常见应用场景当我们我们要处理的数据只涉及在一端插入和删除数据，并且满足 后进先出（LIFO, Last In First Out） 的特性时，我们就可以使用栈这个数据结构。
1.2.1. 实现浏览器的回退和前进功能
我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候，你点击回退按钮，我们依次把 4,3 这两个页面从 Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面 3，你点击前进按钮，我们将 3 页面从 Stack2 弹出，然后压入到 Stack1 中。
1.2.2. 检查符号是否成对出现
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串，判断该字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
比如 "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]" 、"([)]" 则不是。
这个问题实际是 Leetcode 的一道题目，我们可以利用栈 Stack 来解决这个问题。
- 首先我们将括号间的对应规则存放在
Map中，这一点应该毋容置疑； - 创建一个栈。遍历字符串，如果字符是左括号就直接加入
stack中，否则将stack的栈顶元素与这个括号做比较，如果不相等就直接返回 false。遍历结束，如果stack为空，返回true。
1.2.3. 反转字符串将字符串中的每个字符先入栈再出栈就可以了。
1.2.4. 维护函数调用
最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out） 特性。
1.3. 栈的实现
栈既可以通过数组实现，也可以通过链表来实现。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。
下面我们使用数组来实现一个栈，并且这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()、size()这些基本的方法。
提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用
Arrays.copyOf()进行扩容；
public class MyStack {
private int[] storage;//存放栈中元素的数组
private int capacity;//栈的容量
private int count;//栈中元素数量
private static final int GROW_FACTOR = 2;
//不带初始容量的构造方法。默认容量为8
public MyStack() {
this.capacity = 8;
this.storage=new int[8];
this.count = 0;
}
//带初始容量的构造方法
public MyStack(int initialCapacity) {
if (initialCapacity < 1)
throw new IllegalArgumentException("Capacity too small.");
this.capacity = initialCapacity;
this.storage = new int[initialCapacity];
this.count = 0;
}
//入栈
public void push(int value) {
if (count == capacity) {
ensureCapacity();
}
storage[count++] = value;
}
//确保容量大小
private void ensureCapacity() {
int newCapacity = capacity * GROW_FACTOR;
storage = Arrays.copyOf(storage, newCapacity);
capacity = newCapacity;
}
//返回栈顶元素并出栈
private int pop() {
if (count == 0)
throw new IllegalArgumentException("Stack is empty.");
count--;
return storage[count];
}
//返回栈顶元素不出栈
private int peek() {
if (count == 0){
throw new IllegalArgumentException("Stack is empty.");
}else {
return storage[count-1];
}
}
//判断栈是否为空
private boolean isEmpty() {
return count == 0;
}
//返回栈中元素的个数
private int size() {
return count;
}
}
验证
MyStack myStack = new MyStack(3);
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
myStack.push(7);
myStack.push(8);
System.out.println(myStack.peek());//8
System.out.println(myStack.size());//8
for (int i = 0; i < 8; i++) {
System.out.println(myStack.pop());
}
System.out.println(myStack.isEmpty());//true
myStack.pop();//报错：java.lang.IllegalArgumentException: Stack is empty.
2. 队列
2.1. 队列简介
队列 是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
假设队列中有n个元素。
访问：O（n）//最坏情况
插入删除：O（1）//后端插入前端删除元素
2.2. 队列分类
2.2.1. 单队列
单队列就是常见的队列, 每次添加元素时，都是添加到队尾。单队列又分为 顺序队列（数组实现） 和 链式队列（链表实现）。
顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。
假设下图是一个顺序队列，我们将前两个元素 1,2 出队，并入队两个元素 7,8。当进行入队、出队操作的时候，front 和 rear 都会持续往后移动，当 rear 移动到最后的时候,我们无法再往队列中添加数据，即使数组中还有空余空间，这种现象就是 ”假溢出“ 。除了假溢出问题之外，如下图所示，当添加元素 8 的时候，rear 指针移动到数组之外（越界）。
为了避免当只有一个元素的时候，队头和队尾重合使处理变得麻烦，所以引入两个指针，front 指针指向对头元素，rear 指针指向队列最后一个元素的下一个位置，这样当 front 等于 rear 时，此队列不是还剩一个元素，而是空队列。——From 《大话数据结构》
2.2.2. 循环队列
循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是：从头开始，这样也就会形成头尾相接的循环，这也就是循环队列名字的由来。
还是用上面的图，我们将 rear 指针指向数组下标为 0 的位置就不会有越界问题了。当我们再向队列中添加元素的时候， rear 向后移动。
顺序队列中，我们说 front==rear 的时候队列为空，循环队列中则不一样，也可能为满，如上图所示。解决办法有两种：
- 可以设置一个标志变量
flag,当front==rear并且flag=0的时候队列为空，当front==rear并且flag=1的时候队列为满。 - 队列为空的时候就是
front==rear，队列满的时候，我们保证数组还有一个空闲的位置，rear 就指向这个空闲位置，如下图所示，那么现在判断队列是否为满的条件就是：(rear+1) % QueueSize= front。
2.3. 常见应用场景
当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。
- 阻塞队列： 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候，出队操作阻塞，当队列满的时候，入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。
- 线程池中的请求/任务队列： 线程池中没有空闲线程时，新的任务请求线程资源时，线程池该如何处理呢？答案是将这些请求放在队列中，当有空闲线程的时候，会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列，除非系统资源耗尽，比如 ：
FixedThreadPool使用无界队列LinkedBlockingQueue。但是有界队列就不一样了，当队列满的话后面再有任务/请求就会拒绝，在 Java 中的体现就是会抛出java.util.concurrent.RejectedExecutionException异常。 - Linux 内核进程队列（按优先级排队）
- 现实生活中的派对，播放器上的播放列表;
- 消息队列
- 等等......