Java 루프 큐 구현

12097 단어
  1 public class LoopQueue {
  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
", 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 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

좋은 웹페이지 즐겨찾기