队列的特点是先进先出,栈的特点是先进后出。
题目描述
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail
和 deleteHead
,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead
操作返回 -1
)
题解以及实现思路
两个栈,stack1
stack2
;
stack1
负责存储数据
stack2
负责删除数据
根据栈的先进后出原则,stack1
调用pop()
函数时,弹出的是最新存储的元素,然后分发给stack2
接收,然后'stack2'再调用'pop()'弹出的就是队列的头部。
实现代码
class CQuene {
LinkedList<Integer> stack1;
LinkedList<Integer> stack2;
public CQuene(){
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
/**
往stack1里面添加数组
**/
public void apendToTail(int value) {
stack1.add(value);
}
/**
删除队列 如果stack2为空,并且stack1也为空,说明是空队列,返回-1
如果stack2为空, stack1 不为空,stack1 调用pop 给 stack2 然后 stack2 调用pop 删除队列的头部
**/
public int deleteHead() {
if (stack2.isEmpty()) {
if(stack1.isEmpty()) return -1;
while (stack1.isEmpty()){
stack2.add(stack1.pop());
}
return stack2.pop();
}
return stack2.pop();
}
}