队列

  • 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
  • 结构如下图所示

队列.jpg

2.队列的特点

  • 线性表：链表或者数组

  • FIFO(先进先出)

    数组实现队列基本操作

    数组可以用到CPU高速缓存,某种情况下效率比链表好


    数组实现，存在空间浪费问题

    ```java /**

    • @author lfy

    • @date 2022-03-07 */ public class MyQueue implements Queue{

      private E[] data; private int head; private int tail; private int n;

      public MyQueue(int capacity) {

      1. this.data = (E[])new Object[capacity];
      2. n=capacity;

      }

      @Override public void push(E e) {

      1. data[tail] = e;
      2. tail++;

      }

      @Override public E pop() {

      1. if (isEmpty()){
      2.     return null;}
      3. E e = data[head];
      4. head++;
      5. return e;

      }

      @Override public boolean isEmpty() {

      1. return head == tail;

      } }

  1. <a name="EErmc"></a>
  2. #### 循环数组实现
  3. ```java
  4. /**
  5.  * @author lfy
  6.  * @date 2022-03-07
  7.  */
  8. public class MyCycleArrayQueue<E> implements Queue<E>{
  10.     private E[] data;
  11.     private int head;
  12.     private int tail;
  13.     private int n;
  15.     public MyCycleArrayQueue(int capacity) {
  16.         this.data = (E[])new Object[capacity];
  17.         n=capacity;
  18.     }
  19.     @Override
  20.     public void push(E e) {
  21.         if ((tail+1) % n == head) {
  22.             return;
  23.         }
  24.         data[tail] = e;
  25.         tail = (tail+1) % n;
  26.     }
  28.     @Override
  29.     public E pop() {
  30.         if (isEmpty()) {
  31.             return null;
  32.         }
  33.         E e = data[head];
  34.         head = (head+1)%n;
  35.         return e;
  36.     }
  38.     @Override
  39.     public boolean isEmpty() {
  40.         return head == tail;
  41.     }
  42. }

阻塞队列：

  • 此种具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列。阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。