隊(duì)列是一種先進(jìn)先出的線性數(shù)據(jù)結(jié)構(gòu)奶卓。

隊(duì)列的主要操作的是入隊(duì)和出隊(duì)晴音，需要從一端進(jìn)入肘交，從另外一端出去。

• Queue接口定義

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

• 隊(duì)列可以使用數(shù)組實(shí)現(xiàn)唆缴，也可以使用鏈表實(shí)現(xiàn)

  //使用數(shù)組實(shí)現(xiàn)
  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();
      }
      
  }
  

  //使用鏈表實(shí)現(xiàn)
  public class LinkedListQueue<E> implements Queue<E> {
  
      //定義鏈表的節(jié)點(diǎn)
      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) {
          //由于沒有設(shè)置dummyHead,當(dāng)鏈表為空就需要單獨(dú)處理
          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();
  }
  }
  

• 循環(huán)隊(duì)列

  正是因?yàn)檠h(huán)隊(duì)列在元素出隊(duì)操作的優(yōu)化（數(shù)組隊(duì)列的出隊(duì)操作鳍征，需要將剩余元素全部前移），才使得循環(huán)隊(duì)列的復(fù)雜度大大降低面徽。

  public class LoopQueue<E> implements Queue<E> {
  
      private E[] data;
      private int front, tail;
      private int size;
  
      public LoopQueue(int capacity) {
          //容量+1艳丛，是因?yàn)槲覀円室饫速M(fèi)一個(gè)空間
          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);
          }
  
          //元素入隊(duì)
          data[tail] = e;
          //tail循環(huán)后移
          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() {
          //隊(duì)列是否為空
          if(isEmpty()) {
              throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
          }
  
          E ret = data[front];
          data[front] = null;
          front = (front+1)%data.length;
          size --;
  
          //動(dòng)態(tài)縮容
          if(size == getCapacity() / 4 && getCapacity() /2 != 0) {
              resize(getCapacity() / 2);
          }
  
          return ret;
      }
  
      @Override
      public E getFront() {
          //隊(duì)列是否為空
          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();
      }
  }