数据结构-队列(Queue)-FIFO

image-20210608115446932

队列的接口设计

image-20210608115603601 image-20210608115805914

public class Queue<E> {
   private List<E> list = new LinkedList<>();
   
   public int size() {
      return list.size();
   }

   public boolean isEmpty() {
      return list.isEmpty();
   }
   
   public void clear() {
      list.clear();
   }

   public void enQueue(E element) {
      list.add(element);
   }

   public E deQueue() {
      return list.remove(0);
   }

   public E front() {
      return list.get(0);
   }
}

双端队列-Deque

image-20210608120755269

public class Deque<E> {
    private List<E> list = new LinkedList<>();
    
    public int size() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    public void clear() {
        list.clear();
    }

    public void enQueueRear(E element) {
        list.add(element);
    }

    public E deQueueFront() {
        return list.remove(0);
    }

    public void enQueueFront(E element) {
        list.add(0, element);
    }

    public E deQueueRear() {
        return list.remove(list.size() - 1);
    }

    public E front() {
        return list.get(0);
    }

    public E rear() {
        return list.get(list.size() - 1);
    }
}

循环队列-CircleQueue

image-20210608122628816

public class CircleQueue<E> {
   private int front;
   private int size;
   private E[] elements;
   private static final int DEFAULT_CAPACITY = 10;
   
   public CircleQueue() {
      elements = (E[]) new Object[DEFAULT_CAPACITY];
   }
   
   public int size() {
      return size;
   }

   public boolean isEmpty() {
      return size == 0;
   }
   
   public void clear() {
      for (int i = 0; i < size; i++) {
         elements[index(i)] = null;
      }
      front = 0;
      size = 0;
   }

   public void enQueue(E element) {
      ensureCapacity(size + 1);
      
      elements[index(size)] = element;
      size++;
   }

   public E deQueue() {
      E frontElement = elements[front];
      elements[front] = null;
      front = index(1);
      size--;
      return frontElement;
   }

   public E front() {
      return elements[front];
   }
   
   @Override
   public String toString() {
      StringBuilder string = new StringBuilder();
      string.append("capcacity=").append(elements.length)
      .append(" size=").append(size)
      .append(" front=").append(front)
      .append(", [");
      for (int i = 0; i < elements.length; i++) {
         if (i != 0) {
            string.append(", ");
         }
         
         string.append(elements[i]);
      }
      string.append("]");
      return string.toString();
   }
   
   private int index(int index) {
      index += front;
      return index - (index >= elements.length ? elements.length : 0);
   }
   
   /**
    * 保证要有capacity的容量
    * @param capacity
    */
   private void ensureCapacity(int capacity) {
      int oldCapacity = elements.length;
      if (oldCapacity >= capacity) return;
      
      // 新容量为旧容量的1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      E[] newElements = (E[]) new Object[newCapacity];
      for (int i = 0; i < size; i++) {
         newElements[i] = elements[index(i)];
      }
      elements = newElements;
      
      // 重置front
      front = 0;
   }
}

双端循环队列-CircleDeque

public class CircleDeque<E> {
   private int front;
   private int size;
   private E[] elements;
   private static final int DEFAULT_CAPACITY = 10;
   
   public CircleDeque() {
      elements = (E[]) new Object[DEFAULT_CAPACITY];
   }
   
   public int size() {
      return size;
   }

   public boolean isEmpty() {
      return size == 0;
   }

   public void clear() {
      for (int i = 0; i < size; i++) {
         elements[index(i)] = null;
      }
      front = 0;
      size = 0;
   }

   /**
    * 从尾部入队
    * @param element
    */
   public void enQueueRear(E element) {
      ensureCapacity(size + 1);
      
      elements[index(size)] = element;
      size++;
   }

   /**
    * 从头部出队
    * @param element
    */
   public E deQueueFront() {
      E frontElement = elements[front];
      elements[front] = null;
      front = index(1);
      size--;
      return frontElement;
   }

   /**
    * 从头部入队
    * @param element
    */
   public void enQueueFront(E element) {
      ensureCapacity(size + 1);
      
      front = index(-1);
      elements[front] = element;
      size++;
   }

   /**
    * 从尾部出队
    * @param element
    */
   public E deQueueRear() {
      int rearIndex = index(size - 1);
      E rear = elements[rearIndex];
      elements[rearIndex] = null;
      size--;
      return rear;
   }

   public E front() {
      return elements[front];
   }

   public E rear() {
      return elements[index(size - 1)];
   }

   @Override
   public String toString() {
      StringBuilder string = new StringBuilder();
      string.append("capcacity=").append(elements.length)
      .append(" size=").append(size)
      .append(" front=").append(front)
      .append(", [");
      for (int i = 0; i < elements.length; i++) {
         if (i != 0) {
            string.append(", ");
         }
         
         string.append(elements[i]);
      }
      string.append("]");
      return string.toString();
   }
   
   private int index(int index) {
      index += front;
      if (index < 0) {
         return index + elements.length;
      }
      return index - (index >= elements.length ? elements.length : 0);
   }
   
   /**
    * 保证要有capacity的容量
    * @param capacity
    */
   private void ensureCapacity(int capacity) {
      int oldCapacity = elements.length;
      if (oldCapacity >= capacity) return;
      
      // 新容量为旧容量的1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      E[] newElements = (E[]) new Object[newCapacity];
      for (int i = 0; i < size; i++) {
         newElements[i] = elements[index(i)];
      }
      elements = newElements;
      
      // 重置front
      front = 0;
   }
}