概念

队列也是一种线性结构,相比数组,队列对应的操作是数组的子集,只能从一端(队尾)添加元素,只能从另一端(队首)取出元素.
image.png

特点

队列是一种先进先出的数据结构.

数组队列

实现

  1. public interface Queue<E> {
  3.     /**
  4.      * 入队操作
  5.      *
  6.      * 时间复杂度 O(1) 均摊 ArrayQueue 和 LoopQueue同
  7.      * @param e 元素
  8.      */
  9.     void enqueue(E e);
  11.     /**
  12.      * 出队操作
  13.      *
  14.      * 时间复杂度 O(n)  ArrayQueue复杂度为O(n)  LoopQueue复杂度O(1) 均摊
  15.      * 出队拿出数组中第一个元素后,剩下的元素都要前移
  16.      * @return 元素
  17.      */
  18.     E dequeue();
  20.     /**
  21.      * 查看队列队首的元素
  22.      *
  23.      * 时间复杂度 O(1)  ArrayQueue 和 LoopQueue同
  24.      * @return 元素
  25.      */
  26.     E getFront();
  28.     /**
  29.      * 获取队列的数量
  30.      *
  31.      * 时间复杂度 O(1) ArrayQueue 和 LoopQueue同
  32.      * @return size
  33.      */
  34.     int getSize();
  36.     /**
  37.      * 判断队列是否为空
  38.      *
  39.      * 时间复杂度 O(1) ArrayQueue 和 LoopQueue同
  40.      * @return true为空, false反之
  41.      */
  42.     boolean isEmpty();
  43. }

注意:这里的Array类是前面动态数组实现的Array类,点击跳转:动态数组

  1. public class ArrayQueue<E> implements Queue<E> {
  3.     Array<E> array;
  5.     public ArrayQueue(int capacity){
  6.         array = new Array<>(capacity);
  7.     }
  9.     public ArrayQueue(){
  10.         array = new Array<>();
  11.     }
  13.     @Override
  14.     public void enqueue(E e) {
  15.         //向数组的末尾添加元素
  16.         array.addLast(e);
  17.     }
  19.     @Override
  20.     public E dequeue() {
  21.         //取出第一个元素
  22.         return array.removeFirst();
  23.     }
  25.     @Override
  26.     public E getFront() {
  27.         return array.getFirst();
  28.     }
  30.     @Override
  31.     public int getSize() {
  32.         return array.getSize();
  33.     }
  35.     @Override
  36.     public boolean isEmpty() {
  37.         return array.isEmpty();
  38.     }
  40.     public int getCapacity(){
  41.         return array.getCapacity();
  42.     }
  44.     @Override
  45.     public String toString() {
  46.         StringBuilder builder = new StringBuilder();
  47.         builder.append("Queue: ");
  48.         builder.append("front [");
  49.         for (int i = 0; i < array.getSize(); i++) {
  50.             builder.append(array.get(i));
  51.             if (i != array.getSize() - 1) {
  52.                 builder.append(",");
  53.             }
  54.         }
  55.         builder.append("] tail");
  56.         return builder.toString();
  57.     }
  59.     public static void main(String[] args) {
  60.         ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
  61.         for (int i = 0; i < 10; i++) {
  62.             //向队列中添加元素
  63.             arrayQueue.enqueue(i);
  64.             System.out.println(arrayQueue);
  65.             if (i % 3 == 2){
  66.                 arrayQueue.dequeue();
  67.                 System.out.println(arrayQueue);
  68.             }
  69.         }
  71.     }
  72. }

局限

队列的出队操作时间复杂度为O(n),因为出队是把数组的第一个元素删除,那么剩余的其他元素必须全部前移.

循环队列

队首front == 队尾tail 时队列为空
(tail + 1) % 队列长度capacity== front时 队列满

