队列竟然有如此操作——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());
       }
    }

我们在往队列里面推入元素的时候,默认是添加到队尾的,然后它会是最后出队列。

骚操作: 把一个元素插入到队尾后,我们将它 之前 的元素全部 出队列再入队列,效果如下:

初始状态 1 2 3 4
队尾添加一个 5 1 2 3 4 5
1 出队列在入队列 2 3 4 5 1
依次循环 ... 5 1 2 3 4

每次插入元素的时候,进行如上操作,可以保证刚插入的元素一定是在队首。 插入元素时间复杂度O(N),弹出元素时间复杂度O(1)


后记

一开始看了 剑指offer 的两个栈实现一个队列。然后想当然的认为 队列实现栈,也需要两个队列来完成。没想到队列还有如此骚操作👀

经验分享 程序员 微信小程序 职场和发展