先进先出队列（简称队列）是一种基于先进先出（FIFO）策略的集合类型。可以使用数组和链表实现。

API

成员函数（Item 是泛型变量） 功能
Queue() 创建空队列
void enqueue() 添加一个元素
Item dequeue() 删除最早添加的元素
boolean isEmpty() 队列是否为空
int size() 队列中的元素数量

实现

两种实现都支持 forEach 迭代。

数组实现

  1. import java.util.Iterator;
  2. import java.util.NoSuchElementException;
  3. import java.util.Random;
  5. public class ResizingArrayQueue<Item> implements Iterable<Item> {
  6.     // 初始化队列数组大小
  7.     private static final int INIT_CAPACITY = 8;
  8.     // 队列元素数组
  9.     private Item[] q;
  10.     // 当前队列的元素数量
  11.     private int n;
  12.     // 队列头部元素
  13.     private int first;
  14.     // 队列尾部元素
  15.     private int last;
  17.     /**
  18.      * 初始化空队列
  19.      */
  20.     public ResizingArrayQueue() {
  21.         q = (Item[]) new Object[INIT_CAPACITY];
  22.         n = 0;
  23.         first = 0;
  24.         last = 0;
  25.     }
  27.     /**
  28.      * 当前队列是否为空
  29.      *
  30.      * @return 为空返回 true，否则放回 false
  31.      */
  32.     public boolean isEmpty() {
  33.         return n == 0;
  34.     }
  36.     /**
  37.      * 当前队列的元素数量
  38.      *
  39.      * @return 元素数量
  40.      */
  41.     public int size() {
  42.         return n;
  43.     }
  45.     /**
  46.      * 动态调整队列数组大小
  47.      *
  48.      * @param capacity
  49.      */
  50.     private void resize(int capacity) {
  51.         assert capacity >= n;
  52.         Item[] copy = (Item[]) new Object[capacity];
  53.         for (int i = 0; i < n; i++) {
  54.             copy[i] = q[(first + i) % q.length];
  55.         }
  56.         q = copy;
  57.         first = 0;
  58.         last = n;
  59.     }
  61.     /**
  62.      * 添加一个元素
  63.      *
  64.      * @param item
  65.      */
  67.     public void enqueue(Item item) {
  68.         if (n == q.length) resize(2 * q.length);
  69.         q[last++] = item;
  70.         if (last == q.length) last = 0;
  71.         n++;
  72.     }
  74.     /**
  75.      * 删除队列最早添加的元素
  76.      *
  77.      * @return 队列最早添加的元素
  78.      */
  79.     public Item dequeue() {
  80.         if (isEmpty()) throw new NoSuchElementException("Queue underflow");
  81.         Item item = q[first];
  82.         q[first] = null;
  83.         n--;
  84.         first++;
  85.         if (first == q.length) first = 0;
  86.         if (n > 0 && n == q.length / 4) resize(q.length / 2);
  87.         return item;
  88.     }
  90.     /**
  91.      * 查看队列最早添加元素（不删除）
  92.      *
  93.      * @return 队列最早添加的元素
  94.      */
  95.     public Item peek() {
  96.         if (isEmpty()) throw new NoSuchElementException("Queue underflow");
  97.         return q[first];
  98.     }
  100.     /**
  101.      * forEach 迭代
  102.      *
  103.      * @return
  104.      */
  105.     public Iterator<Item> iterator() {
  106.         return new ArrayIterator();
  107.     }
  109.     private class ArrayIterator implements Iterator<Item> {
  110.         private int i = 0;
  112.         public boolean hasNext() {
  113.             return i < n;
  114.         }
  116.         public void remove() {
  117.             throw new UnsupportedOperationException();
  118.         }
  120.         public Item next() {
  121.             if (!hasNext()) throw new NoSuchElementException();
  122.             Item item = q[(i + first) % q.length];
  123.             i++;
  124.             return item;
  125.         }
  126.     }
  128.     public static void main(String[] args) {
  129.         ResizingArrayQueue<String> queue = new ResizingArrayQueue<>();
  130.         for (int i = 0; i < 8; i++) {
  131.             //  generator random string
  132.             int leftLimit = 97; // letter 'a'
  133.             int rightLimit = 122; // letter 'z'
  134.             int targetStringLength = 3;
  135.             Random random = new Random();
  136.             String generatedString = random.ints(leftLimit, rightLimit + 1)
  137.                     .limit(targetStringLength)
  138.                     .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
  139.                     .toString();
  140.             queue.enqueue(generatedString);
  141.         }
  143.         System.out.println("isEmpty: " + queue.isEmpty());
  144.         System.out.println("size: " + queue.size());
  145.         System.out.println("peek: " + queue.peek());
  147.         System.out.println();
  148.         for (String s : queue) {
  149.             System.out.println("str: " + s);
  150.         }
  151.     }
  152. }

其中在 resize() 和 next() 方法中有这么一句代码：

  1. Item item = q[(i + first) % q.length];

还有 enqueue() 和 dequeue() 中的代码：

  1. if (last == q.length) last = 0; // enqueue()
  2. if (first == q.length) first = 0; // dequeue()

对应的是这种情况：

ResizingArrayStack.jpg

