目录
一、概述
二、链表实现队列
接口定义
接口实现类
测试类
三、环形数组实现队列
优点
下标计算
判满和判空
判满
判空
辅助变量size判空和判满
方法1
接口定义
接口实现类
测试类
方式2
接口定义
接口实现类
测试类
方法3
接口定义
接口实现类
测试类
生活鲜少给人留下退路
—— 24.9.27
一、概述
计算机科学中，queue 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品
二、链表实现队列
下面以单向环形带哨兵链表方式来实现队列
接口定义
offer：向队列尾部插入值
poll：从队列头部获取值，并移除
peek：从队列头获取值，不移除
isEmpty：检查队列是否为空
isFull：检查队列是否为满
public interface Queue<E> {/*向队列尾部插入值Params：value-待插入值Returns：插入成功返回true，插入失败返回false*/boolean offer(E e);/*从队列头获取值，并移除Returns：如果队列非空返回头部值，否则返回null*/E poll();/*从队列头获取值，不移除Returns：如果队列非空返回队头值，否则返回null*/E peek();/*检查队列是否为空Return：空返回true，否则返回false*/boolean isEmpty();/*检查队列是否为满Return：满返回true，否则返回false*/boolean isFull();
}
接口实现类
import java.util.Iterator;// 用泛型好处：1.用null代表特殊值 2.代表更多类型
public class LinkedListQueue<E>implements Queue<E>,Iterable<E> {// 静态内部结点类private static class Node<E>{E value;Node<E> next;public Node(E value, Node<E> next){this.value = value;this.next = next;}}// 定义队列的头结点和尾节点Node<E> head = new Node<>(null,null);Node<E> tail = head;private int size = 0; // 当前节点数private int capacity = 10; // 队列最大容量public LinkedListQueue(int capacity) {this.capacity = capacity;tail.next = head;}public LinkedListQueue() {tail.next = head;}/*队列插入方法，在尾部插入Params:value-待插入值Returns：插入成功返回true，插入失败返回false*/@Overridepublic boolean offer(E e) {if(isFull()){return false;}Node<E> newNode = new Node<>(e,head);tail.next = newNode;tail = newNode;size++;return true;}/*从队头获取值，并移除Returns：如果队列非空返回队头值，否则返回null*/@Overridepublic E poll() {if (isEmpty()){return null;}Node<E> first = head.next;head.next = first.next;if (first == tail){tail = head;}size--;return first.value;}/*从队列头获取值，不移除Returns：如果队列非空返回队头值，否则返回null*/@Overridepublic E peek() {if(isEmpty()){return null;}return head.next.value;}/*检查队列是否为空Return：空返回true，否则返回false*/@Overridepublic boolean isEmpty() {return head == tail;}/*检查队列是否为满Return：满返回true，否则返回false*/@Overridepublic boolean isFull() {return size == capacity;}// 队列遍历方法 迭代器@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> current = head.next;@Overridepublic boolean hasNext() {return current != head;}@Overridepublic E next() {E value = current.value;current = current.next;return value;}};}
}
测试类
import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;public class TestLinkedListQueue {// 向队列尾部插入值@Testpublic void offer() {LinkedListQueue<Integer> queue = new LinkedListQueue<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue,List.of(1,2,3,4,5));}// 从队列头获取值，不移除@Testpublic void peek(){LinkedListQueue<Integer> queue = new LinkedListQueue<>();assertNull(queue.peek());queue.offer(1);assertEquals(1,queue.peek());queue.offer(2);assertEquals(1,queue.peek());queue.offer(3);assertEquals(1,queue.peek());}// 从队头获取值，并移除@Testpublic void poll() {LinkedListQueue<Integer> queue = new LinkedListQueue<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertEquals(1,queue.poll());assertEquals(2,queue.poll());assertEquals(3,queue.poll());assertEquals(4,queue.poll());assertEquals(5,queue.poll());assertNull(queue.poll());}// 向有限队列头部加入元素@Testpublic void offerLimit(){LinkedListQueue<Integer> queue = new LinkedListQueue<>(3);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue,List.of(1,2,3));}}
三、环形数组实现队列
环形数组：
大小固定，首尾相连的数组
环形数组是一种逻辑上形成环形结构的数组，它在物理上通常是一个普通的线性数组，但在访问和操作时采用特定的逻辑来处理边界条件，使得元素可以从数组的末尾“循环”到开头，或者从开头“循环”到末尾。这种结构常用于实现循环队列、滑动窗口和约瑟夫环等问题，因为它避免了传统数组的越界问题，并且具有空间效率高、适合FIFO（先进先出）操作等优点。
环形数组的特点
① 逻辑环形：环形数组在逻辑上形成一个闭环，数组的最后一个元素与第一个元素相连。
② 无边界问题：由于索引是循环的，因此不存在传统数组的越界问题。
③ 空间效率高：环形数组可以充分利用数组空间，避免不必要的空间浪费。
④ 适合特定操作：如循环队列、滑动窗口等，这些操作在环形数组上实现起来更加高效。
环形数组的应用
① 循环队列：队列是一种先进先出（FIFO）的数据结构，而循环队列则是使用环形数组来实现的一种队列。在循环队列中，当队列的尾部达到数组的末尾时，下一个元素将插入到数组的开头，从而形成一个循环。
② 滑动窗口：滑动窗口是一种常用于数组/字符串处理的算法技巧，它可以在线性时间内解决一些看似需要嵌套循环的问题。环形数组可以用于实现滑动窗口的某些变体，特别是当窗口大小固定且需要循环移动时。
③ 约瑟夫环问题：约瑟夫环问题是一个著名的数学问题，描述的是n个人围成一圈，从第一个人开始报数，报到m的人出圈，然后从下一个人重新开始报数，如此循环直到所有人出圈。环形数组可以很好地模拟这个问题中的环形结构。
优点
1.对比普通数组，起点和终点更为自由，不用考虑数据移动
2.“环“意味着不会存在【越界】问题
3.数组性能更佳
4.环形数组比较适合实现有界队列、RingBuffer 等
下标计算
索引位置 = (cur + step) % length
cur：当前指针位置
step：前进步数
length：数组长度
判满和判空
判满
（尾指针+1）% 数组长度 = 头指针
判空
头指针 = 尾指针
辅助变量size判空和判满
方法1
使用头尾指针判断队列空和满的情况
接口定义
public interface Queue<E> {/*向队列尾部插入值Params：value-待插入值Returns：插入成功返回true，插入失败返回false*/boolean offer(E e);/*从队列头获取值，并移除Returns：如果队列非空返回头部值，否则返回null*/E poll();/*从队列头获取值，不移除Returns：如果队列非空返回队头值，否则返回null*/E peek();/*检查队列是否为空Return：空返回true，否则返回false*/boolean isEmpty();/*检查队列是否为满Return：满返回true，否则返回false*/boolean isFull();
}
接口实现类
import java.util.Iterator;public class ArrayQueue1<E> implements Queue<E>,Iterable<E> {private final E[] array;private int head = 0;private int tail = 0;public ArrayQueue1(int capacity) {array = (E[])new Object[capacity+1];}// 从队列尾部加入元素@Overridepublic boolean offer(E e) {if (isFull()){return false;}array[tail] = e;tail = (tail + 1) % array.length;return true;}// 从队列头部移除元素@Overridepublic E poll() {if (isEmpty()){return null;}E value = array[head];head = (head + 1) % array.length;return value;}// 获取队列头部元素值@Overridepublic E peek() {if (isEmpty()){return null;}return array[head];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {return (tail+1) % array.length == head;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int cursor = head;@Overridepublic boolean hasNext() {return cursor != tail;}@Overridepublic E next() {E value = array[cursor];cursor = (cursor + 1) % array.length;return value;}};}
}
测试类
import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;
import static org.junit.jupiter.api.Assertions.assertIterableEquals;public class TestArrayQueue1 {// 向队列尾部插入值@Testpublic void offer() {ArrayQueue1<Integer> queue = new ArrayQueue1<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue, List.of(1,2,3,4,5));}// 从队列头获取值，不移除@Testpublic void peek(){ArrayQueue1<Integer> queue = new ArrayQueue1<>(5);assertNull(queue.peek());queue.offer(1);assertEquals(1,queue.peek());queue.offer(2);assertEquals(1,queue.peek());queue.offer(3);assertEquals(1,queue.peek());}// 从队头获取值，并移除@Testpublic void poll() {ArrayQueue1<Integer> queue = new ArrayQueue1<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertEquals(1,queue.poll());assertEquals(2,queue.poll());assertEquals(3,queue.poll());assertEquals(4,queue.poll());assertEquals(5,queue.poll());assertNull(queue.poll());}// 向有限队列头部加入元素@Testpublic void offerLimit(){ArrayQueue1<Integer> queue = new ArrayQueue1<>(3);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue,List.of(1,2,3));}
}
方式2
引入一个辅助变量size，记录队列中的元素个数，直接通过用数组长度和size变量比较，判断队列空还是满。
接口定义
public interface Queue<E> {/*向队列尾部插入值Params：value-待插入值Returns：插入成功返回true，插入失败返回false*/boolean offer(E e);/*从队列头获取值，并移除Returns：如果队列非空返回头部值，否则返回null*/E poll();/*从队列头获取值，不移除Returns：如果队列非空返回队头值，否则返回null*/E peek();/*检查队列是否为空Return：空返回true，否则返回false*/boolean isEmpty();/*检查队列是否为满Return：满返回true，否则返回false*/boolean isFull();
}
接口实现类
import java.util.Iterator;public class ArrayQueue2<E> implements Queue<E>,Iterable<E> {private final E[] array;private int head = 0;private int tail = 0;private int size = 0;public ArrayQueue2(int capacity) {array = (E[]) new Object[capacity];}// 从队列尾部加入元素@Overridepublic boolean offer(E e) {if (isFull()){return false;}array[tail] = e;tail = (tail + 1) % array.length;size++;return true;}// 从队列头部移除元素@Overridepublic E poll() {if (isEmpty()){return null;}E value = array[head];head = (head + 1) % array.length;size--;return value;}// 获取队列头部元素值@Overridepublic E peek() {if (isEmpty()){return null;}return array[head];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int cursor = head;int count = 0;@Overridepublic boolean hasNext() {return count < size;}@Overridepublic E next() {E value = array[cursor];cursor = (cursor + 1) % array.length;count++;return value;}};}
}
测试类
import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;
import static org.junit.jupiter.api.Assertions.assertIterableEquals;public class TestArrayQueue2 {// 向队列尾部插入值@Testpublic void offer() {ArrayQueue2<Integer> queue = new ArrayQueue2<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue, List.of(1,2,3,4,5));}// 从队列头获取值，不移除@Testpublic void peek(){ArrayQueue2<Integer> queue = new ArrayQueue2<>(5);assertNull(queue.peek());queue.offer(1);assertEquals(1,queue.peek());queue.offer(2);assertEquals(1,queue.peek());queue.offer(3);assertEquals(1,queue.peek());}// 从队头获取值，并移除@Testpublic void poll() {ArrayQueue2<Integer> queue = new ArrayQueue2<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertEquals(1,queue.poll());assertEquals(2,queue.poll());assertEquals(3,queue.poll());assertEquals(4,queue.poll());assertEquals(5,queue.poll());assertNull(queue.poll());}// 向有限队列头部加入元素@Testpublic void offerLimit(){ArrayQueue2<Integer> queue = new ArrayQueue2<>(3);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue,List.of(1,2,3));}
}
方法3
head和tail直接存储指针值，tail存储最后一个元素的指针值，计算tail存储指针值指向的索引，tail并不直接指向索引不把计算结果存入head和tail中
接口定义
public interface Queue<E> {/*向队列尾部插入值Params：value-待插入值Returns：插入成功返回true，插入失败返回false*/boolean offer(E e);/*从队列头获取值，并移除Returns：如果队列非空返回头部值，否则返回null*/E poll();/*从队列头获取值，不移除Returns：如果队列非空返回队头值，否则返回null*/E peek();/*检查队列是否为空Return：空返回true，否则返回false*/boolean isEmpty();/*检查队列是否为满Return：满返回true，否则返回false*/boolean isFull();
}
接口实现类
import java.util.Iterator;public class ArrayQueue3<E> implements Queue<E>,Iterable<E> {private final E[] array;// head tail是两个不断递增的整数private int head = 0;private int tail = 0;@SuppressWarnings("all")public ArrayQueue3(int capacity) {// 初始化数组array = (E[]) new Object[capacity];}// 从队列尾部加入元素@Overridepublic boolean offer(E e) {// 判满if(isFull()){return false;}array[tail % array.length] = e;tail ++;return true;}// 从队列头部移除元素@Overridepublic E poll() {if (isEmpty()){return null;}// 找到索引位置E e = array[head % array.length];head ++;return e;}// 获取队列头部元素值@Overridepublic E peek() {if (isEmpty()){return null;}return array[head % array.length];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {return tail - head == array.length;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int cursor = head;@Overridepublic boolean hasNext() {return cursor != tail;}@Overridepublic E next() {E e = array[cursor % array.length];cursor++;return e;}};}
}
测试类
import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;
import static org.junit.jupiter.api.Assertions.assertIterableEquals;public class TestArrayQueue3 {// 向队列尾部插入值@Testpublic void offer() {ArrayQueue3<Integer> queue = new ArrayQueue3<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(List.of(1, 2, 3, 4, 5), queue);}// 从队列头获取值，不移除@Testpublic void peek(){ArrayQueue3<Integer> queue = new ArrayQueue3<>(5);assertNull(queue.peek());queue.offer(1);assertEquals(1,queue.peek());queue.offer(2);assertEquals(1,queue.peek());queue.offer(3);assertEquals(1,queue.peek());}// 从队头获取值，并移除@Testpublic void poll() {ArrayQueue3<Integer> queue = new ArrayQueue3<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertEquals(1,queue.poll());assertEquals(2,queue.poll());assertEquals(3,queue.poll());assertEquals(4,queue.poll());assertEquals(5,queue.poll());assertNull(queue.poll());}// 向有限队列头部加入元素@Testpublic void offerLimit(){ArrayQueue3<Integer> queue = new ArrayQueue3<>(3);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(List.of(1, 2, 3), queue);}
}
![柯桥韩语学校|韩语每日一词打卡：회갑연[회가변]【名词】花甲宴](https://i-blog.csdnimg.cn/direct/c2a35103dfc54110a2cd4ed0470a447e.jpeg)
![[Redis][集群][上]详细讲解](https://i-blog.csdnimg.cn/direct/596a5e439a544bab81d2161f7010cc69.png)