Algorithms study cheatsheets

Coding interview 的 Queue cheatsheet

Queue 学习指南，包含练习题、技巧、时间复杂度与推荐资源

Introduction

Queue 是一种线性结构：在一端 enqueue 入队，在另一端 dequeue 出队。入队的一端叫 back/tail/rear，出队的一端叫 head/front。作为抽象数据类型，queue 可用 array 或 singly linked list 实现。

这种行为叫 FIFO（first in, first out）。名字来自现实生活中排队的类比。

Breadth-first search 常用 queue 实现。

Language	API
C++	`std::queue`
Java	`java.util.Queue`.Use `java.util.ArrayDeque`
Python	`queue`
JavaScript	N/A

很多语言没有内置 Queue，候选人常用 array（JavaScript）或 list（Python）模拟。但如果把队头放左边，dequeue 会变成 O(n)，因为要整体左移。遇到这种情况，建议说明这一点，并向面试官说明可以假设有 O(1) dequeue 的 queue 结构。

该 topic 必练题。