【数据结构】受限制的线性表——队列

🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧上一篇文章：特殊的线性表——栈🎈🎈🎈🎈🎈

文章目录

• 前言
• • 1.队列(Queue)
  • 1.1队列的概念
  • 2.2 队列的使用
  • 2.3 队列模拟实现
  • 2.4 循环队列
  • • 3. 双端队列 (Deque)

前言

上一章我们讲了一种特殊的线性表只能在表尾进行插入和删除操作，接下来我们讲一个和栈很相似的数据结构，它也是一种特殊且所限制的线性表，它是只能在表头删除操作在表尾进行插入操作。

1.队列(Queue)

1.1队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头

2.2 队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。


注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

2.3 队列模拟实现

我们这里通过链表来实现队列：
1.我们先将链表的框架搭建一下，代码如下：

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; }  

2.方法的实现：

2.1入队(offer)

//offer 入队     public void offer(int val) {             ListNode node = new ListNode(val);         //1.空节点         if(head == null) {                 head = node;             last = node;         } else {                 //2.不为空节点，尾插法。             last.next = node;             node.prev = last;             last = node;         }     } 

2.2 出队(poll)

   //poll 出队     public int poll() {             //1.判断队是否为空         if(isEmpty()) {                 //1.1队为空,抛出队为空的异常            throw new QueueEmptyException("队空异常！！！！");         } else {                 //2.队中是否只有一个元素             int val = head.val;             if(head.next == null) {                     //2.1只有一个元素                 head = null;                 last = null;                 return val;             } else {                     //2.2队中不只一个元素，删头节点                 head = head.next;                 head.prev = null;                 return val;             }         }     }     public boolean isEmpty() {             return head ==