勘误
上一篇订阅号的推文LeetCode进阶103-蛇形打印二叉树（今日头条面试题）最后一种方法DFS-非递归的编码实践部分因为失误复制粘贴错了，由于微信公众平台支持修改字符上限为20，无法修改，需要查看正确编码解法的话请点击查看原文链接，原文挂在掘金上并已做修正。
概要
队列结构满足FIFO(first in first out)特点，与栈的FILO(first in last out)恰好相反。实际栈和队列之间可以相互模拟，即使用栈模拟队列或者使用队列模拟栈。
队列
232. 用栈实现队列
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
分析&&思路
要使用栈来模拟队列，根据栈的先进后出的特点（后进先出）会使得元素倒序，不难联想到使用两个栈。第一个栈使得顺序变成倒序，第二个栈使得倒序又变成顺序即最终满足队列顺序的特点。参考图解：
编码实践
class MyQueue {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
public MyQueue() {
}
/**
* 入"队列"至队尾
*
* @param x
*/
public void push(int x) {
s1.push(x);
}
/**
* 首元素出“队列”
*
* @return
*/
public int pop() {
if (!s2.isEmpty()) {
return s2.pop();
}
move();
return s2.pop();
}
/**
* 获取队列头部元素
*
* @return
*/
public int peek() {
if (!s2.isEmpty()) {
return s2.peek();
}
move();
return s2.peek();
}
/**
* 利用第二个栈将“队列”中倒序的数据变成正序
*/
private void move() {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
说明
见注释
栈
225. 用队列实现栈
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
分析&&思路
使用队列模拟栈，需要保证后进先出，在插入新元素到队列后，循环使得队列中队尾元素置顶即可。参考图解：
编码实践
class MyStack {
Queue<Integer> queue = new LinkedList<Integer>();
public MyStack() {
}
/**
* 入“栈”至“栈”顶
* 元素存入queue队列后，将存储元素的queue队列进行循环直到队尾元素成为队头
* @param x
*/
public void push(int x) {
queue.add(x);
for (int i = 0; i < queue.size() - 1; i++) {
queue.add(queue.poll());
}
}
/**
* 出“栈”
* @return
*/
public int pop() {
return queue.poll();
}
/**
* 获取“栈”顶元素
* @return
*/
public int top() {
return queue.peek();
}
/**
* 判断“栈”是否为空
* @return
*/
public boolean empty() {
return queue.isEmpty();
}
}
编码说明
见注释
总结
本篇通过介绍队列和栈的互相模拟方法加强对其特性的理解。实际开发中，队列和栈同样是十分重要的数据结构。最后，如果觉得本篇有所帮助或启发，不妨关注走一波～