实现

  1. public class LoopQueue<E> implements Queue<E> {
  3.     private E[] data;
  4.     private int front, tail;
  5.     private int size;
  7.     @SuppressWarnings("unchecked")
  8.     public LoopQueue(int capacity) {
  9.         data = (E[]) new Object[capacity + 1];
  10.         front = 0;
  11.         tail = 0;
  12.         size = 0;
  13.     }
  15.     public int getCapacity() {
  16.         return data.length - 1;
  17.     }
  19.     public LoopQueue() {
  20.         this(10);
  21.     }
  23.     @Override
  24.     public void enqueue(E e) {
  25.         if ((tail + 1) % data.length == front) {
  26.             resize(getCapacity() * 2);
  27.         }
  28.         data[tail] = e;
  29.         tail = (tail + 1) % data.length;
  30.         size++;
  31.     }
  33.     @SuppressWarnings("unchecked")
  34.     private void resize(int newCapacity) {
  35.         E[] newData = (E[]) new Object[newCapacity + 1];
  36.         for (int i = 0; i < size; i++) {
  37.             //新数组第一个元素对应的data是front,第二个元素是front+1,第三个是front+2,依次类推
  38.             //循环队列可能会产生数组越界
  39.             newData[i] = data[(i + front) % data.length];
  40.         }
  41.         data = newData;
  42.         front = 0;
  43.         tail = size;
  44.     }
  46.     @Override
  47.     public E dequeue() {
  48.         if (isEmpty()) {
  49.             throw new IllegalArgumentException("Cannot dequeue from an empty queue");
  50.         }
  51.         E ret = data[front];
  52.         data[front] = null;
  53.         front = (front + 1) % data.length;
  54.         size--;
  55.         //缩容
  56.         if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
  57.             resize(getCapacity() / 2);
  58.         }
  59.         return ret;
  60.     }
  62.     @Override
  63.     public E getFront() {
  64.         if (isEmpty()) {
  65.             throw new IllegalArgumentException("Cannot dequeue from an empty queue");
  66.         }
  67.         return data[front];
  68.     }
  70.     @Override
  71.     public int getSize() {
  72.         return size;
  73.     }
  75.     @Override
  76.     public boolean isEmpty() {
  77.         return front == tail;
  78.     }
  80.     @Override
  81.     public String toString() {
  82.         StringBuilder builder = new StringBuilder();
  83.         builder.append(String.format("Queue: size = %d,capacity = %d\n", size, data.length));
  84.         builder.append("fount [");
  85.         for (int i = 0; i != tail; i = (i + 1) % data.length) {
  86.             builder.append(data[i]);
  87.             if (i != size - 1) {
  88.                 builder.append(",");
  89.             }
  90.         }
  91.         builder.append("] tail");
  92.         return builder.toString();
  93.     }
  94. }

数组队列和循环队列比较

  1. public class TestQueue {
  3.     public static void main(String[] args) {
  4.         int opCount = 100000;
  5.         System.out.println("数组队列ArrayQueue耗时:  " + testQueue(new ArrayQueue<>(), opCount) + "s");
  6.         System.out.println("循环队列LoopQueue耗时:  " + testQueue(new LoopQueue<>(), opCount) + "s");
  7.     }
  9.     private static double testQueue(Queue<Integer> q, int opCount) {
  10.         long startTime = System.nanoTime();
  11.         SecureRandom random = new SecureRandom();
  12.         for (int i = 0; i < opCount; i++) {
  13.             //入队操作
  14.             q.enqueue(random.nextInt(Integer.MAX_VALUE));
  15.         }
  16.         for (int i = 0; i < opCount; i++) {
  17.             //出队操作
  18.             q.dequeue();
  19.         }
  20.         long endTime = System.nanoTime();
  21.         return (endTime - startTime)/1000000000.0;
  22.     }
  23. }

双端队列

