网站开发薪资,企业网站建设包括,网站设计一级网页,上海做网站定制题目
图书整理 II 读者来到图书馆排队借还书#xff0c;图书管理员使用两个书车来完成整理借还书的任务。书车中的书从下往上叠加存放#xff0c;图书管理员每次只能拿取书车顶部的书。排队的读者会有两种操作#xff1a; push(bookID)#xff1a;把借阅的书籍还到图书馆。…题目
图书整理 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 {vectorint vec;int head0;
public:CQueue() {}void appendTail(int value) {vec.push_back(value);}int deleteHead() {if(headvec.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 {stackint 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();*/
