VIRTUALS

the virtual labs for the virtuals

0%

剑指Offer 09. 用两个栈实现队列

Posted on Edited on In , , ,

摘要：
用两个栈模拟队列，栈结构入门题，很蛋疼的设计。

题目

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

示例 1：

输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出： [null,null,3,-1]

示例 2：

输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出： [null,-1,null,null,5,2]

提示：

  • $1 <= values <= 10000$
  • 最多会对 appendTail、deleteHead 进行 $10000$ 次调用

用两个栈模拟队列，一个放的是正序序列，一个是倒序序列。分别用作队列的插入队尾和删除队首操作。

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
/*
 * 2021-6-24 21:08:04
 * author: etoa
 */
class CQueue {
public:
    static constexpr int N = 10010;
    int stk1[N], stk2[N];
    int tt1, tt2;
    CQueue() {
        tt1 = 0;
        tt2 = 0;
    }
    
    void appendTail(int value) {
        stk1[++tt1] = value;
    }
    
    int deleteHead() {
        if (!tt2) {
            if (!tt1) return -1;
            else {  // dump
                for (; tt1; --tt1) {
                    stk2[++tt2] = stk1[tt1];
                }
            }
        }
        return stk2[tt2--];
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
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
// 执行用时: 364 ms
// 内存消耗: 101.2 MB
class CQueue {
public:
    stack<int> stkTail;
    stack<int> stkHead;
    CQueue() {
        
    }
    
    void appendTail(int value) {
        stkTail.push(value);
    }
     
    int deleteHead() {
        if (stkHead.empty()) {
            if (stkTail.empty()) return -1;
            for (; !stkTail.empty(); stkTail.pop()) stkHead.push(stkTail.top());
        }
        int res = stkHead.top();
        stkHead.pop();
        return res;
    }
};
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
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
// 执行用时: 53 ms
// 内存消耗: 47.3 MB
class CQueue {
    Deque<Integer> stk1 = new LinkedList<>();
    Deque<Integer> stk2 = new LinkedList<>();

    public CQueue() {

    }
    
    public void appendTail(int value) {
        stk2.addLast(value);
    }
    
    public int deleteHead() {
        if (stk1.size() == 0) {
            if (stk2.size() == 0) return -1;
            for (; stk2.size() != 0; ) stk1.addLast(stk2.removeLast());
        }
        return stk1.removeLast();
    }
}
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

原题链接： 剑指Offer 09. 用两个栈实现队列