实现

  1. public class Deque<E> {
  2.     private E[] data;
  3.     private int front, tail;
  4.     private int size;
  6.     @SuppressWarnings("unchecked")
  7.     public Deque(int capacity) {
  8.         data = (E[]) new Object[capacity];
  9.         front = 0;
  10.         tail = 0;
  11.         size = 0;
  12.     }
  14.     public Deque() {
  15.         this(10);
  16.     }
  18.     public int getCapacity() {
  19.         return data.length;
  20.     }
  22.     public boolean isEmpty() {
  23.         return size == 0;
  24.     }
  26.     public int getSize() {
  27.         return size;
  28.     }
  30.     /**
  31.      * 在队尾添加元素
  32.      *
  33.      * @param e 元素
  34.      */
  35.     public void addLast(E e) {
  36.         // addLast 的逻辑和我们之前实现的队列中的 enqueue 的逻辑是一样的
  37.         if (size == getCapacity()) {
  38.             resize(getCapacity() * 2);
  39.         }
  41.         data[tail] = e;
  42.         tail = (tail + 1) % data.length;
  43.         size++;
  44.     }
  46.     /**
  47.      * 在队首添加元素
  48.      *
  49.      * @param e 元素
  50.      */
  51.     public void addFront(E e) {
  52.         if (size == getCapacity()) {
  53.             resize(getCapacity() * 2);
  54.         }
  55.         // 我们首先需要确定添加新元素的索引位置
  56.         // 这个位置是 front - 1 的地方
  57.         // 但是要注意，如果 front == 0，新的位置是 data.length - 1 的位置
  58.         front = front == 0 ? data.length - 1 : front - 1;
  59.         data[front] = e;
  60.         size++;
  61.     }
  63.     /**
  64.      * 删除队首元素
  65.      *
  66.      * @return 返回被删除的元素
  67.      */
  68.     public E removeFront() {
  69.         // removeFront 的逻辑和我们之前实现的队列中的 dequeue 的逻辑是一样的
  70.         if (isEmpty()) {
  71.             throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
  72.         }
  74.         E ret = data[front];
  75.         data[front] = null;
  76.         front = (front + 1) % data.length;
  77.         size--;
  78.         if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
  79.             resize(getCapacity() / 2);
  80.         }
  81.         return ret;
  82.     }
  84.     /**
  85.      * 删除队尾元素
  86.      *
  87.      * @return 被删除的元素
  88.      */
  89.     public E removeLast() {
  90.         if (isEmpty()) {
  91.             throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
  92.         }
  93.         // 计算删除掉队尾元素以后，新的 tail 位置
  94.         tail = tail == 0 ? data.length - 1 : tail - 1;
  95.         E ret = data[tail];
  96.         data[tail] = null;
  97.         size--;
  98.         if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
  99.             resize(getCapacity() / 2);
  100.         }
  101.         return ret;
  102.     }
  104.     /**
  105.      * 获取队首元素
  106.      *
  107.      * @return 元素
  108.      */
  109.     public E getFront() {
  110.         if (isEmpty()) {
  111.             throw new IllegalArgumentException("Queue is empty.");
  112.         }
  113.         return data[front];
  114.     }
  116.     /**
  117.      * 获取队尾元素
  118.      *
  119.      * @return 队尾元素
  120.      */
  121.     public E getLast() {
  122.         if (isEmpty()) {
  123.             throw new IllegalArgumentException("Queue is empty.");
  124.         }
  125.         // 因为 tail 指向的是队尾元素的下一个位置，我们需要计算一下真正队尾元素的索引
  126.         int index = tail == 0 ? data.length - 1 : tail - 1;
  127.         return data[index];
  128.     }
  130.     /**
  131.      * 缩容和扩容
  132.      *
  133.      * @param newCapacity 新的队列长度
  134.      */
  135.     @SuppressWarnings("unchecked")
  136.     private void resize(int newCapacity) {
  137.         E[] newData = (E[]) new Object[newCapacity];
  138.         for (int i = 0; i < size; i++) {
  139.             newData[i] = data[(i + front) % data.length];
  140.         }
  141.         data = newData;
  142.         front = 0;
  143.         tail = size;
  144.     }
  146.     @Override
  147.     public String toString() {
  149.         StringBuilder res = new StringBuilder();
  150.         res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
  151.         res.append("front [");
  152.         for (int i = 0; i < size; i++) {
  153.             res.append(data[(i + front) % data.length]);
  154.             if (i != size - 1) {
  155.                 res.append(", ");
  156.             }
  157.         }
  158.         res.append("] tail");
  159.         return res.toString();
  160.     }
  162.     public static void main(String[] args) {
  164.         // 在下面的双端队列的测试中，偶数从队尾加入；奇数从队首加入
  165.         Deque<Integer> dq = new Deque<>();
  166.         for (int i = 0; i < 16; i++) {
  167.             if (i % 2 == 0) {
  168.                 dq.addLast(i);
  169.             } else {
  170.                 dq.addFront(i);
  171.             }
  172.             System.out.println(dq);
  173.         }
  175.         // 之后，我们依次从队首和队尾轮流删除元素
  176.         System.out.println();
  177.         for (int i = 0; !dq.isEmpty(); i++) {
  178.             if (i % 2 == 0) {
  179.                 dq.removeFront();
  180.             } else {
  181.                 dq.removeLast();
  182.             }
  183.             System.out.println(dq);
  184.         }
  185.     }
  186. }

用队列实现栈(leetcode225)

要求

