【算法实现】用栈结构实现队列功能
题目
读者来到图书馆排队借还书，图书管理员使用两个书车来完成整理借还书的任务。书车中的书从下往上叠加存放，图书管理员每次只能拿取书车顶部的书。排队的读者会有两种操作：
- push(bookID)：把借阅的书籍还到图书馆。
- pop()：从图书馆中借出书籍。
为了保持图书的顺序，图书管理员每次取出供读者借阅的书籍是 最早 归还到图书馆的书籍。你需要返回 每次读者借出书的值 。 如果没有归还的书可以取出，返回 -1 。
思考
队列的特点是先进先出,栈的特点是先进后出。要利用栈实现队列功能,需要使用两个栈来协作。 一个栈用于入队,直接将元素 push 进去。一个栈用于出队,当这个栈为空时,需要先将入队栈的所有元素 pop 并 push 进出队栈,这样出队栈的头部元素就是队列的头部元素。
算法实现
- 定义入队栈 inputStack 和出队栈 outputStack
- appendTail 直接 push 入 inputStack
- deleteHead 先判断 outputStack 是否为空。如果为空,则将 inputStack 的元素 pop 到 outputStack
- outputStack 弹出头部元素返回。如果两个栈均为空则返回 -1
class CQueue {
Deque<Integer> inputStack;
Deque<Integer> outputStack;
public CQueue() {
inputStack = new LinkedList<Integer>();
outputStack = new LinkedList<Integer>();
}
public void appendTail(int value) {
inputStack.push(value);
}
public int deleteHead() {
if (outputStack.isEmpty()) {
while (!inputStack.isEmpty()) {
outputStack.push(inputStack.pop());
}
}
if (outputStack.isEmpty()) {
return -1;
} else {
return outputStack.pop();
}
}
}