Java数据结构与算法之循环队列的实现

概述

从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章.

循环队列

循环队列 (Circular Queue) 是一种特殊的队列. 循环队列解决了队列出队时需要将所有数据前移一位 (复杂度为 O(n)) 的问题.

循环队列的底层依然是数组, 不过增加了指向头和尾的指针.

循环队列实现

1. 判断队列是否为空: 当头指针 Q.front == 尾指针 Q.rear, 队列为空

2. 判断队列是否为满: 当头指针 Q.front == 尾指针 Q.rear + 1) ％ Maxsize, 队列为满

改变队列大小

// 改变队列大小
private void resize(int capacity) {
// 定义新数组
   E[] newData = (E[]) new Object[capacity + 1];

// 转移数组元素
   for (int i = 0; i < size; i++) {
       newData[i] = data[(i +front) ％ data.length];
   }

// 更新
   data = newData;
   front = 0;
   rear = size;
}

enqueue 方法

// 入队
public void enqueue(E e) {

// 判断是否为满
   if((rear + 1) ％ data.length == front) {
       resize(getCapacity() * 2);
   }

// 队伍加入
   data[rear] = e;
   rear = (rear + 1) ％ data.length;
   size++;
}

dequeue 方法

// 出队
public E dequeue() {

// 判断是否为空
   if(isEmpty()) {
       throw new RuntimeException("队列为空");
   }

// 取出第一个元素
   E element = data[front];
   data[front] = null;

// 移动头指针
   front = (front + 1) ％ data.length;

// 数组大小-1
   size--;

// 判断是否需要缩小
   if(size==getCapacity() / 4 && getCapacity() / 2 != 0) {
       resize(getCapacity() / 2);
   }

return element;
}

main

// 主函数
public static void main(String[] args) {

// 创建循环队列
   CircularQueue<Integer> queue = new CircularQueue<>(5);

// 入队
   for (int i = 0; i < 8; i++) {
       queue.enqueue(i);
       System.out.println(queue);
   }

// 出队
   for (int i = 0; i < 8; i++) {
       queue.dequeue();
       System.out.println(queue);
   }
}

输出结果:

CircularQueue{data=[0, null, null, null, null, null], front=0, rear=1, size=1}

CircularQueue{data=[0, 1, null, null, null, null], front=0, rear=2, size=2}

CircularQueue{data=[0, 1, 2, null, null, null], front=0, rear=3, size=3}

CircularQueue{data=[0, 1, 2, 3, null, null], front=0, rear=4, size=4}

CircularQueue{data=[0, 1, 2, 3, 4, null], front=0, rear=5, size=5}

CircularQueue{data=[0, 1, 2, 3, 4, 5, null, null, null, null, null], front=0, rear=6, size=6}

CircularQueue{data=[0, 1, 2, 3, 4, 5, 6, null, null, null, null], front=0, rear=7, size=7}

CircularQueue{data=[0, 1, 2, 3, 4, 5, 6, 7, null, null, null], front=0, rear=8, size=8}

CircularQueue{data=[null, 1, 2, 3, 4, 5, 6, 7, null, null, null], front=1, rear=8, size=7}

CircularQueue{data=[null, null, 2, 3, 4, 5, 6, 7, null, null, null], front=2, rear=8, size=6}

CircularQueue{data=[null, null, null, 3, 4, 5, 6, 7, null, null, null], front=3, rear=8, size=5}

CircularQueue{data=[null, null, null, null, 4, 5, 6, 7, null, null, null], front=4, rear=8, size=4}

CircularQueue{data=[null, null, null, null, null, 5, 6, 7, null, null, null], front=5, rear=8, size=3}

CircularQueue{data=[6, 7, null, null, null, null], front=0, rear=2, size=2}

CircularQueue{data=[7, null, null], front=0, rear=1, size=1}

CircularQueue{data=[null, null], front=0, rear=0, size=0}

完整代码 

import java.util.ArrayList;
import java.util.Arrays;

public class CircularQueue<E> {

private E[] data;
   private int front, rear;
   private int size;

// 无参构造
   public CircularQueue() {
       this(10);
   }

// 有参构造
   public CircularQueue(int capacity) {
      data = (E[]) new Object[capacity + 1];
      front = rear = size = 0;
   }

// 入队
   public void enqueue(E e) {

// 判断是否为满
       if((rear + 1) ％ data.length == front) {
           resize(getCapacity() * 2);
       }

// 队伍加入
       data[rear] = e;
       rear = (rear + 1) ％ data.length;
       size++;
   }

// 出队
   public E dequeue() {

// 判断是否为空
       if(isEmpty()) {
           throw new RuntimeException("队列为空");
       }

// 取出第一个元素
       E element = data[front];
       data[front] = null;

// 移动头指针
       front = (front + 1) ％ data.length;

// 数组大小-1
       size--;

// 判断是否需要缩小
       if(size==getCapacity() / 4 && getCapacity() / 2 != 0) {
           resize(getCapacity() / 2);
       }

return element;
   }

// 获取队列大小
   public int getSize() {
       return size;
   }

// 获取队列容量
   public int getCapacity() {
       return data.length - 1;
   }

// 队列是否为空
   public boolean isEmpty() {
       return front == rear;
   }

// 改变队列大小
   private void resize(int capacity) {

// 创建新数组
       E[] newData = (E[]) new Object[capacity + 1];

// 转移数组元素
       for (int i = 0; i < size; i++) {
           newData[i] = data[(i +front) ％ data.length];
       }

// 更新
       data = newData;
       front = 0;
       rear = size;
   }

@Override
   public String toString() {
       return "CircularQueue{" +
               "data=" + Arrays.toString(data) +
               ", front=" + front +
               ", rear=" + rear +
               ", size=" + size +
               '}';
   }

// 主函数
   public static void main(String[] args) {

// 创建循环队列
       CircularQueue<Integer> queue = new CircularQueue<>(5);

// 入队
       for (int i = 0; i < 8; i++) {
           queue.enqueue(i);
           System.out.println(queue);
       }

// 出队
       for (int i = 0; i < 8; i++) {
           queue.dequeue();
           System.out.println(queue);
       }
   }
}

来源：https://blog.csdn.net/weixin_46274168/article/details/121882681