用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
思路:创建两个栈,一个实现队列的 插入操作,一个实现队列的 删除操作。、
如何实现?首先明白,栈是先进后出,队列是先进先出。
队列进行插入操作时,相当于进栈,队列进行删除操作时,相当于删除栈中最底层的元素,此时需要把栈里面的元素全部弹出来放到第二个空白的栈中,这个第二个栈的第一个元素就是队列要删除的元素了。
空有理论不行,实操的话又弱点,还是参考大佬的代码吧。
实现:
参考大佬的解法:
class CQueue {
LinkedList<Integer> A, B;
public CQueue() {
A = new LinkedList<Integer>();
B = new LinkedList<Integer>();
}
public void appendTail(int value) {
A.addLast(value);
}
public int deleteHead() {
if(!B.isEmpty()) return B.removeLast();
if(A.isEmpty()) return -1;
while(!A.isEmpty())
B.addLast(A.removeLast());
return B.removeLast();
}
}
作者:jyd
链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
这里用 LinkedList 看作栈来使用,虽然我也不知道为什么, 我又去看查 了一下 LinkedList,它的源码定义是这样的:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
继承了 AbstractSequentialList, 实现了实现 List (列表)、Deque(双端队列、允许两头进,两头出)、Cloneable、Serializable。
上面涉及的知识更复杂了,但是不重要,我们先看 它的一些方法的实现:
添加方法:addLast(): 将指定元素添加到此列表的结尾
移除方法:removeLast():移除并返回此列表的最后一个元素。
网友评论