1. 队列
1.1 队列的概念
像栈一样，队列也是表。然而，使用队列是插入在一端进行而删除则在另一端进行。
队列的基本操作的是入队，它是在表的末端（队尾）插入一个元素，和出队，它是删除（并返回）表的开头元素。
1.2 队列的使用
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
2. 模拟实现
定义双向链表类
static class ListNode { public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } }
定义两个指针，分别指向头节点和尾节点
public ListNode head; public ListNode last;
入队（offer）
- 判断队列是否为空，如果为空，将新节点设置为头节点，将新节点设置为尾节点
head = last = node;
- 如果队列不为空，将最后一个节点
last的next域指向新节点，新节点的prev域指向最后一个节点，更新尾节点为新节点
last.next = node; node.prev = last; last = node;
代码：
/** * 入队 * @param val */ public void offer(int val) { ListNode node = new ListNode(val); if (head == null) { head = last = node; } else { last.next = node; node.prev = last; last = node; } }
出队（poll）
- 判断队列是否为空，如果为空则抛出异常
if (head == null) { throw new RuntimeException("队列为空"); }
- 如果队列只有一个元素，则移除该元素并返回该元素，同时将
head和last置为空，返回移除元素的值
// 链表中只有一个元素 int val = head.val; if (head == last) { head = null; last = null; return val; }
- 如果队列有多个元素，则移除头元素并返回该元素的值，将头节点指向头节点的下一个节点，将头节点的
prev置为空，返回移除元素的值
head = head.next; head.prev = null; return val;
代码：
/** * 出队 */ public int poll() { // 判断链表中是否有元素 if (head == null) { throw new RuntimeException("队列为空"); } // 链表中只有一个元素 int val = head.val; if (head == last) { head = null; last = null; return val; } head = head.next; head.prev = null; return val; }
获取队头元素（peek）
- 判断队列是否为空，如果为空，则抛出异常
if (head == null) { throw new RuntimeException("队列为空"); }
- 如果不为空，则返回队头元素的值
return head.val;
代码：
/** * 获取队头元素 * @return */ public int peek() { if (head == null) { throw new RuntimeException("队列为空"); } return head.val; }
获取队列中有效元素个数
遍历队列计算元素个数并返回
代码：
/** * 获取队列有效元素个数 * @return */ public int size() { int count = 0; ListNode cur = head; while (cur != null) { count++; cur = cur.next; } return count; }
检测队列是否为空
判断队列的头节点是否为空，如果为空，则队列为空
/** * 判断队列是否为空 * @return */ public boolean isEmpty() { return head == null; }
3.完整代码
MyQueue类：
public class MyQueue { static class ListNode { public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; /** * 入队 * @param val */ public void offer(int val) { ListNode node = new ListNode(val); if (head == null) { head = last = node; } else { last.next = node; node.prev = last; last = node; } } /** * 出队 */ public int poll() { // 判断链表中是否有元素 if (head == null) { throw new RuntimeException("队列为空"); } // 链表中只有一个元素 int val = head.val; if (head == last) { head = null; last = null; return val; } head = head.next; head.prev = null; return val; } /** * 获取队头元素 * @return */ public int peek() { if (head == null) { throw new RuntimeException("队列为空"); } return head.val; } /** * 获取队列有效元素个数 * @return */ public int size() { int count = 0; ListNode cur = head; while (cur != null) { count++; cur = cur.next; } return count; } /** * 判断队列是否为空 * @return */ public boolean isEmpty() { return head == null; } }
异常类：
public class EmptyQueueException extends RuntimeException{ public EmptyQueueException() { } public EmptyQueueException(String message) { super(message); } }
