队列(Queue)

队列是一种先进先出的线性数据结构。

队列的主要操作的是入队和出队，需要从一端进入，从另外一端出去。

• Queue接口定义

  public interface Queue<E> {
      int getSize();
      boolean isEmpty();
      void enqueue(E e);  //入队
      E dequeue();        //出队
      E getFront();       //获取队首元素
  }
  

• 队列可以使用数组实现，也可以使用链表实现

  //使用数组实现
  public ArrayQueue<E> implements Queue<E> {
      
      private Array<E> array;
      public ArrayQueue(int capacity) {
          array = new Array<>(capacity);
      }
      public ArrayQueue() {
          array = new Array<>();
      }
      
      public int getSize() {
          return array.getSize();
      }
      
      public boolean isEmpty() {
          return array.isEmpty();
      }
      
      public void enqueue(E e) {
          array.addLast(e);
      }
      
      public E dequeue() {
          return array.removeFirst();
      }
      
      public E getFront() {
          return array.getFirst();
      }
      
  }
  

  //使用链表实现
  public class LinkedListQueue<E> implements Queue<E> {
  
      //定义链表的节点
      private class Node {
          private E e;
          private Node next;
  
          public Node(E e, Node next) {
              this.e = e;
              this.next = next;
          }
          public Node(E e) {
              this(e, null);
          }
          @Override
          public String toString() {
              return e.toString();
          }
      }
  
      private Node head, tail;
      private int size = 0;
  
      public LinkedListQueue() {
          head = null;
          tail = null;
          size = 0;
      }
  
      @Override
      public int getSize() {
          return size;
      }
  
      @Override
      public boolean isEmpty() {
          return size == 0;
      }
  
      @Override
      public void enqueue(E e) {
          //由于没有设置dummyHead,当链表为空就需要单独处理
          if(tail == null) {
              tail = new Node(e);
              head = tail;
          } else {
              tail.next = new Node(e);
              tail = tail.next;
          }
          size ++;
      }
  
      @Override
      public E dequeue() {
          if(isEmpty()){
              throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
          }
          Node retNode = head;
          //head指针后移
          head = head.next;
          retNode.next = null;
          if(head == null) {
              tail = null;
          }
          size --;
          return retNode.e;
      }
  
      @Override
      public E getFront() {
          if(isEmpty()){
              throw new IllegalArgumentException("Empty Queue.");
          }
          return head.e;
      }
  
      @Override
  public String toString() {
      StringBuilder res = new StringBuilder();
      res.append("Queue: (front)");
  
      Node curr = head;
      while(curr != null) {
          if(curr.next != null) {
              res.append(curr + "->");
          }else{
              res.append(curr + "(tail) -> ");
          }
          curr = curr.next;
      }
      res.append("null");
      return res.toString();
  }
  }
  

• 循环队列

  正是因为循环队列在元素出队操作的优化（数组队列的出队操作，需要将剩余元素全部前移），才使得循环队列的复杂度大大降低。

  public class LoopQueue<E> implements Queue<E> {
  
      private E[] data;
      private int front, tail;
      private int size;
  
      public LoopQueue(int capacity) {
          //容量+1，是因为我们要故意浪费一个空间
          data = (E[]) new Object[capacity + 1];
          front = 0;
          tail = 0;
          size = 0;
      }
  
      public LoopQueue() {
          this(10);
      }
  
      @Override
      public int getSize() {
          return size;
      }
  
      public int getCapacity() {
          return data.length-1;
      }
  
      @Override
      public boolean isEmpty() {
          return front == size;
      }
  
      @Override
      public void enqueue(E e) {
          //判断是否堆满
          if( (tail+1)%data.length == front) {
              resize(getCapacity() * 2);
          }
  
          //元素入队
          data[tail] = e;
          //tail循环后移
          tail = (tail+1)%data.length;
          size ++;
      }
  
      private void resize(int newCapacity) {
          E[] newData = (E[]) new Object[newCapacity + 1];
          for (int i = 0; i < size; i++) {
              newData[i] = data[(i+front)%data.length];
          }
          data = newData;
          front = 0;
          tail = size;
      }
  
      @Override
      public E dequeue() {
          //队列是否为空
          if(isEmpty()) {
              throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
          }
  
          E ret = data[front];
          data[front] = null;
          front = (front+1)%data.length;
          size --;
  
          //动态缩容
          if(size == getCapacity() / 4 && getCapacity() /2 != 0) {
              resize(getCapacity() / 2);
          }
  
          return ret;
      }
  
      @Override
      public E getFront() {
          //队列是否为空
          if(isEmpty()) {
              throw new IllegalArgumentException("Queue is empty.");
          }
          return data[front];
      }
  
      @Override
      public String toString() {
          StringBuilder res = new StringBuilder();
          res.append(String.format("LoopQueue:size = %d, capacity = %d\n", size, getCapacity()));
          res.append("front-> [");
          for (int i = front; i != tail ; i = (i+1)%data.length) {
              res.append(data[i]);
              if((i+1)%data.length != tail) {
                  res.append(", ");
              }
          }
          res.append("] <-tail\n");
          return res.toString();
      }
  }