一, 队列简介
定义
队列 (queue) 在计算机科学中, 是一种先进先出的线性表. 它只允许在表的前端进行删除操作, 而在表的后端进行插入操作. 进行插入操作的端称为队尾, 进行删除操作的端称为队头. 队列中没有元素时, 称为空队列.
队列是一种线性结构;
相比数组, 队列对应操作的是数组的子集;
只能从一端 (队尾) 添加元素, 只能从另一端 (队首) 取出元素 . 先进先出的数据结构(先到先得 First In First Out[FIFO] ).
二, 代码实现
1. 队列接口
- public interface Queue{
- int getSize(); // 返回元素的个数
- E getFront(); // 返回队首元素内容
- boolean isEmpty(); // 判断是否为空
- void enqueue(E e); // 入队
- E dequeue(); // 出队
- }
2, 循环队列
循环队列中有两个新词, 两个指针
front 指向队列的第一个元素, 初始指向 0
tail 指向队列的最后一个元素的后一个位置, 初始指向 0
- public class LoopQueue<E> implements Queue<E> {
- private E[] data;
- // 指向队列的第一个元素, 初始指向 0
- private int front;
- // 指向队列的最后一个元素的后一个位置, 初始指向 0
- private int tail;
- // 元素数量
- private int size;
- public LoopQueue(int capacity){
- data = (E[]) new Object[capacity + 1];
- front = 0;
- tail = 0;
- size = 0;
- }
- public LoopQueue(){
- this(10);
- }
- @Override
- public int getSize() {
- return size;
- }
- /**
- * 因为容量放的时候多了个 1, 所以 get 容量的时候, 需要减 1
- * @return
- */
- public int getCapacity(){
- return data.length - 1;
- }
- /**
- * 当 front 和 tail 的值相等时, 队列为空, 初始两个指向的是同一个值(只有初始的时候, 指向的是同一个地方)
- * @return
- */
- @Override
- public boolean isEmpty() {
- return front == tail;
- }
- /**
- * 1.if((tail + 1) % data.length == front) 如果 tail + 1 超过了 data.length 的大小,
- * 代表当前 tail 指向已经超出了容量的大小, 因为是循环式, 所以需要 tail 去循环头元素中查看值是否有被占用,
- * 如果 == front 代表循环头没有, 就需要扩容了.
- * 2. 举例: 元素容量为 8,tail 目前指向 7 front 指向 2
- * if((7 + 1) % 8 == 2 ) if(0 == 2) 这里是 false, 因为 front 指向了 2, 所以代表 第 0,1 位是没有值的
- * 所以这个值需要在在第 0 位放(空间利用)
- * 3.data[tail] = param tail 当前指向的地方需要赋值, 然后 tail 自增 循环体 的 1,size+1
- * @param param
- */
- @Override
- public void enqueue( E param) {
- if ((tail + 1) % data.length == front) {
- resize(getCapacity() * 2);
- }
- data[tail] = param;
- tail = (tail + 1) % data.length;
- size++;
- }
- /**
- * 1. 如果队列为空抛出异常
- * 2. 用 ret 变量来接受当前队列头的值
- * 3. 接收成功之后将, 队列头元素置空
- * 4.front 指针指向下一个元素
- * 5.size 大小 - 1
- * 6. 如果 size 大小占据了容量的 1/4 和 size 为容量的 1/2 且不等于 0 的时候, 对容量进行缩减, 缩减为原来容量的 1/2
- * 7. 返回 ret 变量
- * @return
- */
- @Override
- public E dequeue() {
- if(isEmpty()){
- throw new IllegalArgumentException("Cannot dequeue from an empty queue");
- }
- E ret = data[front];
- data[front] = null;
- front = (front + 1) % data.length;
- size --;
- if (size == getCapacity() / 4 && getCapacity() / 2 != 0){
- resize(getCapacity()/2);
- }
- return ret;
- }
- @Override
- public E getFront() {
- if (isEmpty())
- throw new IllegalArgumentException("Queue is empty");
- return data[front];
- }
- /**
- * 扩充队列的容量
- * 1.front 代表了当前元素初始位置的指向
- * 2.newData 的第 i 位元素, 应该等于 i + front % data.length 的值
- * 3. 举例: 元素容量 20,i 等于 0 ,front 等于 2, 结果: newData[0] = data[(0 + 2) % 20]
- * = data[2] 意思就是, newData 的第一位元素, 应该等于 data 有值的第一位元素
- * % data.length 的原因主要是为了防止数组越界错误
- * 4. 新数组赋值完成需要将 front 重新指向 0, 因为新数组的 front 指针是从 0 开始的.
- * tail 最后要指向等于 size 大小的值,
- * @param newCapacity
- */
- private void resize(int newCapacity){
- E[] newData = (E[]) new Object[newCapacity + 1];
- for (int i=0; i <size; i++){
- newData[i] = data[(i + front) % data.length];
- }
- data = newData;
- front = 0;
- tail = size;
- }
- /**
- * 1. 元素从 front 位置开始循环遍历, i 的值不能等于 tail,
- * 也就是到 tail 的前一位, i = i + 1 且 %data.length,
- * 因为 i 有可能从循环头重新开始
- * 2.( i + 1 ) % data.length != tail 如果当前 i + 1 % data.length
- * 不等于 tail 表示不到最后一个元素, 就拼接,
- * @return
- */
- @Override
- public String toString(){
- StringBuilder stringBuilder = new StringBuilder();
- stringBuilder.append(String.format("LoopQueue:size = %d, capacity = %d\n",size, getCapacity()));
- stringBuilder.append("front [");
- for (int i=front; i != tail; i = (i + 1)%data.length){
- stringBuilder.append(data[i]);
- if ((i + 1)%data.length != tail){
- stringBuilder.append(",");
- }
- }
- stringBuilder.append("] tail");
- return stringBuilder.toString();
- }
- }
循环队列测试类
- public class LoopQueueTest {
- public static void main(String[] args) {
- LoopQueue<Integer> integerArrayQueue = new LoopQueue<>();
- for (int i = 0; i <10; i++) {
- integerArrayQueue.enqueue(i);
- System.out.println(integerArrayQueue);
- if(i % 3 == 2){
- integerArrayQueue.dequeue();
- System.out.println(integerArrayQueue);
- }
- }
- }
- }
- // 测试结果
- LoopQueue:size = 1, capacity = 5
- front [0] tail
- LoopQueue:size = 2, capacity = 5
- front [0,1] tail
- LoopQueue:size = 3, capacity = 5
- front [0,1,2] tail
- LoopQueue:size = 2, capacity = 5
- front [1,2] tail
- LoopQueue:size = 3, capacity = 5
- front [1,2,3] tail
- LoopQueue:size = 4, capacity = 5
- front [1,2,3,4] tail
- LoopQueue:size = 5, capacity = 5
- front [1,2,3,4,5] tail
- LoopQueue:size = 4, capacity = 5
- front [2,3,4,5] tail
- LoopQueue:size = 5, capacity = 5
- front [2,3,4,5,6] tail
- LoopQueue:size = 6, capacity = 10
- front [2,3,4,5,6,7] tail
- LoopQueue:size = 7, capacity = 10
- front [2,3,4,5,6,7,8] tail
- LoopQueue:size = 6, capacity = 10
- front [3,4,5,6,7,8] tail
- LoopQueue:size = 7, capacity = 10
- front [3,4,5,6,7,8,9] tail
3. 数组实现队列
- public class ArrayQueue<E> implements Queue<E>{
- Array<E> array; // 详情内容: https://www.cnblogs.com/FondWang/p/11806545.html
- // 初始化大小
- public ArrayQueue(int capacity){
- array=new Array<E>(capacity);
- }
- // 无参构造器
- public ArrayQueue(){
- array=new Array<E>();
- }
- // 入队. 只能从队尾添加数据
- @Override
- public void enqueue(E param) {
- array.addLast(param);
- }
- // 出队. 只能从队首添加内容
- @Override
- public E dequeue() {
- return array.removeFirst();
- }
- // 返回队首的元素
- @Override
- public E getFront() {
- return array.getFirst();
- }
- @Override
- public int getSize() {
- return array.getSize();
- }
- @Override
- public boolean isEmpty() {
- return array.isEmpty();
- }
- @Override
- public String toString(){
- StringBuffer sb = new StringBuffer();
- sb.append("front:");
- sb.append("[");
- for(int i=0;i<array.getSize();i++){
- sb.append(array.get(i));
- if(i!=array.getSize()-1){
- sb.append(",");
- }
- }
- sb.append("] tail");
- return sb.toString();
- }
- }
数组队列测试类
- public class ArrayQueueTest {
- public static void main(String[] args) {
- ArrayQueue<Integer> integerArrayQueue = new ArrayQueue<>();
- for (int i = 0; i <10; i++) {
- integerArrayQueue.enqueue(i);
- System.out.println(integerArrayQueue);
- if(i % 3 == 2){
- integerArrayQueue.dequeue();
- System.out.println(integerArrayQueue);
- }
- }
- }
- }
- // 测试结果
- ArrayQueue:front [0] tail
- ArrayQueue:front [0, 1] tail
- ArrayQueue:front [0, 1, 2] tail
- ArrayQueue:front [1, 2] tail
- ArrayQueue:front [1, 2, 3] tail
- ArrayQueue:front [1, 2, 3, 4] tail
- ArrayQueue:front [1, 2, 3, 4, 5] tail
- ArrayQueue:front [2, 3, 4, 5] tail
- ArrayQueue:front [2, 3, 4, 5, 6] tail
- ArrayQueue:front [2, 3, 4, 5, 6, 7] tail
- ArrayQueue:front [2, 3, 4, 5, 6, 7, 8] tail
- ArrayQueue:front [3, 4, 5, 6, 7, 8] tail
- ArrayQueue:front [3, 4, 5, 6, 7, 8, 9] tail
4. 循环队列和数组队列 效率对比
测试代码
- import java.util.Random;
- public class Main {
- private static double testQueue(Queue<Integer> q, int opCount){
- long startTime = System.nanoTime();
- Random random = new Random();
- for (int i=0;i<opCount; i++){
- q.enqueue(random.nextInt(Integer.MAX_VALUE));
- }
- for (int i=0; i<opCount;i++){
- q.dequeue();
- }
- long endTime = System.nanoTime();
- return (endTime - startTime) / 1000000000.0;
- }
- public static void main(String[] args) {
- int opCount = 100000;// 十万数据增删效率
- ArrayQueue arrayQueue = new ArrayQueue();
- double time1 = testQueue(arrayQueue,opCount);
- System.out.println("ArrayQueue, time:" + time1 + "s");
- LoopQueue loopQueue = new LoopQueue();
- double time2 = testQueue(loopQueue,opCount);
- System.out.println("LoopQueue, time:" + time2 + "s");
- System.out.println("loopQueue 队列数 ArrayQueue 的" + Math.round(time1/time2) + "倍");
- }
- }
测试结果
- ArrayQueue, time:3.78317767s
- LoopQueue, time:0.011734084s
loopQueue 队列 是 ArrayQueue 的 322 倍
// 测试三次: 322,327,322, 平均(322+327+323)/ 3 约为 323 倍
来源: http://www.bubuko.com/infodetail-3275465.html