栈（Stack）与队列（Queue，Deque）

前言：

栈与队列在数据结构中用法都相对比较简单，是数据结构中经常用到的两种。

1.栈（Stack）

（1）特点：

 先入后出，后入先出。栈的底层就是一个数组（java原生库中），通过对数组的操作来实现栈的相关操作。栈也是可以用链表（LinkedList）来实现的，在LinkedList这个类中也有push，pop，peek等方法，足以说明栈可以用LinkedList来实现。栈继承了Vector类（这个类中也有一个判空的方法isEmpty() ），可以使用在这个类中的所有非私用方法。

（2）方法：

这里push，pop，empty时间和空间复杂度都为O(1)。 empty判空是定义了一个变量，用来计数。

（3）OJ题：

1）逆波兰表达式求值：

题析：

题解：

import java.util.Stack;
class Solution {public boolean isOperation(String x) {if(x.equals("+") | x.equals("-") | x.equals("*") | x.equals("/")) {return false;}return true;}public int evalRPN(String[] tokens) {Stack<String> stack = new Stack<>();for(String x : tokens) {if(!isOperation(x)) {//如果不是数字int num1 = Integer.parseInt(stack.pop()); //栈顶元素 => 放在右边int num2 = Integer.parseInt(stack.pop()); //栈顶后面一个元素 => 放在左边switch(x) {case "+":stack.push(String.valueOf((num2 + num1)));break;case "-":stack.push(String.valueOf((num2 - num1)));break;case "*":stack.push(String.valueOf((num2 * num1)));break;case "/":stack.push(String.valueOf((num2 / num1)));break;default:break;}}else {stack.push(x);}}return Integer.parseInt(stack.peek());}
}

2）括号匹配： 

题析：

题解：

import java.util.Stack;
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();char[] arr = s.toCharArray();for(char x : arr) {if(stack.empty()){stack.push(x);}else {if(stack.peek() == '(' && x == ')' || stack.peek() == '{' && x == '}' || stack.peek() == '[' && x == ']') {stack.pop();}else {stack.push(x);}}}return stack.empty();}
}

3）出栈入栈次序匹配：

题析：

题解：

public class Solution {public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(!stack.isEmpty() && j < popV.length && stack.peek() == popV[j]) {stack.pop();j++;}}if(!stack.isEmpty()) {return false;}return true;}
}

2.队列

队列分为单端队列（Queue）和双端队列（Deque），都是接口，都有先入先出，后入后出的特点。

2.1 单端队列（Queue）

（1）特点：

只有一端可以入，一端可以出。Queue可以用线性表（循环队列），也可以用链表（LinkedList）来实现。

（2）方法：

主要的方法就这三种。需要注意的是这里面Queue接口中没有empty()方法，但由于它是继承了Vector类，所以可以使用isEmpty()方法来判断是否Queue为空。

（3）OJ题：

1）设计循环队列：

题析：

题解：

//法一：设置一个计数变量：count
class MyCircularQueue {//循环队列的底层就是一个数组public int[] arr;//队头public int front;//队尾public int tail;//计数public int count;public MyCircularQueue(int k) {arr = new int[k];}public boolean enQueue(int value) {if(isFull()) {//队列已满return false;}if(tail == arr.length) {tail = 0;}arr[tail] = value;tail++;count++;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front++;if(front == arr.length) {front = 0;}count--;return true;}public int Front() {if(isEmpty()) {return -1;}return arr[front];}public int Rear() {if(isEmpty()) {return -1;}if(isFull()) {}int index = (tail == 0) ? 0 : (tail - 1); return arr[index];}public boolean isEmpty() {return count == 0;}public boolean isFull() {return count == arr.length;}
}

//法二：浪费一个空间
class MyCircularQueue {//循环队列的底层就是一个数组public int[] arr;//队头public int front;//队尾public int tail;public MyCircularQueue(int k) {arr = new int[k + 1];}public boolean enQueue(int value) {if(isFull()) {//队列已满return false;}arr[tail] = value;tail = (tail + 1) % arr.length;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front = (front + 1) % arr.length;return true;}public int Front() {if(isEmpty()) {return -1;}return arr[front];}public int Rear() {if(isEmpty()) {return -1;}int index = (tail == 0) ? (arr.length - 1) : (tail - 1); return arr[index];}public boolean isEmpty() {return tail == front;}public boolean isFull() {return (tail + 1) % arr.length == front;}
}

浪费一个空间的这种写法： 

题中给的示列：

而按我们这种这里的写法： 如果设置长度为3，那么只能放两个元素，所以需要将数组的长度设置为4就能放三个元素了，也就是数组长度设置为k + 1。

 2.2 双端队列

（1）特点：

两端都可以入队出队。Deque可以用线性表（循环队列），也可以用链表（LinkedList）来实现。

（2）方法：

与单端队列的方法都大同小异。 

3.栈与队列相关的OJ题

（1）用栈实现队列

题析：

题解：

class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(stack2.isEmpty()) {while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(stack2.isEmpty()) {while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

（2）用队列实现栈：

题析：

题解：

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new ArrayDeque<>();queue2 = new ArrayDeque<>();}public void push(int x) {if(!queue1.isEmpty()) {queue1.offer(x);}else if(!queue2.isEmpty()) {queue2.offer(x);}else {//两个都为空,指定放在queue1中queue1.offer(x);}}public int pop() {if(empty()) {return -1;}int i = 0;if(!queue1.isEmpty()) {int size = queue1.size();for(i = 0; i < size- 1; i++) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size = queue2.size();for(i = 0; i < size- 1; i++) {queue1.offer(queue2.poll());}return  queue2.poll();}}public int top() {int i = 0;if(!queue1.isEmpty()) {int size = queue1.size();int x = -1;for(i = 0; i < size; i++) {x = queue1.poll();queue2.offer(x);}return x;}else {int size = queue2.size();int x = -1;for(i = 0; i < size; i++) {x = queue2.poll();queue1.offer(x);}return  x;}}public boolean empty() {//两个队列均为空的时候才能判断该栈为空return queue1.isEmpty() && queue2.isEmpty();}
}