算法刷题目栈和队列
Source
Edit
History

由两个栈组成的队列

由两个栈组成的队列

一、题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

leetcode：https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

二、实现思路

  • 两个栈，一个栈 A 只用来进元素，一个栈 B 只用来出元素
  • 进的时候，只通过栈 A。出的时候
    • 如果栈 B 没有元素，则先将栈 A 的元素全部进到栈 B 中，然后再从栈 B 中出。
    • 如果栈 B 有元素，直接从栈 B 出

三、代码

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
#include <stack>
#include <iostream>

class CQueue {
public:
    CQueue() {

    }

    void appendTail(int value) {
        push_stack_.push(value);
    }

    int deleteHead() {
        if (pop_stack_.empty() && push_stack_.empty()) {
            return -1;
        }
        if (pop_stack_.empty()) {
            while (!push_stack_.empty()) {
                pop_stack_.push(push_stack_.top());
                push_stack_.pop();
            }
        }
        int val = pop_stack_.top();
        pop_stack_.pop();
        return val;
    }

private:
    std::stack<int> push_stack_;
    std::stack<int> pop_stack_;
};

int main() {
    CQueue c;
    std::cout << c.deleteHead() << std::endl;
    c.appendTail(5);
    c.appendTail(2);
    std::cout << c.deleteHead() << std::endl;
    std::cout << c.deleteHead() << std::endl;
}
  • 时间复杂度, appendTail: O(1)，deleteHead：O(n)
  • 空间复杂度：O(n)