菜单

用队列实现栈

2015年7月23日 - 算法

关于面试中是否应该考算法,众说纷纭,我不站队,美其名曰理性看待,哈哈。说重要的可能他们工作中需要使用大量的算法知识,说不重要的可能他们项目中没有用到什么算法知识,并且用到也已经有现成的库替他们解决了这些算法问题,还没有到需要去优化轮子的地步。如果我是面试官,我只会考最基本的算法概念,更看重一些计算机理论知识、视野、做一件事是否明白主次之分,这些构成个人的整体素质。

用队列实现一个栈,这个题目见过很多次了,但我从没有去实现它的冲动,因我的工作中没有碰到类似的问题,我压根不知道什么时候需要这样去折腾,等到需要的时候再去折腾也还可以,时间精力有限,不可能什么都能提前研究透了。要是说这种题目可以锻炼思维,好吧,那我就锻炼一下,写几行简单的代码来实现这个基于队列的栈。我不知道别人是怎么实现的,有空再看看,我的实现如下,经测试没啥问题:

class Stack {

public:

 

    Stack()

    {

        qnum = 1;

    }

    // Push element x onto stack.

    void push(int x) {

         

        if(q1.empty())

        {

            q1.push(x);

            qnum = 1;

        }

        else if(q2.empty())

        {

            q2.push(x);

            qnum = 2;

        }

        else if(qnum == 1)

        {

            while(!q2.empty())

            {

                q1.push(q2.front());

                q2.pop();

            }

            q2.push(x);

            qnum = 2;

        }

        else if(qnum == 2)

        {

            while(!q1.empty())

            {

                q2.push(q1.front());

                q1.pop();

            }

            q1.push(x);    

            qnum = 1;

        }

    }

 

    // Removes the element on top of the stack.

    void pop() {

         

        if(qnum == 1)

        {

            if(!q1.empty()) q1.pop();

             

            if(q1.empty()) qnum = 2;

        }

        else if(qnum == 2)

        {

            if(!q2.empty()) q2.pop();

             

            if(q2.empty()) qnum = 1;

        }

    }

 

    // Get the top element.

    int top() {

        

        if(qnum == 1)

        {

            if(!q1.empty()) return q1.front();

        }

        else if(qnum == 2)

        {

            if(!q2.empty()) return q2.front();

        }         

    }

 

    // Return whether the stack is empty.

    bool empty() {

         

        return q1.empty() && q2.empty();

    }

     

private:

 

    queue<int> q1;

    queue<int> q2;

     

    int qnum;

};



发表评论