一、队列的概念
类似我们现实生活中的在食堂排队打饭，排队靠前的先打饭，他为什么排队靠前呢，就是因为他先进行排队，名次靠前，才轮到他打饭，如图：
而队列是先进先出的数据结构，先放进去队列里的元素先出来，和栈的先进后出不同，类似上面的食堂排队打饭的例子。
我们自定义一个MyQueue类，里面有双向链表ListNode类，链表里面有存放数据的val变量，next域和prev域，记录头结点的head和尾节点的last，还有记录链表元素个数的usedSize，代码如下：
public class MyQueue implements IQueue{ class ListNode { public int value; public ListNode prev; public ListNode next; public ListNode(int value) { this.value = value; } } ListNode head; ListNode last; int usedSize; }
二、队列的接口
代码如下：
public interface IQueue { public boolean offer(int x); public int poll(); public int peek(); public int size(); public boolean isEmpty(); }
三、队列的方法实现
（1）offer方法
此方法是入队列方法，首先要创建一个链表node，判断链表中为不为空，如果是空，就把head和last定义成node，usedSize++；如果不为空，就要尾差，把last.next变成node，node.prev变成last，最后再把last = node，usedSize++，代码如下：
public boolean offer(int x) { ListNode node = new ListNode(x); if(head == null) { head = node; last = node; } else { last.next = node; node.prev = last; last = last.next; } usedSize++; return true; }
执行效果如下：
队列个数usedSize = 2，链表有两个节点。
（2）poll方法
此方法是出队列方法，首先判断链表是不是空，如果是空就出不了队列，抛异常；如果不为空，就判断head.next为不为空，也就是判断队列是不是只有一个元素，如果只有一个元素，就取出头结点的val值，再把head和last置为空，usedSize--；如果有多个元素，就取出头结点的val值，把头结点的next置为空，头结点往后走一步，头结点的prev置空，usedSize--。代码如下：
public int poll() { if(head == null) { //队列为空，出不了队列，抛异常 throw new EmptyException("队列为空"); } if(head.next == null) { int retValue = head.value; last = null; head = null; usedSize--; return retValue; } int retValue = head.value; ListNode nodeNext = this.head.next; head.next = null; nodeNext.prev = null; head = nodeNext; usedSize--; return retValue; } //自定义异常类 public class EmptyException extends RuntimeException{ public EmptyException(String msg) { super(msg); } }
执行效果如下：
出队列三次，把队列出完，如果里面没元素了，就会抛异常。
（3）peek方法
此方法是取出队列的首元素，但不删除。首先要判断队列是不是空的，是空的就抛异常，不为空就返回队首元素val值，代码如下：
public int peek() { if(head == null) { //队列为空，出不了队列，抛异常 throw new EmptyException("队列为空"); } else { int retValue = head.value; return retValue; } } //自定义异常类 public class EmptyException extends RuntimeException{ public EmptyException(String msg) { super(msg); } }
执行效果如下：
只拿队列首元素，不出队列。
（4）size方法
直接返回usedSize，代码如下：
public int size() { return usedSize; }
执行效果如下：
返回队列元素的个数。
（5）isEmpty方法
直接返回head == null，代码如下：
public boolean isEmpty() { return this.head == null; }
执行效果如下：
判断队列是否为空。
四、最终代码
//自定义接口 public interface IQueue { public boolean offer(int x); public int poll(); public int peek(); public int size(); public boolean isEmpty(); } //MyQueue类 public class MyQueue implements IQueue{ class ListNode { public int value; public ListNode prev; public ListNode next; public ListNode(int value) { this.value = value; } } ListNode head; ListNode last; int usedSize; @Override public boolean offer(int x) { ListNode node = new ListNode(x); if(head == null) { head = node; last = node; } else { last.next = node; node.prev = last; last = last.next; } usedSize++; return true; } @Override public int poll() { if(head == null) { //队列为空，出不了队列，抛异常 throw new EmptyException("队列为空"); } if(head.next == null) { int retValue = head.value; last = null; head = null; usedSize--; return retValue; } int retValue = head.value; ListNode nodeNext = this.head.next; head.next = null; nodeNext.prev = null; head = nodeNext; usedSize--; return retValue; } @Override public int peek() { if(head == null) { //队列为空，出不了队列，抛异常 throw new EmptyException("队列为空"); } else { int retValue = head.value; return retValue; } } @Override public int size() { return usedSize; } @Override public boolean isEmpty() { return this.head == null; } } //自定义异常类 public class EmptyException extends RuntimeException{ public EmptyException(String msg) { super(msg); } }