链表实现

  1. package chapter1.c1_3;
  3. import java.util.Iterator;
  4. import java.util.NoSuchElementException;
  5. import java.util.Random;
  7. public class LinkedQueue<Item> implements Iterable<Item> {
  8.     private int n;
  9.     private Node first;
  10.     private Node last;
  12.     /**
  13.      * 内部结点类
  14.      */
  15.     private class Node {
  16.         private Item item;
  17.         private Node next;
  18.     }
  20.     /**
  21.      * 初始化空栈
  22.      */
  23.     private LinkedQueue() {
  24.         first = null;
  25.         last = null;
  26.         n = 0;
  27.         assert check();
  28.     }
  31.     /**
  32.      * 是否为空栈
  33.      *
  34.      * @return 为空返回 true，否则返回 false
  35.      */
  36.     public boolean isEmpty() {
  37.         return first == null;
  38.     }
  40.     public int size() {
  41.         return n;
  42.     }
  44.     /**
  45.      * 查看最早添加的元素（不删除）
  46.      *
  47.      * @return 最早添加的元素
  48.      */
  49.     public Item peek() {
  50.         if (isEmpty()) throw new NoSuchElementException("Queue underflow");
  51.         return first.item;
  52.     }
  54.     /**
  55.      * 添加一个元素
  56.      *
  57.      * @param item
  58.      */
  59.     public void enqueue(Item item) {
  60.         Node oldLast = last;
  61.         last = new Node();
  62.         last.item = item;
  63.         last.next = null;
  64.         if (isEmpty()) first = last;
  65.         else oldLast.next = last;
  66.         n++;
  67.         assert check();
  68.     }
  70.     /**
  71.      * 删除最早添加的元素
  72.      *
  73.      * @return 最早添加的元素
  74.      */
  75.     public Item dequeue() {
  76.         if (isEmpty()) throw new NoSuchElementException("Queue underflow");
  77.         Item item = first.item;
  78.         first = first.next;
  79.         n--;
  80.         if (isEmpty()) last = null;
  81.         assert check();
  82.         return item;
  83.     }
  85.     /**
  86.      * 元素转化为字符串
  87.      *
  88.      * @return 字符串
  89.      */
  90.     public String toString() {
  91.         StringBuilder s = new StringBuilder();
  92.         for (Item item : this) {
  93.             s.append(item).append(" ");
  94.         }
  95.         return s.toString();
  96.     }
  98.     /**
  99.      * 检测内部变量
  100.      *
  101.      * @return 全部通过返回 true，否则返回 false
  102.      */
  103.     public boolean check() {
  104.         if (n < 0) {
  105.             return false;
  106.         } else if (n == 0) {
  107.             if (first != null) return false;
  108.             return last == null;
  109.         } else if (n == 1) {
  110.             if (first == null || last == null) return false;
  111.             if (first != last) return false;
  112.             return first.next == null;
  113.         } else {
  114.             if (first == null || last == null) return false;
  115.             if (first == last) return false;
  116.             if (first.next == null) return false;
  117.             if (last.next != null) return false;
  119.             int numberOfNodes = 0;
  120.             for (Node x = first; x != null && numberOfNodes <= n; x = x.next) {
  121.                 numberOfNodes++;
  122.             }
  123.             if (numberOfNodes != n) return false;
  125.             Node lastNode = first;
  126.             while (lastNode.next != null) {
  127.                 lastNode = lastNode.next;
  128.             }
  129.             return last == lastNode;
  130.         }
  131.     }
  133.     /**
  134.      * 支持 forEach 迭代
  135.      *
  136.      * @return
  137.      */
  138.     @Override
  139.     public Iterator<Item> iterator() {
  140.         return new LinkedIterator();
  141.     }
  143.     private class LinkedIterator implements Iterator<Item> {
  144.         private Node current = first;
  146.         @Override
  147.         public boolean hasNext() {
  148.             return current != null;
  149.         }
  151.         @Override
  152.         public Item next() {
  153.             if (!hasNext()) throw new NoSuchElementException();
  154.             Item item = current.item;
  155.             current = current.next;
  156.             return item;
  157.         }
  159.         @Override
  160.         public void remove() {
  161.             throw new UnsupportedOperationException();
  162.         }
  163.     }
  165.     public static void main(String[] args) {
  166.         ResizingArrayQueue<String> queue = new ResizingArrayQueue<>();
  167.         for (int i = 0; i < 8; i++) {
  168.             //  generator random string
  169.             int leftLimit = 97; // letter 'a'
  170.             int rightLimit = 122; // letter 'z'
  171.             int targetStringLength = 3;
  172.             Random random = new Random();
  173.             String generatedString = random.ints(leftLimit, rightLimit + 1)
  174.                     .limit(targetStringLength)
  175.                     .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
  176.                     .toString();
  177.             queue.enqueue(generatedString);
  178.         }
  180.         System.out.println("isEmpty: " + queue.isEmpty());
  181.         System.out.println("size: " + queue.size());
  182.         System.out.println("peek: " + queue.peek());
  184.         System.out.println();
  185.         for (String s : queue) {
  186.             System.out.println("str: " + s);
  187.         }
  188.     }
  189. }

对应的图：

linkedQueue.jpg

附件：

LinkedQueue.drawioResizingArrayStack.drawio

参考：