Java数据结构与算法分析|队列

GitHub源码分享

项目主页&＃xff1a;https://github.com/gozhuyinglong/blog-demos
本文源码&＃xff1a;https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures

1. 队列&＃xff08;queue&＃xff09;

队列和栈一样&＃xff0c;也是一个操作受限制的线性表。不同的是队列的插入在一端进行&＃xff0c;我们称为队尾&＃xff08;rear&＃xff09;&＃xff1b;而删除&＃xff08;取出&＃xff09;在另一端进行&＃xff0c;我们称为队头&＃xff08;front&＃xff09;。

队列是一个先进先出&＃xff08;FIFO - First In First Out&＃xff09;的有序列表&＃xff0c;其操作只有两种&＃xff1a;

• 入队&＃xff08;enqueue&＃xff09;&＃xff1a;向队尾添加一个元素
• 出队&＃xff08;dequeue&＃xff09;&＃xff1a;从队头删除&＃xff08;取出&＃xff09;一个元素

2. 队列的数组实现

如同栈一样&＃xff0c;对队列的每一种操作&＃xff0c;链表实现或数组实现都给出快速的运行时间。队列的链表实现是简单而直接的&＃xff0c;我们就不过介绍了。下面我们讨论如何使用数组实现一个队列。

先看下图&＃xff0c;我们需要声明一个数组&＃xff0c;并维护两个指针&＃xff1a;

• head指针&＃xff1a;指向待出列的元素位置
• tail指针&＃xff1a;指向待入列的存储位置
  可以看出&＃xff0c;到达队尾后无法再添加新的元素&＃xff0c;然后前面已出列的位置还空着。

上面问题我们可以将数组进行首尾想死&＃xff0c;形成一个环形数组&＃xff0c;即指针到达数组尾部后&＃xff0c;重新指向数组头部&＃xff0c;如下图所示。

这里需要注意几点&＃xff1a;

• 判断空队列可以通过head &＃61;&＃61; tail
• 判断队列满不能再通过head与tail重合&＃xff0c;而是需要空出一个存储空间来&＃xff0c;即&＃xff1a;head &＃61;&＃61; tail &＃43; 1。而环形数组需要取模运算&＃xff0c;所以正确判断队列满&＃xff1a;head &＃61;&＃61; (tail &＃43; 1) % capacity。
• 数组真实容量应为&＃xff1a;指定容量 &＃43; 1

3. 代码实现

下面代码是使用环形数组实现的队列&＃xff0c;所以又叫做环形队列。
其容量为&＃xff1a;指定容量 &＃43; 1&＃xff0c;head 与t ail 初始值为0。队列存储元素使用了泛型&＃xff0c;所以可以操作你想用的数据类型。下面看具体实现&＃xff1a;

public class ArrayQueueDemo {public static void main(String[] args) {ArrayQueue<Integer> queue &＃61; new ArrayQueue<>(5);System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.println("入队&＃xff1a;1 --> " &＃43; queue.add(1));System.out.println("入队&＃xff1a;2 --> " &＃43; queue.add(2));System.out.println("入队&＃xff1a;3 --> " &＃43; queue.add(3));System.out.println("入队&＃xff1a;4 --> " &＃43; queue.add(4));System.out.println("入队&＃xff1a;5 --> " &＃43; queue.add(5));System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.println("入队&＃xff1a;6 --> " &＃43; queue.add(6));System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);System.out.println("入队&＃xff1a;7 --> " &＃43; queue.add(7));System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);System.out.println("入队&＃xff1a;8 --> " &＃43; queue.add(8));System.out.println("入队&＃xff1a;9 --> " &＃43; queue.add(9));System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.println("出队&＃xff1a; --> " &＃43; queue.get());System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);System.out.println("入队&＃xff1a;10 --> " &＃43; queue.add(10));System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);}private static class ArrayQueue<T> {private final T[] queue; // 存储队列数据元素private final int capacity; // 容量private int head &＃61; 0; // 头部指针&＃xff0c;指向队头元素private int tail &＃61; 0; // 尾部指针&＃xff0c;指向下一个待入队元素的存储位置public ArrayQueue(int capacity) {this.capacity &＃61; capacity &＃43; 1; // 环形队列需要空出一个位置&＃xff0c;来满足队列满时head与tail不重合this.queue &＃61; (T[]) new Object[this.capacity];}/*** 向队列添加一个元素** &＃64;param data* &＃64;return*/public boolean add(T data) {// 队列满&＃xff0c;添加失败if (isFull()) {return false;}// tail指向下一个待入队元素的存储位置&＃xff0c;所以先赋值再让指针加1queue[tail] &＃61; data;// 环形数组需要取模运算tail &＃61; (tail &＃43; 1) % capacity;return true;}/*** 从队列中获取一个元素** &＃64;return*/public T get() {if (isEmpty()) {return null;}// head指向头元素位置&＃xff0c;所以先取出再让指针加1T data &＃61; queue[head];// 环形数组需要取模运算head &＃61; (head &＃43; 1) % capacity;return data;}/*** 当前队列大小** &＃64;return*/public int size() {int size &＃61; tail - head;if (size < 0) {size &＃43;&＃61; capacity;}return size;}/*** 队列是否为空&＃xff1a;当tail与head指向同一位置时&＃xff0c;表示队列为空** &＃64;return*/public boolean isEmpty() {return tail &＃61;&＃61; head;}/*** 队列是否已满&＃xff1a;因为预留了一个位置&＃xff0c;所以tail需要加1&＃xff1b;环形队列需要取模运算** &＃64;return*/public boolean isFull() {return head &＃61;&＃61; (tail &＃43; 1) % capacity;}}
}


输出结果&＃xff1a;

头指针: 0 尾指针: 0 队列大小: 0 容量: 6
出队&＃xff1a; --> null
入队&＃xff1a;1 --> true
入队&＃xff1a;2 --> true
入队&＃xff1a;3 --> true
入队&＃xff1a;4 --> true
入队&＃xff1a;5 --> true
头指针: 0 尾指针: 5 队列大小: 5 容量: 6
出队&＃xff1a; --> 1
入队&＃xff1a;6 --> true
头指针: 1 尾指针: 0 队列大小: 5 容量: 6
入队&＃xff1a;7 --> false
出队&＃xff1a; --> 2
出队&＃xff1a; --> 3
头指针: 3 尾指针: 0 队列大小: 3 容量: 6
入队&＃xff1a;8 --> true
入队&＃xff1a;9 --> true
头指针: 3 尾指针: 2 队列大小: 5 容量: 6
出队&＃xff1a; --> 4
出队&＃xff1a; --> 5
出队&＃xff1a; --> 6
出队&＃xff1a; --> 8
出队&＃xff1a; --> 9
头指针: 2 尾指针: 2 队列大小: 0 容量: 6
入队&＃xff1a;10 --> true
头指针: 2 尾指针: 3 队列大小: 1 容量: 6