Implement Stack Using Queues

225. 用队列实现栈

分析

每次访问栈顶元素 top() 或弹出栈顶元素 pop() 时，先将队列中的前 size - 1 个元素重新入队，从而把「最后加入的元素」移动到队头，模拟栈顶

push(): O(1)
pop(): O(n)
top(): O(n)
empty(): O(1)

时间复杂度

排序复杂度：O(nlogn)
三重循环复杂度：外层循环 O(n)，内层双指针 O(n)，总复杂度为 O(n^2)

总时间复杂度 O(n^2)

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


class MyStack
{
public:
    std::queue<int> q;

    MyStack() {}

    // 压栈：直接将元素压入队列末尾
    void push(int x)
    {
        q.push(x);
    }

    // 弹栈：将前 size - 1 个元素移至队尾，留下最后一个元素弹出
    int pop()
    {
        int size = q.size();
        while (size-- > 1)
        {
            q.push(q.front());
            q.pop();
        }
        int x = q.front();
        q.pop();
        return x;
    }

    // 查看栈顶：逻辑与 pop 类似，但最后将该元素重新压入队尾
    int top()
    {
        int size = q.size();
        while (size-- > 1)
        {
            q.push(q.front());
            q.pop();
        }
        int x = q.front();
        q.pop();
        q.push(x);
        return x;
    }

    // 判空：直接判断队列是否为空
    bool empty()
    {
        return q.empty();
    }
};