Implement Queue Using Stacks

232. 栈实现队列

分析

使用两个栈：
- stk：用于存储新加入的元素（输入栈）
- cache：用于临时反转栈 stk 中的顺序，以模拟队列的出队（输出栈）
实现方式：
- push(x)：直接压入 stk
- pop() / peek()：
  1. 把 stk 中的所有元素依次压入 cache，此时顺序反转
  2. cache.top() 就是队列头部元素
  3. 取出元素后，再把所有元素放回 stk，保持结构还原
- empty()：只需判断 stk 是否为空

时间复杂度

push(): O(1)
pop()/peek(): O(n)
empty(): O(1)

C++代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101


class MyQueue
{
public:
    std::stack<int> stk, cache; // stk是输入栈，cache是输出栈

    MyQueue() {}

    void push(int x)
    {
        stk.push(x); // 直接压入输入栈
    }

    int pop()
    {
        // 将 stk 中所有元素转移到 cache 中
        while (stk.size())
        {
            cache.push(stk.top());
            stk.pop();
        }
        int x = cache.top(); // 弹出队头元素
        cache.pop();

        // 将剩余元素放回 stk
        while (cache.size())
        {
            stk.push(cache.top());
            cache.pop();
        }
        return x;
    }

    int peek()
    {
        while (stk.size())
        {
            cache.push(stk.top());
            stk.pop();
        }
        int x = cache.top(); // 查看队头元素但不删除

        while (cache.size())
        {
            stk.push(cache.top());
            cache.pop();
        }
        return x;
    }

    bool empty()
    {
        return stk.empty();
    }
};

// 优化，引入惰性转移（懒加载）策略，只在 cache 为空时才转移元素
class MyQueue
{
public:
    std::stack<int> stk, cache;

    MyQueue() {}

    void push(int x)
    {
        stk.push(x);
    }

    int pop()
    {
        if (cache.empty())
        {
            while (!stk.empty())
            {
                cache.push(stk.top());
                stk.pop();
            }
        }
        int x = cache.top();
        cache.pop();
        return x;
    }

    int peek()
    {
        if (cache.empty())
        {
            while (!stk.empty())
            {
                cache.push(stk.top());
                stk.pop();
            }
        }
        return cache.top();
    }

    bool empty()
    {
        return stk.empty() && cache.empty();
    }
};