一.简介

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

二.示例

2.1 用队列实现栈

使用队列实现栈的下列操作

• push(x) -- 元素 x 入栈

• pop() -- 移除栈顶元素

• top() -- 获取栈顶元素

• empty() -- 返回栈是否为空

注意

• 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

第一种

public class MyQueue {
    Queue s1= new LinkedList<>();
    Queue s2= new LinkedList<>();
    public MyQueue() {
    }
    /**
     * 将元素x推导队列的末尾
     * @param x
     */
    public void  push(int x){
        while (!s1.isEmpty()){
            s2.offer(s1.poll());
        }
        s1.offer(x);
        while (!s2.isEmpty()){
            s1.offer(s2.poll());
        }
    }
    /**
     * 从队列的开头移除并返回元素
     * @return
     */
    public int pop(){
        return s1.poll();
    }
    /**
     * 返回队列开头元素
     * @return
     */
    public int peek(){
        return s1.peek();
    }
    /**
     * 如果队列为空，返回true ,否则 false
     * @return
     */
    public boolean empty(){
        return !s1.isEmpty() && !s2.isEmpty();
    }
}

第二种方法

public class MyQueue {
Queue s1= new LinkedList<>();
public void  push(int x){
    //移多少位
    int size = s1.size();
    //根据遍历，每次把前面的结点，放到后面，留有一个头结点
    //留有一个头结点
    s1.offer(x);
    for (int i = 0; i < size; i++) {
      s1.offer(s1.poll());
    }
}
public int pop(){
return s1.poll();
}
public int peek(){
return s1.peek();
}
public boolean empty(){
return s1.isEmpty();
}
}