概括

  • 始终在一端插入数据，另一端删除数据
  • 先进先出（FIFO，First Input First Output）
  • 插入和删除时间复杂度O(1)

image.png

循环队列

通过 双指针 + 数组 实现循环队列

  1. public class QueueDemo {
  3.     public static void main(String[] args) {
  4.         MyQueue myQueue = new MyQueue();
  5.         myQueue.enQueue(3);
  6.         myQueue.enQueue(5);
  7.         myQueue.enQueue(6);
  8.         myQueue.enQueue(8);
  9.         myQueue.enQueue(1);
  10.         myQueue.deQueue();
  11.         myQueue.deQueue();
  12.         myQueue.deQueue();
  13.         myQueue.enQueue(2);
  14.         myQueue.enQueue(4);
  15.         myQueue.enQueue(9);
  16.         myQueue.print();
  17.     }
  19.     public static class MyQueue {
  21.         private final int[] arr = new int[10];
  22.         private int front;
  23.         private int rear;
  25.         public void enQueue(int element) {
  26.             if ((rear + 1) % arr.length == front) {
  27.                 throw new RuntimeException("队列已满！");
  28.             }
  29.             arr[rear] = element;
  30.             rear = (rear + 1) % arr.length;
  31.         }
  33.         public int deQueue() {
  34.             if (rear == front) {
  35.                 throw new RuntimeException("队列已空！");
  36.             }
  37.             int remove = arr[front];
  38.             front = (front + 1) % arr.length;
  39.             return remove;
  40.         }
  42.         public void print() {
  43.             for (int i = front; i != rear; i = (i + 1) % arr.length) {
  44.                 System.out.println(arr[i]);
  45.             }
  46.         }
  47.     }
  48. }