一、栈

1、栈的概念

是一种线性表，具有后进先出的特点。只能在固定的一段进行数据的插入和删除，进行元素插入和删除的一端称为栈顶，另一端称为栈底。

2、栈的使用

3、栈实例

（1）逆序打印链表

eg：链表为1->2->3->4->5

逆序打印：5->4->3->2->1

递归方式：

void printList(ListNode head){if(null!=head){printList(head.next);System.out.print(head.val+" ");}
}

栈方式：

Stack<Integer> stack=new Stack<>();
while(head!=null){stack.push(head.val);head=head.next;
}
while(!stack.empty()){System.out.print(stack.pop()+" ");
}

（2）括号匹配

class Solution {public boolean isValid(String s) {int n=s.length();Stack<Character> stack=new Stack<>();for(int i=0;i<n;i++){char c=s.charAt(i);if(c=='('||c=='['||c=='{'){stack.push(c);}else{if(stack.empty()){return false;}if(c==')'&&stack.peek()=='('||c==']'&&stack.peek()=='['||c=='}'&&stack.peek()=='{'){stack.pop();}else{return false;}}}return stack.empty();}
}

（3）逆波兰表达式求值

class Solution {public int evalRPN(String[] tokens) {int n=tokens.length;Stack<Integer> s=new Stack<>();for(int i=0;i<n;i++){String temp=tokens[i];if(!(temp.equals("+")||temp.equals("-")||temp.equals("*")||temp.equals("/"))){s.push(Integer.valueOf(temp));}else{int b=s.pop();int a=s.pop();if(temp.equals("+")){s.push(a+b);}else if(temp.equals("-")){s.push(a-b);}else if(temp.equals("*")){s.push(a*b);}else{s.push(a/b);}}}return s.pop();}
}

（4）出栈入栈次序匹配

 public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> s=new Stack<>();int n=pushV.length;int j=0;for(int i=0;i<n;i++){s.push(pushV[i]);while(!s.empty()&&s.peek()==popV[j]){s.pop();j++;}}return j==n;}

（5）最小栈

class MinStack {Stack<Integer> s1;Stack<Integer> s2;public MinStack() {s1=new Stack<>();s2=new Stack<>();}public void push(int val) {s1.push(val);if(s2.empty()){s2.push(val);}else{if(s2.peek()>=val){s2.push(val);}}}public void pop() {int a=s1.pop();if(!s2.empty()&&s2.peek()==a){s2.pop();}}public int top() {return s1.peek();}public int getMin() {if(s2.empty()){return -1;}else{return s2.peek();}}
}

（6）栈、虚拟机栈、栈帧有什么区别？

栈：是一种线性表，具有后进先出的特点；

虚拟机栈：jvm划分的一块内存；

栈帧：调用方法的时候会在虚拟机当中给这个方法开辟一块内存。

二、队列

1、队列的概念

是一种线性表，具有先进先出的特点。只能在固定的一段进行数据的插入和删除，进行元素插入一端称为队尾，另一端称为队头。

2、队列的使用

注意：Queue是一个接口，在实例化对象时，使用LinkedList实例化对象，因为LinkedList实现了Queue接口。

3、队列实例

（1）循环队列

区分空与满

①记录长度标记

放入一个元素，长度+1；取出一个元素，长度-1；长度>队列最长长度，已满；长度<=0，已空；

该方法操作简单，就不再详细编写代码。

②保留一个位置

class MyCircularQueue {int[] elem;int front;int rear;public MyCircularQueue(int k) {elem=new int[k+1];}public boolean enQueue(int value) {if(isFull()){return false;}else{elem[rear]=value;rear=(rear+1)%elem.length;return true;}}public boolean deQueue() {if(isEmpty()){return false;}else{front=(front+1)%elem.length;return true;}}public int Front() {if(isEmpty()){return -1;}else{return elem[front];}}public int Rear() {if(isEmpty()){return -1;}else{int index=(rear==0)?elem.length-1:rear-1;return elem[index];}}public boolean isEmpty() {return front==rear;}public boolean isFull() {return (rear+1)%elem.length==front;}
}

（2）用队列实现栈

队列：先进先出；栈：先进后出

两个队列一模一样：进出队列变换。

class MyStack {Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1=new LinkedList<Integer>();q2=new LinkedList<Integer>();}public void push(int x) {if(q1.isEmpty()){q2.offer(x);}else{q1.offer(x);}}public int pop() {if(empty()){return -1;}int temp=0;if(q1.isEmpty()){while(!q2.isEmpty()){temp=q2.poll();if(!q2.isEmpty()){q1.offer(temp);}}}else{while(!q1.isEmpty()){temp=q1.poll();if(!q1.isEmpty()){q2.offer(temp);}}}return temp;}public int top() {if(empty()){return -1;}int temp=0;if(q1.isEmpty()){while(!q2.isEmpty()){temp=q2.poll();q1.offer(temp);}}else{while(!q1.isEmpty()){temp=q1.poll();           q2.offer(temp);                }}return temp;}public boolean empty() {return q1.isEmpty()&&q2.isEmpty();}
}

（3）用栈实现队列

两个栈不一样，一个栈固定为入队列，一个栈固定为出队列。

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

4、双端队列（Deque）

允许两端都可以进行入队和出队操作。Deque是一个接口，实例化对象使用LinkedList实现。