面试中需要熟知的栈和队列

栈介绍

栈是一种抽象的数据类型，它支持push操作(在栈顶插入一个新元素)和pop操作(移除并返回最近添加的元素，即栈顶的元素)。作为一种抽象数据类型，栈可以使用数组或单链表来实现。

栈的操作通常被称为后进先出(LIFO)。

嵌套或递归函数调用都是通过栈来实现的，栈还用于实现深度优先搜索(DFS)，深度优先搜索可以使用递归或栈来实现。

栈在不用语言中的实现

语言	对应接口
C++	std::stack
Java	java.util.Stack
Python	通过List来模拟栈的操作
JavaScript	通过Array来模拟栈的操作

栈操作的时间复杂度

操作	时间复杂度
top	O(1)
push	O(1)
pop	O(1)
empty	O(1)
查找	O(n)

栈的边界条件

• 空栈，不要从空的栈里面取元素。
• 只有一个元素的栈。
• 只有两个元素的栈。

队列介绍

队列是一个线性集合，可以通过在一端添加元素(排队操作)，从另一端删除元素(出队列操作)。通常，添加元素的一端称为队列的后端或尾部，删除元素的一端称为队列的头部或前端。作为一种抽象数据类型，队列可以使用数组或单链表来实现。

队列的操作通常被称为FIFO(先进先出)。

广度优先搜索(BFS)通常使用队列实现。

队列在不用语言中的实现

语言	对应接口
C++	std::queue
Java	java.util.Queue

队列操作的时间复杂度

操作	时间复杂度
front	O(1)
back	O(1)
push	O(1)
pop	O(1)
empty	O(1)

面试中需要注意的事情

有些语言没有可以使用的内置队列这个数据类型，通常使用数组(JavaScript)或列表(Python)作为队列。在这种情况下，出队列操作(假设队列的前面在左边)将是O(n)，因为它需要将所有其他元素向左移动一位。

队列的边界条件

• 空队列
• 队列中只有一个元素
• 队列中只有两个元素