题目

图书整理 II
读者来到图书馆排队借还书，图书管理员使用两个书车来完成整理借还书的任务。书车中的书从下往上叠加存放，图书管理员每次只能拿取书车顶部的书。排队的读者会有两种操作：

• push(bookID)：把借阅的书籍还到图书馆。
• pop()：从图书馆中借出书籍。

为了保持图书的顺序，图书管理员每次取出供读者借阅的书籍是最早归还到图书馆的书籍。你需要返回每次读者借出书的值。

如果没有归还的书可以取出，返回 -1。

示例 1：

输入： [“BookQueue”, “push”, “push”, “pop”] [[], [1], [2], []]
输出：[null,null,null,1] 解释： MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2]
(leftmost is front of the queue) myQueue.pop(); // return 1, queue is
[2]

提示：

1 <= bookID <= 10000 最多会对 push、pop 进行 10000 次调用

思考

• 本题其实就是要求实现队列以及队列的入队函数和出队函数
• 按题目的要求，实际上是要求使用两个栈（两个书车）来实现队列
• 但是解法1 没用用栈

解法1：使用 vector 实现

class CQueue {
    vector<int> vec;
    int head=0;
public:
    CQueue() {
        
    }
    
    void appendTail(int value) {
        vec.push_back(value);
    }
    
    int deleteHead() {
        if(head<vec.size()){
            return vec[head++];
        }
        return -1;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

解法2：使用 stack 实现

• 本质上是用另一个栈实现对另一个栈中元素的倒序
• 在倒序栈中，如果还有元素，在出队的时候直接 pop 即可，因为此时倒序栈中的元素还是较早入队的元素
• 直到倒序栈中没有元素，再将顺序栈中的元素放入倒序栈

class CQueue {
    stack<int> a, b;
public:
    CQueue() {}
    
    void appendTail(int value) {
        a.push(value);
    }
    
    int deleteHead() {
        if(a.empty() && b.empty()) return -1;
        if(b.empty() && !a.empty()){
            while(!a.empty()){
                b.push(a.top());
                a.pop();
            } 
        }
        int temp = b.top();
        b.pop();
        return temp;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */