剑指offer刷题笔记——用两个栈实现队列

yangxiaodong 2019-01-13 PM 43℃ 0条

题目描述

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

问题分析

根据栈先进后出的原则,队列先进先出的原则。如果用两个栈做队列,那么一个栈用来一次性存放数据,存入数据后在一次性全部弹入另一个栈中,另一个栈在弹出,则就可以实现先进先出的队列了。

思路

思路很简单,但是实际必须做到以下两点(摘自《程序员代码面试指南》)

  1. 建立两个栈,stackPush和stackPop。一个用来压栈,一个用来弹栈,按照分析思路即可
  • 注意1:如果stackPush要往stackPop中压入数据,那么必须一次性把stackPush中的数据全部压入。
  • 注意2:如果stackPop不为空,stackPush绝对不能向stackPop中压入数据。
    违反举例:

违反1,1~5依次压入stackPush,stackPush的栈顶到栈底依次为5~1,从stackPush压入stackPop中时,如果没有全部压完,如果此时用户想做弹栈操作时,会出错。
违反2,1~5依次压入stackPush,stackPush将所有数据压入stackPop,此时stackPop的栈顶到栈底为1~5。此时又有6~10压入stackPush,stackPop不为空,则无法压入。(压入报错,自己想为什么呢?嘻嘻(-。-)

代码

C++代码

class Solution
{
public:
    void push(int node) {
        stack1.push(node); //一次性全部压入完
    }

    int pop() {
        int tmp;
        if(stack2.empty()) //为空才压入
        {
            while(!stack1.empty())
            {
                tmp = stack1.top();
                stack2.push(tmp);
                stack1.pop();
            }
        }
        tmp = stack2.top();
        stack2.pop();
        return tmp;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};
标签: none

非特殊说明,本博所有文章均为博主原创。

评论啦~