你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）
实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。

  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

    Java实现

    ```java public class MyStack {

    Queue queue;

    public MyStack() {

    1.   queue = new LinkedList<>();

    }

    /**

    • Push element x onto stack. */ public void push(int x) { //队列长度 int size = queue.size(); queue.offer(x); for (int i = 0; i < size; i++) {

      1.  //将队列的第一个元素删除并再次放入队列
      2.  queue.offer(queue.poll());

      } }

      /**

    • Removes the element on top of the stack and returns that element. */ public int pop() { if (queue.size() == 0) {

      1.  throw new IllegalArgumentException("queue is empty");

      } return queue.poll(); }

      /**

    • Get the top element. */ public int top() { if (queue.size() == 0) {

      1.  throw new IllegalArgumentException("queue is empty");

      } return queue.peek(); }

      /**

    • Returns whether the stack is empty. */ public boolean empty() { return queue.isEmpty(); }

}

  1. <a name="gR5G8"></a>
  2. ### go实现
  3. ```go
  4. type MyStack struct {
  5.     queue []int
  6. }
  8. /** Initialize your data structure here. */
  9. func Constructor() (s MyStack) {
  10.     return
  11. }
  13. /** Push element x onto stack. */
  14. func (s *MyStack) Push(x int) {
  15.     n := len(s.queue)
  16.     s.queue = append(s.queue, x)
  17.     for ; n > 0; n-- {
  18.         s.queue = append(s.queue, s.queue[0])
  19.         s.queue = s.queue[1:]
  20.     }
  21. }
  23. /** Removes the element on top of the stack and returns that element. */
  24. func (s *MyStack) Pop() int {
  25.     v := s.queue[0]
  26.     s.queue = s.queue[1:]
  27.     return v
  28. }
  30. /** Get the top element. */
  31. func (s *MyStack) Top() int {
  32.     return s.queue[0]
  33. }
  35. /** Returns whether the stack is empty. */
  36. func (s *MyStack) Empty() bool {
  37.     return len(s.queue) == 0
  38. }

用栈实现队列(leetcode232)

要求

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素

  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

    Java实现

    ```java public class MyQueue { Deque inStack; Deque outStack;

    /**

    • Initialize your data structure here. */ public MyQueue() { inStack = new LinkedList<>(); outStack = new LinkedList<>(); }

      /**

    • Push element x to the back of queue. */ public void push(int x) { inStack.push(x); }

      /**

    • Removes the element from in front of queue and returns that element. */ public int pop() { //当输出栈为空时 if (outStack.isEmpty()) {

      1.  //执行将输入栈中元素依次弹出并放入输出栈
      2.  in2out();

      } return outStack.pop(); }

      /**

    • Get the front element. */ public int peek() { if (outStack.isEmpty()) {

      1.  in2out();

      } return outStack.peek(); }

      /**

    • Returns whether the queue is empty. */ public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); }

      private void in2out() { //当输入栈不为空时,循环将输入栈得元素放入输出栈 while (!inStack.isEmpty()) {

      1.  outStack.push(inStack.pop());

      } } }

  1. <a name="2LqTh"></a>
  2. ### go实现
  3. ```go
  4. type MyQueue struct {
  5.     inStack, outStack []int
  6. }
  8. func Constructor1() (q MyQueue) {
  9.     return
  10. }
  12. func (q *MyQueue) Push(x int) {
  13.     q.inStack = append(q.inStack, x)
  14. }
  16. func (q *MyQueue) in2out() {
  17.     for len(q.inStack) > 0 {
  18.         q.outStack = append(q.outStack, q.inStack[len(q.inStack)-1])
  19.         q.inStack = q.inStack[:len(q.inStack)-1]
  20.     }
  21. }
  23. func (q *MyQueue) Pop() int {
  24.     if len(q.outStack) == 0 {
  25.         q.in2out()
  26.     }
  27.     x := q.outStack[len(q.outStack)-1]
  28.     q.outStack = q.outStack[:len(q.outStack)-1]
  29.     return x
  30. }
  32. func (q *MyQueue) Peek() int {
  33.     if len(q.outStack) == 0 {
  34.         q.in2out()
  35.     }
  36.     return q.outStack[len(q.outStack)-1]
  37. }
  39. func (q *MyQueue) Empty() bool {
  40.     return len(q.inStack) == 0 && len(q.outStack) == 0
  41. }

项目demo