4.19两个栈实现队列 - WisperDin/blog GitHub Wiki

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型

思路

栈是LIFO的逻辑结构，队列是FIFO的逻辑结构，要使用栈还原队列的操作，关键的一点是 保序

将队列push时的顺序 在队列pop前还原出来 ，根据这一点继续思考，假定先使用一个栈接受队列的push，当需要pop时，需要将栈中的元素从栈顶逐个pop出，push到另一个栈中，以还原队列push时的顺序

具体实现

stack1 来存 队列的push保存

stack2 用来pop前还原队列的顺序

Push: 直接push到stack1

Pop:

  • 如果stack2为空，将stack1逐个pop出，push到stack2中，最后pop出stack2栈顶元素
  • 如果stack2不为空，直接pop出stack2栈顶元素

难点

在于使用stack2还原队列顺序时，在stack2重建顺序后，在后续队列的push时，相当与此时队列被分成了两部分分别存储在stack1，stack2；

比如操作序列：

PUSH 1
PUSH 4
PUSH 2
POP 1
PUSH 9

根据上述思路，此时(最底下表示栈底)

stack1：

9

stack2:

4

2

当前队列的顺序为: 4 2 9

队列队头开始的局部进行了保序！！

每一次当stack2为空重建顺序时，重建的元素可用至全部POP出为止

代码实现

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty()){
            //将stack1 全pop 按pop顺序 push 到stack2
            int stack1Len = stack1.size();
            for (int i=0; i < stack1Len ; i++){
                int tmpTop = stack1.top();
                stack1.pop();
                stack2.push(tmpTop);
            }
        }
        //弹出stack2栈顶元素
        int popVal = stack2.top();
        stack2.pop();
        return popVal;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

变式：两个队列实现栈

思路

由于队列出队再入队顺序不会变更,所以采用每次出队直至剩最后一个元素,再pop该元素来模拟栈的pop,所以每次做一次栈的pop,数据都会流到另一个队列中,只剩一个作为pop的元素

class Solution
{
public:
    void push(int node) {
        //若有非空queue 选择它来push,否则就随便
        queue<int>* pQueue = &queue1;
        if(!queue2.empty()){
            pQueue = &queue2;
        }
        (*pQueue).push(node);
    }

    int pop() {

        if(queue2.empty()){
            //queue2为空,就从queue1 pop出queue1.size()-1个元素push到queue2 
            //pop出queue1最后一个元素返回
            return popIner(&queue2,&queue1);
        }
        if(queue1.empty()){
            //queue1为空,就从queue2 pop出queue2.size()-1个元素push到queue1 
            //pop出queue2最后一个元素返回
            return popIner(&queue1,&queue2);
        }
        return 0;
    }

private:
    queue<int> queue1;
    queue<int> queue2;
    int popIner (queue<int>* emptyQueue,queue<int>* notEmpryQueue){
        int notEmptyLen = notEmpryQueue->size();
        for (int i=0;i<notEmptyLen-1;i++){
            int tmpVal = notEmpryQueue->front();
            notEmpryQueue->pop();
            emptyQueue->push(tmpVal);
        }
        int lastVal = notEmpryQueue->front();
        notEmpryQueue->pop();
        return lastVal;
    }
};

总结

  1. 栈的LIFO特性其实也可以理解成倒序输出
  2. 队列的FIFO特性也可以理解为始终保序输出
⚠️ **GitHub.com Fallback** ⚠️