【数据结构与算法】7.详解队列的基本操作

1. 队列

1.1 队列的概念

像栈一样，队列也是表。然而，使用队列是插入在一端进行而删除则在另一端进行。

队列的基本操作的是入队，它是在表的末端（队尾）插入一个元素，和出队，它是删除（并返回）表的开头元素。

1.2 队列的使用

2. 模拟实现

定义双向链表类

定义两个指针，分别指向头节点和尾节点

入队（offer）

判断队列是否为空，如果为空，将新节点设置为头节点，将新节点设置为尾节点

如果队列不为空，将最后一个节点last的next域指向新节点，新节点的prev域指向最后一个节点，更新尾节点为新节点

代码：

出队（poll）

判断队列是否为空，如果为空则抛出异常

如果队列只有一个元素，则移除该元素并返回该元素，同时将head和last置为空，返回移除元素的值

如果队列有多个元素，则移除头元素并返回该元素的值，将头节点指向头节点的下一个节点，将头节点的prev置为空，返回移除元素的值

代码：

获取队头元素（peek）

判断队列是否为空，如果为空，则抛出异常

如果不为空，则返回队头元素的值

代码：

获取队列中有效元素个数

遍历队列计算元素个数并返回

代码：

检测队列是否为空

判断队列的头节点是否为空，如果为空，则队列为空

3.完整代码

MyQueue类：

异常类：