队列的结构

可以把队列想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。

队列最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。特别是长得像一个环的循环队列。在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，就需要循环数组实现的循环队列。

先进者先出，是典型的“队列”。

后进者先出，先进者后出，是典型的“栈”结构。

栈只支持**入栈 push()和出栈 pop()**两个操作。

队列只支持：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

1570433339703

队列跟栈一样也是一种操作受限的线性表数据结构。

循环队列、阻塞队列、并发队列等具有某些额外特性的队列，它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。

比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；

Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

队列的实现

用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

数组实现的顺序队列

java基于数组的实现：

// 用数组实现的队列public class ArrayQueue {  // 数组：items，数组大小：n  private String[] items;  private int n = 0;  // head 表示队头下标，tail 表示队尾下标  private int head = 0;  private int tail = 0;  // 申请一个大小为 capacity 的数组  public ArrayQueue(int capacity) {    items = new String[capacity];    n = capacity;  }  // 入队  public boolean enqueue(String item) {    // 如果 tail == n 表示队列已经满了    if (tail == n) return false;    items[tail] = item;    ++tail;    return true;  }  // 出队  public String dequeue() {    // 如果 head == tail 表示队列为空    if (head == tail) return null;    // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了    String ret = items[head];    ++head;    return ret;  }}

把上面代码翻译成python：

from typing import Optional
class ArrayQueue:
    """用数组实现的队列"""    def __init__(self, capacity: int):
        self.items: list = [None] * capacity
        self._capacity = capacity
        self.head = 0  # 队头下标        self.tail = 0  # 队尾下标    def enqueue(self, item: str) -> bool:
        """入队"""        if self.tail == self._capacity:
            return False        self.items[self.tail] = item
        self.tail += 1        return True    def dequeue(self) -> Optional[str]:
        """出队"""        if self.head == self.tail:
            return None        item = self.items[self.head]
        self.head += 1        return item
    def __str__(self) -> str:
        return str(self.items[self.head:self.tail])