LCR 125. 图书整理 II (opens new window)

题目：

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

• 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 次调用

解题：

方法一：双栈法

将一个栈当作输入栈，用于压入 appendTail 传入的数据；另一个栈当作输出栈，用于 deleteHead 操作。

每次 deleteHead 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

1. 加入队尾 appendTail() ： 将数字 val 加入栈 A 即可。

2. 删除队首deleteHead() ： 有以下三种情况。

   1. 当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
   2. 否则，当 A 为空： 即两个栈都为空，无元素，因此返回 -1 。
   3. 否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。

class CQueue {
private:
    stack<int> inStack,outStack;
    void in2out(){
        while(!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }
public:
    CQueue() {

    }
    
    void appendTail(int value) {
        inStack.push(value);
    }
    
    int deleteHead() {
        if(outStack.empty()) {
            if(inStack.empty()) {
                return -1;
            }
            in2out();
        }
        int value = outStack.top();
        outStack.pop();
        return value;
    }
};

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