# 用于编码面试的队列备忘单

> 原文：<https://www.techinterviewhandbook.org/algorithms/queue/>

<header>

## 简介[](#introduction "Direct link to heading")

队列是在序列中维护的元素的线性集合，并且可以通过在序列的一端添加元素(**入队**操作)和从另一端移除元素(**出列**操作)来修改。通常，序列中添加元素的末端称为队列的后部，删除元素的末端称为队列的前部。作为一种抽象数据类型，队列可以使用数组或单链表来实现。

这种行为通常被称为 FIFO(先进先出)。这种类型的结构的名称“队列”来源于对现实生活中排队等待商品或服务的人们的类比。

广度优先搜索通常使用队列来实现。

## 学习资源[](#learning-resources "Direct link to heading")

*   读物
    *   [排队还是不排队](https://medium.com/basecs/to-queue-or-not-to-queue-2653bcde5b04)，基本秒
*   录像
    *   [队列](https://www.coursera.org/lecture/data-structures/queues-EShpq)，加州大学圣地亚哥分校

## 实现[](#implementations "Direct link to heading")

| 语言 | 应用程序接口 |
| --- | --- |
| C++ | [T2`std::queue`](https://docs.microsoft.com/en-us/cpp/standard-library/queue-class) |
| Java 语言(一种计算机语言，尤用于创建网站) | [`java.util.Queue`](https://docs.oracle.com/javase/10/docs/api/java/util/Queue.html) 。使用 [`java.util.ArrayDeque`](https://docs.oracle.com/javase/10/docs/api/java/util/ArrayDeque.html) |
| 计算机编程语言 | [T2`queue`](https://docs.python.org/3/library/queue.html) |
| Java Script 语言 | 不适用的 |

## 时间复杂度[](#time-complexity "Direct link to heading")

| 操作 | 大 O |
| --- | --- |
| 排队/出价 | O(1) |
| 出列/轮询 | O(1) |
| 前面 | O(1) |
| 背部 | O(1) |
| isEmpty | O(1) |

## 面试时要注意的事情[](#things-to-look-out-for-during-interviews "Direct link to heading")

大多数语言没有可以使用的内置队列类，候选语言通常使用数组(JavaScript)或列表(Python)作为队列。但是，请注意，这种情况下的入队操作将是 O(n ),因为它需要将所有其他元素移位一位。在这种情况下，您可以向面试官指出这一点，并说您假设有一个队列数据结构可以使用，它具有高效的入队操作。

## 拐角情况[](#corner-cases "Direct link to heading")

*   空队列
*   有一个项目的队列
*   两个物品排队

## 基本问题[](#essential-questions "Direct link to heading")

如果你在学习这个话题，这些是需要练习的基本问题。

*   [使用队列实现堆栈](https://leetcode.com/problems/implement-stack-using-queues)

## 推荐练习题[](#recommended-practice-questions "Direct link to heading")

*这些是在你为题目学习并练习了基本问题后推荐练习的问题。*

*   [使用堆栈实现队列](https://leetcode.com/problems/implement-queue-using-stacks)
*   [设计循环队列](https://leetcode.com/problems/design-circular-queue)
*   [设计点击计数器(LeetCode Premium)](https://leetcode.com/problems/design-hit-counter)

## 推荐课程[](#recommended-courses "Direct link to heading")

### [AlgoMonster](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)[T3】](#algomonster "Direct link to heading")

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得**终身访问**。 [**今天加入七折优惠→**](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)

### [寻找编码面试:编码问题的模式](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)[](#grokking-the-coding-interview-patterns-for-coding-questions "Direct link to heading")

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。**学习和理解模式，而不是背答案！** [**现在获得终身使用权→**](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)

### [掌握编码面试:数据结构+算法](https://fxo.co/DQpY)[](#master-the-coding-interview-data-structures--algorithms "Direct link to heading")

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 **19 个小时**的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 [**结账→**](https://fxo.co/DQpY)

</header>