已知队列(Queue)支持先进先出的操作addremove

[问答题]

已知队列(Queue)支持先进先出的操作add/remove，而栈(Stack)则支持先进后出的操作push/pop，请用两个队列实现栈先进后出的操作，希望该栈的push/pop时间复杂度尽量小。

1) 简述思路(3分)

2) 已知这两个队列的容量为M,该栈的容量是多少(1分)

3) 假设队列的每次Add/Remove操作时间复杂度O(1)，N代表存储在栈里的元素个数，请评估该栈的push/pop操作时间复杂度(1分)
4) 写出push/pop的代码，需要考虑栈溢出(stackoverflow)的情况(3分)

马客(Mark)

“用队列模拟栈” 估计也只有在做题时能看到这种奇葩的需求。。。稍微优化了一点点。

push是O(1)的，同时保证q[cur]的size <= 1，这样能在pop最近一个push的元素时做到O(1)（但总的时间是没变的，只量把一些两个队列之间的pop和push提前做了），其他情况还是O(n)

#include <queue>
template<typename T> class MyStack{
private:
    std::queue<T> q[2];
    int cur;
    void check(){
        if(q[cur].empty() && !q[!cur].empty()){
            while(q[!cur].size() > 1) q[cur].push(q[!cur].front()), q[!cur].pop();
            cur = !cur;
   }
    }
public:
    MyStack() : cur(0) { }
    unsigned int size() const { return q[0].size() + q[1].size(); }
    bool empty() const { return q[0].empty() && q[1].empty(); }
    void push(const T& e){    //O(1)
         if(!q[cur].empty()) q[!cur].push(q[cur].front()), q[cur].pop();
          q[cur].push(e);
    }
    const T& top() {
        check();
        return q[cur].front();
    }
    void pop() {
        check();
        q[cur].pop();
    }
}

编辑于 2015-10-13 17:33:22 回复(0)

yql

楼上思路正确.

但是还是可以改进.

思路:由于队列和栈进出相反. 后进的需要先出, 每次需要把队尾的元素出队,必然要把除了队尾的元素之外的元素,先找地方(d2)保存起来. 下一次出队的时候,同样道理,.

进队时,两个队列d1,d2的状态必然是 : 一个为空 , 另一个装元素. 将需要进队的元素直接插入非空那个队列队尾.

出队时, 将非空队列的除去最后一个元素外的所以元素都放到另一个空队列中,在将最后一个出队...整个过程就是倒腾过来 , 倒腾过去.

但是要知道 , 两个队列是交替做临时队列的 , 而不是说每次都用d2做临时存储,然后出队完还要把d2中的东西还给d1,这是不需要的! 因为下次你用d1做存储区不就行了么..不用还回去!!!这就是优化点!

编辑于 2015-09-19 16:36:19 回复(0)

来学习的小张

用两个队列来模拟栈的实现，总是在不为空的队列里面进行操作，如果刚开始两个队列都为空，则指定一个队列进行入栈操作。

在弹栈时，选择不为空的队列进行操作，将队列中得元素依次出队放到另一个队列中，直到

剩下最后一个元素未出队，再把这最后一个元素出队即可认为弹栈成功。

在获取栈顶元素时，依旧是选择不为空的队列进行操作，将队列中得元素依次出队放到另一个队列中并记录下每次出队的元素，直到出到最后一个元素，返回这最后一个元素的值。

class MyStack {
    //初始化两个队列
    private  Queue<Integer> que1;
    private  Queue<Integer> que2;
    public MyStack() {
       que1 = new LinkedList<>();
       que2 = new LinkedList<>();
    }
    public void push(int x){
        if(que1 != isEmpty()){
            que1.offer(x);
        }else if(que2 != isEmpty()){
            que2.offer(x);
        }else{
            que1.offer(x);
        }
    }
    public int pop(){
        if(empty()){
            return -1;
        }
        if(que1 != isEmpty()){
             int size = que1.size();
            for(int i = 0; i < size - 1;i++){
            int x = que1.poll();
            que2.offer(x);
             }
            return que1.poll();
        }
        if(que2 != isEmpty()){
             int size = que2.size();
            for(int i = 0; i < size - 1;i++){
            int x = que2.poll();
            que1.offer(x);
             }
            return que2.poll();
        }
    }

    public int top(){
         if(empty()){
            return -1;
        }
        if(que1 != isEmpty()){
             int size = que1.size();
            int x = -1;
            for(int i = 0; i < size;i++){
            x = que1.poll();
            que2.offer(x);
             }
            return x;
        }
        if(que2 != isEmpty()){
            int x = -1;
             int size = que2.size();
            for(int i = 0; i < size;i++){
             x = que2.poll();
            que1.offer(x);
             }
            return x;
        }
    }
    public boolean empty(){
        return que1.isEmpty() && que2.isEmpty();
    }
}

编辑于 2022-01-09 16:30:45 回复(0)

若水/爆米花

思路:
有两个队列s1,s2
1 栈的push 操作就用队列s1的push操作
2 出栈:
当s1的size为>1,先将s1的序列出队到s2,当s1的size为1,也即s1剩最后一个元素时,
用一个变量将其保存,并出队.然后将s2的元素又全部转回s1,s2充当了一个中转的作用,
# include <string.h>

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
template<typename T>
class mystack
{
public:
mystack() {}
~mystack() {}
void push(T &t ) {s1.push(t);}
T top()
{
while(s1.size() >1)
{
s2.push(s1.front());
s1.pop();
}
T temp = s1.front();
s1.pop();
while(s2.size())
{
s1.push(s2.front());
s2.pop();
}
return temp;
}
private:
queue<T> s1,s2;
};
int main()
{
int n = 10;
mystack<int> s;
for (int i = 0; i < n; ++i)
{
s.push(i);
}
for (int i = 0; i < n; ++i)
{
cout<<s.top()<<" ";
}
}

编辑于 2015-06-23 21:33:37 回复(0)

提交观点

问题信息

美团栈队列

上传者：覆水难收LE

难度：

4条回答 3收藏 29054浏览

已知队列(Queue)支持先进先出的操作addremove

问题信息

热门推荐

相关试题