4. 栈和队列
栈：push，pop，peek（返回当前值），empty
队列：add，remove，peek（返回当前值），isEmpty
4.1 双向链表实现栈和队列
4.2 数组实现栈和队列
加一个指针指向某个位置。
队列：环形数组
4.3 最小栈
1. 题目
https://leetcode.cn/problems/min-stack/
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
2. 思路
两个栈，A栈放值，B栈放当前A的最小值（新加入的时候，如果比最小值大就接着放之前的最小值，如果比最小值小，就放新的最小值）
3. 代码
class MinStack {
Deque<Integer> val;
Deque<Integer> min;
public MinStack() {
val = new LinkedList<Integer>();
min = new LinkedList<Integer>();
}
public void push(int val) {
this.val.push(val);
if(this.min.isEmpty()){
this.min.push(val);
}else{
int cur = this.min.peek();
if(cur > val){
this.min.push(val);
}else{
this.min.push(cur);
}
}
}
public void pop() {
if(!val.isEmpty()){
val.pop();
min.pop();
}
}
public int top() {
return val.peek();
}
public int getMin() {
return min.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
4.4 用栈实现队列
1. 题目
https://leetcode.cn/problems/implement-queue-using-stacks/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
2. 思路
两个栈，一个in，一个out，
进入：加入到in栈。
弹出：如果out为空，就把in倒入，否则弹出out。
3. 代码
class MyQueue {
Stack<Integer> in;
Stack<Integer> out;
public MyQueue() {
in = new Stack<Integer>();
out = new Stack<Integer>();
}
public void inToOut(){
while(!in.empty()){
out.push(in.pop());
}
}
public void push(int x) {
in.push(x);
}
public int pop() {
if(out.empty()){
// 清空in到out中
inToOut();
}
return out.pop();
}
public int peek() {
if(out.empty()){
// 清空in到out中
inToOut();
}
return out.peek();
}
public boolean empty() {
if(out.empty() && in.empty()){
return true;
}
return false;
}
}
4.4 用队列实现栈
1. 题目
https://leetcode.cn/problems/implement-stack-using-queues/
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
2. 思路
两个队列，A，B，不断转换状态。
弹出：A中只留一个剩下加入B，B转为活跃，A的弹出。而后B中只留下一个剩下加入A，A转为活跃，B弹出
进入：加入到活跃队列中
3. 代码
class MyStack {
Queue<Integer> a;
Queue<Integer> b;
char alive;
public MyStack() {
a = new LinkedList<Integer>();
b = new LinkedList<Integer>();
alive = 'a';
}
public int changeQue(Queue<Integer> from, Queue<Integer> to){
int size = from.size();
// 导出，只留最后一个
for(int i = 0; i < size-1; i++){
int temp = from.remove();
to.add(temp);
}
alive = alive == 'a'?'b':'a';
return from.remove();
}
public void push(int x) {
if(alive == 'a'){
a.add(x);
}else{
b.add(x);
}
}
public int pop() {
int val = 0;
if(alive == 'a'){
val = changeQue(a,b);
}else{
val = changeQue(b,a);
}
return val;
}
public int top() {
int val = 0;
if(alive == 'a'){
val = changeQue(a,b);
b.add(val);
}else{
val = changeQue(b,a);
a.add(val);
}
return val;
}
public boolean empty() {
if(a.isEmpty() && b.isEmpty()){
return true;
}
return false;
}
}