栈和队列的理论基础
栈(stack)：
特点：先进后出(LIFO)
java底层：
Java中的Stack<E>类继承了Vector<E>类
一般使用Deque<E>实现stack【Deque<Integer> stack = new ArrayDeque<Integer>();】
基本操作：
push() ---- 进栈
pop() ---- 出栈
peek() ---- 查看栈顶元素
empty() ---- 测试栈是否为空
实现：
使用链表实现栈
使用数组实现栈
使用队列实现栈
队列(queue)：
特点：后进后出(FIFO)
Queue<E>的java底层：
Java中Queue<E>接口继承了Collection<E>接口
一般用LinkedList<E>类进行实现
Queue基本操作：
add()、offer() ---- 从队尾添加元素
remove()、poll() ---- 从队头删除元素
element()、peek() ---- 查看队头元素
Deque<E>的java底层：
Java中Deque<E>接口继承了Queue<E>接口
支持在两端插入和移除元素
deque <----> double ended queue 双端队列
Deque<E>可以等效Queue<E>
Deque<E>可以等效Stack<E>，优先使用此接口
Deque基本操作：
addFirst()、offerFirst() ---- 在队头添加元素
removeFirst()、pollFirst() ---- 从队头删除元素
getFirst()、peekFirst() ---- 查看队头元素
addLast()、offerLast() ---- 在队尾添加元素
removeLast()、pollLast() ---- 从队尾删除元素
getLast()、peekLast() ---- 查看队尾元素
实现：
使用链表实现队列
使用数组实现队列
使用栈实现队列
232.用栈实现队列
题目链接：力扣
思路
首先使用一个栈来模拟队列，入队相当于入栈，但是出队的话队头还压在栈底，要出来的话就需要将此栈中的元素全部弹出。
此时可以用另一个栈来保存弹出的元素，那么上一个栈中的栈底元素就在这个栈的栈顶元素，就是队列的队头，如果需要出队和查看队头就都可以进行操作了
用栈实现队列
第一步：定义一个入栈和一个出栈
第二步：实现push() --- 最好实现
第三步：实现pop() --- 出栈为出队
首先需要判断出栈是不是为空
如果出栈为空，要将入栈中的所有元素加入到出栈中，再从出栈中进行出队
如果不为空，说明出栈中还有元素，元素从出栈中进行出队
第四步：实现peek()
首先需要判断出栈是否为空
如果出栈为空，要将入栈中的所有元素加入到出栈中，再从出栈中返回队头
如果不为空，说明出栈中还有元素，从出栈中返回队头
第五步：实现isEmpty()
只有出栈和入栈中所有的元素为空，才算整个队列为空
class MyQueue { Stack<Integer> stackIn; Stack<Integer> stackOut; // 对队列进行初始化 public MyQueue() { stackIn = new Stack<>(); stackOut = new Stack<>(); } public void push(int x) { stackIn.push(x); } public int pop() { if (stackOut.isEmpty()) { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } return stackOut.pop(); } public int peek() { if (stackOut.isEmpty()) { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } else {} return stackOut.peek(); } public boolean empty() { return stackIn.isEmpty() && stackOut.isEmpty(); } }
225.用队列实现栈
题目链接：力扣
思路
因为有了上道题的经验，首先的思维就是用两个队列对栈进行实现，按照上道题目的思路是不可以的，因为把一个队列移动到另一个队列，出队的顺序并没有发生变化。所以需要转换思路。如果每次添加的数字都不出现在队尾，而是出现在队头就可以了。
那就每次添加数字的时候，先进q2，然后把q1已有的元素添加到q2，此时q2就是栈的顺序了，q1就为空了。但是我们得固定一个队列进行出栈操作，所以就把q1和q2进行交换。此时q1就是一个栈了，q2就为空，这样就实现了栈
那么如何用一个队列实现栈呢，压栈可以是入队，但是弹栈的时候需要队尾元素出来，怎么办呢，那就可以跟进队列的长度，把除队尾元素的元素全部出队再入队，这样队尾元素就到队头了，可以进行pop
那么top怎么实现呢，因为只查不删，所以直接返回队尾元素就可以了，java的Queue接口没有直接返回队尾元素的功能，所以我们要么使用Deque接口，要么就需要在添加元素的时候下功夫了，这样的队列才可以top和pop
随意每添加一个元素，就给队列中的元素重新排个序，保持队列中一直是压栈的顺序
如果使用Deque接口的话，就直接在每次删除的时候变换顺序就可以了,查询的话查询队尾就可以
用队列实现栈
用两个队列实现栈
第一步：创建两个队列
第二步：实现push() --- 压栈
先进q2进行待命
让q1中的元素进q2，实现了新进的元素都在队头(栈顶)
让q1和q2进行交换
第三步：实现pop()
q1进行出队
第四步：实现peek()
q1进行考察队头
第五步：实现empty()
q1是否为空
class MyStack { Queue<Integer> queue1; Queue<Integer> queue2; public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } // 向栈中添加元素,这里queue2就是个备份队列 // 经过一番操作，queue1其实就是栈的顺序 public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } // 到此处，queue2就有栈的顺序了，queue为空队列，已经被搬空了 // 然后再对queue1和queue2进行交换 Queue<Integer> queueTemp; queueTemp = queue1; queue1 = queue2; queue2 = queueTemp; } public int pop() { return queue1.poll(); } public int top() { return queue1.peek(); } public boolean empty() { return queue2.isEmpty(); } }
用一个队列实现栈
第一步：创建队列
第二步：实现push()
为了让top和pop更加方便，避免这两个操作临近操作时出错，在添加的时候就将顺序排成栈的顺序
每入队一个元素，就将前面的元素出队再入队，这样保证了队头是栈顶元素
第三步：实现pop()
排好队的队列出队
第四步：实现top()
排好队的队列查队头
第五步：实现empty()
队列是否为空
class MyStack { Queue<Integer> queue; public MyStack() { queue = new LinkedList<>(); } public void push(int x) { queue.offer(x); int len = queue.size() - 1; while (len-- > 0) { queue.offer(queue.poll()); } } public int pop() { return queue.poll(); } public int top() { return queue.peek(); } public boolean empty() { return queue.isEmpty(); } }
