【数据结构与算法】7.详解队列的基本操作
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);
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-05-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录