队列在C语言中如何实现和应用，有哪些关键知识点需要掌握？

本文共计3524个文字，预计阅读时间需要15分钟。

预存队列是一种先进先出（FIFO）的线性表，通常使用链表或数组来实现。队列允许从后端（rear）插入新元素（插入，enqueue），同时从前端（front）弹出元素（弹出，dequeue）。

预备

队列，是一种先进先出（FIFO）的线性表，一般来说会使用链表或者数组来实现它。

队列被允许从后端（rear）插入（insert）新元素，称作入列（push，enqueue）；而从前端（front）弹出（pop）元素，称作出列（pop，dequeue）。

学术上说它和堆栈常常被同时提起，因为堆栈与队列几乎一摸一样，除了出栈时也在后端弹出元素，从而构成了后进先出（LIFO）的数据结构。

古典的单向链表/单向队列

单向链表表示的队列，出列时必须遍历整个链表，直至链尾的前一位，然后摘除链尾来实现出列操作。

毫无疑问，这一定是代价很高的。

但这种方案的优势在于任何时候任何人都能够随手写得出来。也就是说，它是最具备可手撸性的一种实现方案，虽然出列代价较高，但对于相当多的场景来说那点代价 CPU 根本不当作是事。

双向链表/双向队列

双向链表的好处是在链表头尾的操作都是 O(1) 的，代价极低，可以视作毫无代价。但这是用额外的两个指针的空间代价来达成的。对于像 std::deque<long> 这样的双向链表来说，每个链表元素的数据部分（payload）需要 8 bytes，而附着在 payload 上的指针则需要 16 bytes（典型的 64bit 计算时），相当于说超出数据实体两倍的代价，不可謂不昂贵。