队列是一种FIFO（先进先出）的数据结构，其插入新元素被称为入队，删除被称为出队，每次删除的都是最先入队的元素，即第一个元素。
队列 - 图1

实现

采用 List 数组来存储数据，指针 p_start 来指示队列的第一个元素位置。随着 p_start 的移动，越来越多的空间被浪费。

  • isEmpty ：指针位置大于等于数组的大小
  • front ：队列的第一个元素
  • enQueue ：添加数据
  • deQueue ：如果队列为空，则返回false，否则将 p_start +1，返回True ```java import java.util.ArrayList; import java.util.List;

public class MyQueue { private List data; private int p_start;

  1. /**
  2.  * @return whether queue is empty
  3.  */
  4. public boolean isEmpty() {
  5.     return p_start >= data.size();
  6. }
  8. /**
  9.  * @return the front item from the queue
  10.  */
  11. public int front() {
  12.     return data.get(p_start);
  13. }
  15. /**
  16.  * insert an element into the queue
  17.  *
  18.  * @param x
  19.  * @return whether insert successfully
  20.  */
  21. public boolean enQueue(int x) {
  22.     data.add(x);
  23.     return true;
  24. }
  26. /**
  27.  * delete the first item from the queue
  28.  *
  29.  * @return true if the operation is successful
  30.  */
  31. public boolean deQueue() {
  32.     if (!isEmpty()) {
  33.         p_start++;
  34.         return true;
  35.     } else
  36.         return false;
  37. }
  39. public MyQueue() {
  40.     data = new ArrayList<>();
  41.     p_start = 0;
  42. }

}

  1. <a name="wFWiR"></a>
  2. # 循环队列
  3. 对于上述的队列来说，空间被大大浪费了，**循环队列**采用固定的长度数组和两个指针来指示起始位置。
  4. ```java
  5. public class MyCircularQueue {
  6.     private int[] data;
  7.     private int head;
  8.     private int tail;
  9.     private int size;
  11.     /**
  12.      * Initialize your data structure here. Set the size of the queue to be k.
  13.      */
  14.     public MyCircularQueue(int k) {
  15.         data = new int[k];
  16.         head = tail = -1;
  17.         size = k;
  18.     }
  20.     /**
  21.      * Insert an element into the circular queue. Return true if the operation is successful.
  22.      */
  23.     public boolean enQueue(int value) {
  24.         if (isFull())
  25.             return false;
  26.         if (isEmpty())
  27.             head = 0;
  28.         tail = (tail + 1) % size;
  29.         data[tail] = value;
  30.         return true;
  31.     }
  33.     /**
  34.      * Delete an element from the circular queue. Return true if the operation is successful.
  35.      */
  36.     public boolean deQueue() {
  37.         if (isEmpty())
  38.             return false;
  39.         if (head == tail) {
  40.             head = tail = -1;
  41.             return true;
  42.         }
  43.         head = (head + 1) % size;
  44.         return true;
  45.     }
  47.     /**
  48.      * Get the front item from the queue.
  49.      */
  50.     public int Front() {
  51.         if (isEmpty())
  52.             return -1;
  53.         return data[head];
  54.     }
  56.     /**
  57.      * Get the last item from the queue.
  58.      */
  59.     public int Rear() {
  60.         if (isEmpty())
  61.             return -1;
  62.         return data[tail];
  63.     }
  65.     /**
  66.      * Checks whether the circular queue is empty or not.
  67.      */
  68.     public boolean isEmpty() {
  69.         return head == -1;
  70.     }
  72.     /**
  73.      * Checks whether the circular queue is full or not.
  74.      */
  75.     public boolean isFull() {
  76.         return ((tail + 1) % size) == head;
  77.     }
  78. }

参考

  1. leetcode 数据结构——队列