进栈操作的算法（算法图解栈和队列）
作者：任玉刚
原文：https://mp.weixin.qq.com/s/TVFNmT9t6qVINia2nsRLaQ
算法，一门既不容易入门，也不容易精通的学问。
对于笔者来说算法算是我程序员生涯很不擅长的技能之一了，自从互联网界招人进入平静期后，越来越多的大厂在社招的时候不但会考验面试者的工作所用到的技能，而且会用算法题来考验面试者的逻辑思维能力和基本数据结构的掌握能力。这也就让想要社招进入大厂的部分同学有了一些望而却步的心理，毕竟工作中大部分时间在与UI层面的逻辑打交道，数据处理方面及时之前在学校中掌握的还不做，几年的CV生活，估计也忘的差不多了。
但是作为一条有梦想的咸鱼，我们还是要重拾这些知识的。今天笔者将会挑选几道栈与队列的题目来回顾下相关算法的基本知识。
栈与队列分别是两种数据结构，不同语言对于栈和队列有着不同的声明，在 java 中 Stack 类是继承自 Vector 集合的子类，Queue 则是以接口形式存在，常用的其实现类是 LinkedList 这个双向队列。在C 的标准模版库也是有这两个数据结构定义的具体类的。
栈数据结构的特点是 FILO（first in last out） 即先进后出，队列则是 FIFO（first in first out）即先进先出。相信栈与队列的数据结构的基本特点大家也是熟记于胸了。下面就带大家看一道面试题来带大家看下这两者在面试题中的形式。
由两个栈实现一个队列 （✭✭✩✩✩）
题目难度两颗星，主要考察了对于栈和队列的数据结构特点。
前文介绍了，对于一个栈来说遵循 pop 操作时从栈的顶部取一个元素，对于队列来说 poll 操作时从队列队首取一个元素。所以该题翻译过来就是使用两个栈定义一种先放入的元素，最先被取出的数据结构。
此题应考虑到两种情况，首先最简单的一种情况，假设有 1，2，3，4，5 个元素依次进入自定义的队列，再依次取出。由于是进栈操作都进行完了才进行出栈操作，所以我们只需在元素出队时，将进栈元素倒入另一个空栈中即可。示意图如下：
再一种情况是，如果 add poll 操作是交替进行的，那么如何保证数据结构先进先出的定义呢？比如先放入 1，2，3然后要进行一次取出操作取出 1，随后在进行 add 操作放入4，5，这种情况下如何操作两个栈，才能保证之后再取出的时候元素为 2，3，4，5 顺序？实际上我们只需要保证一下两点就可以：
- 无论如果 StackA（最开始add元素的那个栈） 要往 StackB 中压入元素，那么必须选择一次性全部压入。
- 无论什么时候从队列中取元素，必须保证元素是从 StackB 中 pop 出的，也就是说，当 StackB 不为空的时候绝不能再次向 StackB 中压入元素。
为了方便理解可以看下边这幅图：
明白了需要注意的点后就是该写代码的时候了，需要注意的点在图中已经用红色字体标出了，也就是在存入元素一直往 StackA 中存，取元素是从 StackB 中取，但要要注意的是取的时候需要保证 StackB 为空的时候要先将 StackA 中元素一次性压如 StackB 中，在进行从 StackB 中取的操作。
public static class TwoStackQueue<E>{
private Stack<E> stackA;
private Stack<E> stackB;
public TwoStackQueue() {
stackA = new Stack<>();
stackB = new Stack<>();
}
/**
* 添加元素逻辑
* @param e 要添加的元素
* @return 这里只是遵循 Queue 的习惯，这里简单处理返回 true 即可
*/
public boolean add(E e){
stackA.push(e);
return true;
}
/**
* 去除元素的时候需要判断两个地方，StackA & StackB 是否都为空
* StackB 为空的时候讲StackA中的元素全部依次压入 StackB
* @return 返回队列中的元素 如果队列为空返回 null
*/
public E poll(){
//如果队列中没有元素则直接返回空，也可以选择抛出异常
if (stackB.isEmpty() && stackA.isEmpty()){
return null;
}
if (stackB.isEmpty()){
while (!stackA.isEmpty()){
stackB.add(stackA.pop());
}
}
return stackB.pop();
}
/**
* peek 操作不取出元素，只返回队列头部的元素值
* @return 队列头部的元素值
*/
public E peek(){
//如果队列中没有元素则直接返回空，也可以选择抛出异常
if (stackB.isEmpty() && stackA.isEmpty()){
return null;
}
if (stackB.isEmpty()){
while (!stackA.isEmpty()){
stackB.add(stackA.pop());
}
}
return stackB.peek();
}
}
对应的 C 解法：
#include <stdio.h>
#include <stack>
using namespace std;
template <typename T> class TStackQueue
{
public:
void add(T t);
T poll();
private:
stack<T> stackA;
stack<T> stackB;
};
template <typename T> void TStackQueue<T>::add(T node) {
stackA.push(node);
}
template<typename T> T TStackQueue<T>::poll(){
if (stackB.empty() && stackA.empty()) {
return NULL;
}
if (stackB.empty()) {
while (!stackA.empty()) {
stackB.push(stackA.top());
stackA.pop();
}
}
T node = stackB.top();
stackB.pop();
return node;
}
两个队列实现一个栈 （✭✭✩✩✩）
上道题我们完成了两个栈实现一个队列的题目，那么两个队列实现一个栈又该注意哪些呢？
首先队列是先进先出，我们可以发现队列无论怎么倒，我们不能逆序一个队列。既然不能套用上题的解法，那么就得另谋出路，但是可以预知无非就是两个队列进行交替的入队出队操作，那么唯一要做的就是判断目前出队的值是否是按照放入元素顺序中最后放入的元素。 依旧画图举例
这里我们只看首次取出操作，那么需要注意一点， 如何判断哪一次取出操作后 QueueA 为空？
事实上作为 Queue 作为容器，我们可以通过事先定义好的方法 queue.size() 去判断一个队列中元素的个数，有人可能说这是犯规，其实不是的。题目中给出是让你用队列去实现，那么队列中公共 API 都是你可以用的。所以可以想象出下面的伪代码：
//如果 queueA 的大小不为 0 则循环取出元素
while(queueA.size() > 0){
//被取出的元素
int result = queueA.poll();
// 这里注意我们取出元素后再去判断一次，队列是否为空，如果为空代表是最后一个元素
if(queueA.size() != 0){
queueB.add(result)
}else{
return result;
}
}
上文我们只是说了一次取出操作，那么一次取出操作后，再次放入元素应该怎么放，我们似乎又遇到了困难。
与上题不同的是，我们应该先思考如果连续两次取出应该怎么操作，上面一次取出后 QueueA 空了，所以我们如果按照相同的思路将 B 中的元素倒入 A 中，那么将会得到 3 ，这看起来没什么问题。那么如果下一步进行的 push 操作，那么应该放入 QueueA 还是 QueueB 中才能保证元素先进后出的规则呢，很容易想到是放入 B 中。 那么总结一下操作要点：
- 任何时候两个队列总有一个是空的。
- 添加元素总是向非空队列中 add 元素。
- 取出元素的时候总是将元素除队尾最后一个元素外，导入另一空队列中，最后一个元素出队。
接上图我们开看第一次取出操作后可能的两种操作情况：
思路缕清楚了，那么时候写代码了：
public static class TwoQueueStack<E> {
private Queue<E> queueA;
private Queue<E> queueB;
public TwoQueueStack() {
queueA = new LinkedList<>();
queueB = new LinkedList<>();
}
/**
* 选一个非空的队列入队
*
* @param e
* @return
*/
public E push(E e) {
if (queueA.size() != 0) {
System.out.println("从 queueA 入队 " e);
queueA.add(e);
} else if (queueB.size() != 0) {
System.out.println("从 queueB 入队 " e);
queueB.add(e);
} else {
System.out.println("从 queueA 入队 " e);
queueA.add(e);
}
return e;
}
public E pop() {
if (queueA.size() == 0 && queueB.size() == 0) {
return null;
}
E result = null;
if (queueA.size() != 0) {
while (queueA.size() > 0) {
result = queueA.poll();
if (queueA.size() != 0) {
System.out.println("从 queueA 出队 并 queueB 入队 " result);
queueB.add(result);
}
}
System.out.println("从 queueA 出队 " result);
} else {
while (queueB.size() > 0) {
result = queueB.poll();
if (queueB.size() != 0) {
System.out.println("从 queueB 出队 并 queueA 入队 " result);
queueA.add(result);
}
}
System.out.println("从 queueB 出队" result);
}
return result;
}
}
为了方便大家理解我将文章进行下测试：
public static void main(String[] args) {
TwoQueueStack<Integer> queueStack = new TwoQueueStack<>();
queueStack.push(1);
queueStack.push(2);
queueStack.push(3);
queueStack.push(4);
queueStack.pop();
queueStack.pop();
queueStack.push(5);
queueStack.pop();
}
结果为下面所示,看上去我们的代码是对的
从 queueA 入队 1
从 queueA 入队 2
从 queueA 入队 3
从 queueA 入队 4
从 queueA 出队 并 queueB 入队 1
从 queueA 出队 并 queueB 入队 2
从 queueA 出队 并 queueB 入队 3
从 queueA 出队 4
从 queueB 出队 并 queueA 入队 1
从 queueB 出队 并 queueA 入队 2
从 queueB 出队3
从 queueA 入队 5
从 queueA 出队 并 queueB 入队 1
从 queueA 出队 并 queueB 入队 2
从 queueA 出队 5
附C 代码实现：
#include <stdio.h>
#include<queue>
#include<exception>
using namespace std;
template <typename T> class TQueueStack
{
public:
void push(const T& node);
T pop();
private:
queue<T> queueA;
queue<T> queueB;
};
// 插入元素
template<typename T> void TQueueStack<T>::push(const T& node)
{
//插入到非空队列，如果均为空则插入到queueB中
if (queueA.size() == 0)
{
queueB.push(node);
}
else
{
queueA.push(node);
}
}
template<typename T> T TQueueStack<T>::pop()
{
if (queueA.size() == 0 && queueB.size() == 0)
{
return NULL;
}
T head;
if (queueA.size() > 0)
{
while (queueA.size()>1)
{
//queueA中的元素依次删除，并插入到queueB中，其中queueA删除最后一个元素
//相当于从栈中弹出队尾元素
T& data = queueA.front();
queueA.pop();
queueB.push(data);
}
head = queueA.front();
queueA.pop();
}
else
{
while (queueB.size()>1)
{
//queueB 中的元素依次删除，并插入到 queueA 中，其中 queueB 删除最后一个元素
//相当于从栈中弹出队尾元素
T& data = queueB.front();
queueB.pop();
queueA.push(data);
}
head = queueB.front();
queueB.pop();
}
return head;
}
判断出栈顺序是否符合要求（✭✭✭✩✩）
经历了上两道题，大家是不是感觉对栈和队列更反感，哦不对是更了解了呢。（额~ 一不小心把实话说出来了）。下面我们来看第二道题这是一个有关于出栈顺序的判断的题目:
题目: 输入两个整数数组，第一个表示一个栈的压入序列，请写一个函数，判断第二个数组是否为该栈的出栈序列，假设数组中的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
看到这道题我们首先应该去理解题目中的怎么去判断是否符合出栈顺序，其实题目想要表达的意思是如果以数组 A 的方式进栈但并不是一次全部进栈，比如我们先进栈1，2，3，4 然后出栈 4，然后进栈 5，然后在出栈 5，3，2，1。 那么什么情况下是不可能满足的出栈顺序呢？比如 1，肯定是比 2 先进栈的，所以 2肯定比 1先出栈。所以解题的关键就在于，如何判断数组2 中的元素，是按数组1 中某种进栈顺序操作的出栈序列。
思路是如果我们在进栈的同时维护一个出栈角标，如果栈顶元素等于 popA[popIndex] 的时候，将角标加一，并出栈该元素，并继续判断下一个栈顶元素，如果栈顶元素不等于 popA[popIndex] 的时候继续入栈元素，直到所有元素入栈完毕如果，栈不为空则表示 popA 不是一个出栈序列。通过下图可以更好的理解题目要考察的内容：
所以在编程的只需要注意一下三点：
- 执行放入操作后，如果栈顶的元素等于对应角标在 popA 数组中的元素值，那么就需要出栈该元素，同事角标加1
- 如果栈顶的元素不等于对应角标在 popA 数组中的元素值，那么就执行放入操作。
- 待所有的元素都被放入栈中，此时如果栈为空，那么 popA 就是一个出栈序列，反之则不是。
下面看代码实现：
public static class Solution {
public boolean IsPopOrder(int[] pushA, int[] popA) {
int len = pushA.length;
Stack<Integer> stack = new Stack<>();
for (int pushIndex = 0, popIndex = 0; pushIndex < len; pushIndex ) {
stack.push(pushA[pushIndex]);
//如果栈顶元素等于 popA[popIndex] 则一直出栈且 popIndex
while (popIndex < popA.length && popA[popIndex] == stack.peek()) {
stack.pop();
popIndex ;
}
}
return stack.isEmpty();
}
}
C 实现如下：
class Solution {
public:
bool IsPopOrder(vector<int> pushA, vector<int> popA) {
if(pushA() == 0) return false;
vector<int> stack;
for(int i = 0,j = 0 ;i < pushA.size();){
stack.push_back(pushA[i ]);
while(j < popA.size() && stack.back() == popA[j]){
stack.pop_back();
j ;
}
}
return stack.empty();
}
};
测试结果如下：
public static void main(String[] args) {
Solution solution = new Solution();
int[] pushA = new int[]{1, 2, 3, 4, 5};
int[] popA1 = new int[]{4, 3, 5, 1, 2};
int[] popA2 = new int[]{4, 5, 3, 2, 1};
System.out.println("popA1 是否是出栈队列 " solution.IsPopOrder(pushA, popA1));
System.out.println("popA2 是否是出栈队列 " solution.IsPopOrder(pushA, popA2));
}
// 结果
//popA1 是否是出栈队列 false
//popA2 是否是出栈队列 true
总结
本文列举了栈和队列的一些面试题目，通过这些面试题目我们可以了解到一些面试中算法的考点，对于运算相关题目，我们还是需要多加练习，但是不要害怕自己某些地方不会限制了解题思路，通过多加练习，记住见过的解题中的规律，相信经过一段时间练习后，也会感受到自我的提高。
推荐阅读：
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
