Skip to content

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

原文:https://www.techinterviewhandbook.org/algorithms/queue/

简介

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

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

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

学习资源

实现

语言 应用程序接口
C++ T2std::queue
Java 语言(一种计算机语言,尤用于创建网站) java.util.Queue 。使用 java.util.ArrayDeque
计算机编程语言 T2queue
Java Script 语言 不适用的

时间复杂度

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

面试时要注意的事情

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

拐角情况

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

基本问题

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

推荐练习题

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

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式,并有内容帮助你快速修改基本的数据结构和算法。最重要的是,AlgoMonster 不是基于订阅的——支付一次性费用,就可以获得终身访问今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题,但从问题模式的角度来进行练习,这是一种我也同意的学习方法,我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题,并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式,而不是背答案! 现在获得终身使用权→

掌握编码面试:数据结构+算法

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



回到顶部