队列竟然有如此操作——queue.add( queue.poll() )
使用队列实现栈的下列操作:
-
push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空
栈 是后进先出,队列 是先进先出。
以下涉及剧透,谨慎观看:
我们最主要的工作就是,把队列在队尾新插入的元素,弹出的时候先弹出(后进先出)
代码如下:
public void push(int x) { queue.add(x); for(int i=0;i<queue.size()-1;i++) { queue.add(queue.poll()); } }
我们在往队列里面推入元素的时候,默认是添加到队尾的,然后它会是最后出队列。
骚操作: 把一个元素插入到队尾后,我们将它 之前 的元素全部 出队列再入队列,效果如下:
初始状态每次插入元素的时候,进行如上操作,可以保证刚插入的元素一定是在队首。 插入元素时间复杂度O(N),弹出元素时间复杂度O(1)
后记
一开始看了 剑指offer 的两个栈实现一个队列。然后想当然的认为 队列实现栈,也需要两个队列来完成。没想到队列还有如此骚操作👀