Java实现循环队列

╰+哭是因爲堅強的太久メ 2023-08-17 16:37 118阅读 0赞

1 public class LoopQueue<E> {
      2 
      3     private E[] data;
      4     private int front; // 头
      5     private int tail; // 尾
      6     private int size;
      7 
      8     public LoopQueue(int capacity) {
      9         data = (E[]) new Object[capacity + 1];
     10         front = 0;
     11         tail = 0;
     12         size = 0;
     13     }
     14 
     15     public LoopQueue() {
     16         this(10);
     17     }
     18 
     19     public int getCapacity() {
     20         return data.length - 1;
     21     }
     22 
     23     public int getSize() {
     24         return size;
     25     }
     26 
     27     public boolean isEmpty() {
     28         return front == tail;
     29     }
     30 
     31     public boolean isFull() {
     32         return (tail + 1) % data.length == front;
     33     }
     34 　　 // 入队
     35     public void enqueue(E e) {
     36         if (isFull()) {
     37             resize(getCapacity() * 2);
     38         }
     39         data[tail] = e;
     40         tail = (tail + 1) % data.length;
     41         size++;
     42     }
     43 
     44     private void resize(int newCapacity) {
     45         E[] newArr = (E[]) new Object[newCapacity + 1];
     46         for (int i = 0; i < size; i++) {
     47             newArr[i] = data[(front + i) % data.length];
     48         }
     49         data = newArr;
     50         front = 0;
     51         tail = size;
     52     }
     53 　　 // 出队
     54     public E dequeue() {
     55         if (isEmpty()) {
     56             throw new IllegalArgumentException("Cannot dequeue from an empty queue");
     57         }
     58         E res = data[front];
     59         data[front] = null;
     60         front = (front + 1) % data.length;
     61         size--;
     62         if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
     63             resize(getCapacity() / 2);
     64         }
     65         return res;
     66     }
     67 　　 
     68     public E getFront() {
     69         if (isEmpty()) {
     70             throw new IllegalArgumentException("Cannot dequeue from an empty queue");
     71         }
     72         return data[front];
     73     }
     74 
     75     @Override
     76     public String toString() {
     77         StringBuilder str = new StringBuilder();
     78         str.append(String.format("Queue: size = %d, capacity = %d\n", size, getCapacity()));
     79         str.append("front [");
     80         for (int i = front; i != tail; i = (i + 1) % data.length) {
     81             str.append(data[i]);
     82             if ((i + 1) % data.length != tail) {
     83                 str.append(", ");
     84             }
     85         }
     86         str.append("] tail");
     87         return str.toString();
     88     }
     89 
     90     public static void main(String[] args) {
     91         LoopQueue<Integer> queue = new LoopQueue<>();
     92         for (int i = 0; i < 10; i++) {
     93             queue.enqueue(i);
     94             System.out.println(queue);
     95             if (i % 3 == 2) {
     96                 queue.dequeue();
     97                 System.out.println(queue);
     98             }
     99         }
    100     }
    101 }

转载于:https://www.cnblogs.com/rabbitli/p/11255603.html