队列和栈是什么？有什么区别？

队列和栈是两种核心线性数据结构，核心区别在于数据进出顺序：队列遵循“先进先出”（FIFO），如排队打印任务或消息队列；栈遵循“后进先出”（LIFO），如函数调用栈或括号匹配。队列在表的一端插入、另一端删除，适用于任务调度、BFS等需顺序处理的场景；栈在表的一端进行插入和删除，适用于递归、表达式求值、DFS等需回溯处理的场景。两者均可通过数组或链表实现：数组实现连续存储、访问高效，但固定大小易溢出，队列需用循环队列避免“假溢出”；链表实现动态扩容、灵活，但有指针开销。选择队列还是栈，关键在于问题的数据处理顺序需求：若需按序处理或层序遍历，选队列；若需嵌套或回溯，选栈。实际应用中，二者常结合使用，如复杂算法或解析器设计。

队列和栈，它们都是我们处理数据时特别常用到的两种线性数据结构，核心区别在于它们数据进出的顺序：队列就像排队，先来的先走，是“先进先出”（FIFO）的；而栈则像叠盘子，最后放上去的盘子最先被拿走，是“后进先出”（LIFO）的。理解它们，可以说就抓住了很多算法和系统设计的关键。

队列和栈是什么？有什么区别？

要说清楚队列和栈，得从它们的基本操作说起。

队列（Queue），顾名思义，就是排队。它是一种只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作的线性表。你可以把它想象成一个管道，数据从一端进去，从另一端出来，严格遵循“先进先出”（First-In, First-Out, FIFO）的原则。比如，你打印文件，任务会排队；或者在银行柜台，先到的人先办理业务，这都是队列的典型场景。

栈（Stack），则更像一个有底的容器，比如一个桶，或者一叠盘子。它是一种只能在表的一端（通常称为栈顶，top）进行插入和删除操作的线性表。数据总是从栈顶进出，所以最后进入的数据会最先被取出，也就是“后进先出”（Last-In, First-Out, LIFO）。我们平时用浏览器的“后退”按钮，或者编程语言里函数调用的过程，都离不开栈。

它们最根本的区别，就在于数据访问的顺序。队列是两端操作，一端进，一端出；栈是单端操作，进出都在同一端。这个看似简单的差异，决定了它们在不同场景下的独特作用。

为什么说队列和栈是两种核心数据结构？它们在实际编程中有什么典型应用场景？

在我看来，队列和栈之所以能被称为“核心”数据结构，是因为它们抽象出了两种最基本、最直观的数据处理模式：顺序处理和回溯处理。它们不光是理论上的概念，更是我们日常编程中解决各种问题的利器。

队列的典型应用场景：

• 操作系统任务调度： 比如CPU时间片轮转调度，或者IO请求的处理，任务通常会排队等待执行，确保公平性和顺序性。
• 消息队列： 在分布式系统里，服务之间通信常常通过消息队列，生产者把消息扔进去，消费者按顺序取出来处理，解耦了系统，也保证了消息的有序性。
• 广度优先搜索（BFS）： 在图或树的遍历中，BFS需要一层一层地探索节点，这时候队列就派上用场了，它能保证你先访问完当前层的所有节点，再去访问下一层。
• 缓存淘汰策略： 虽然LRU更复杂，但简单的FIFO缓存策略就是基于队列实现的，最先进入缓存的数据，在缓存满时最先被淘汰。

栈的典型应用场景：

• 函数调用栈： 这是最经典的应用了。当一个函数调用另一个函数时，当前函数的执行状态（局部变量、返回地址等）会被压入栈中，等被调用的函数执行完毕，再从栈顶弹出，恢复之前的状态。递归函数尤其依赖这个机制。
• 表达式求值： 比如把中缀表达式（如

  2 + 3 * 4

  ）转换为后缀表达式或前缀表达式，或者直接计算表达式的值，栈都能高效地处理运算符的优先级和括号匹配。

• 撤销/重做功能（Undo/redo）： 在文本编辑器或图像处理软件中，用户的每一步操作都可以被压入一个栈，需要撤销时就从栈顶弹出最近的操作；如果再配合一个“重做栈”，就能实现完整的撤销重做功能。
• 深度优先搜索（DFS）： 与BFS相对，DFS需要沿着一条路径尽可能深地探索，直到无路可走才回溯。这个过程自然地契合了栈的LIFO特性，或者说，递归调用本身就是利用了语言的调用栈。
• 括号匹配： 检查代码或文本中的括号（

  ()

  ,

  []

  ,

  {}

  ）是否正确配对，通常会用一个栈来辅助：遇到左括号就入栈，遇到右括号就检查栈顶是否是匹配的左括号，是则出栈，否则就是不匹配。

从操作特性来看，队列和栈的实现方式有哪些异同点？

实现队列和栈，通常有两种主要方式：基于数组和基于链表。这两种方式各有优缺点，也直接反映了它们操作特性上的异同。

共同点：

无论是队列还是栈，它们本质上都是线性结构，因此都可以用数组或链表来承载数据。它们的核心操作都涉及到对特定位置的数据进行插入和删除，以及判断是否为空、是否已满（针对固定大小的实现）。

实现方式上的差异：

• 基于数组的实现：

  • 栈： 相对简单。我们只需要一个数组和一个指向栈顶的指针（或索引）。入栈时，指针向上移动，数据存入新位置；出栈时，数据从指针位置取出，指针向下移动。效率很高，因为是连续内存访问。但缺点是数组大小固定，可能遇到“栈溢出”的问题。
  • 队列： 稍微复杂一点。需要两个指针，一个指向队头（front），一个指向队尾（rear）。入队时队尾指针移动，出队时队头指针移动。这里有个“假溢出”的问题，就是当队头指针不断往前走，数组前面空了一大截，队尾指针却到了数组末尾，看起来满了，但实际还有空间。所以，通常会采用“循环队列”的实现方式，把数组看成一个环形结构，队尾指针达到末尾后，可以回到数组开头继续入队，有效利用空间。

• 基于链表的实现：

  • 栈： 同样很简洁。每次入栈就是创建新节点并将其作为新的头节点（栈顶）；出栈就是移除头节点。这种方式天生支持动态扩容，不会有固定大小的限制，但每次操作都需要额外的指针操作和内存分配/释放开销。
  • 队列： 也非常直观。通常需要维护一个头指针（指向队头）和一个尾指针（指向队尾）。入队时，新节点添加到链表尾部，更新尾指针；出队时，移除头节点，更新头指针。同样，它也是动态大小的，没有假溢出问题，但在内存访问上不如数组连续。

在我实际写代码时，如果对数据量大小有清晰预估，且追求极致性能，可能会倾向于数组实现。但如果数据量不确定，或者需要频繁的插入删除，链表实现往往更灵活、更不容易出错。选择哪种，更多的是根据具体场景的需求来权衡。

在解决具体算法问题时，如何选择使用队列还是栈？

选择队列还是栈，这其实是个对问题本质理解的考量。它不像选个算法那么复杂，更多是看你数据的“流向”和“处理顺序”需求。

最直接的判断依据就是：数据是需要“先进先出”地处理，还是“后进先出”地处理？

• 如果你需要按顺序处理任务，或者探索一个结构时要一层一层地推进，那么队列往往是你的首选。 比如，你在实现一个任务调度器，或者在图上做广度优先搜索（BFS），你肯定希望先来的任务先执行，或者先探索完当前层的所有节点。队列的FIFO特性完美契合了这种需求。
• 如果你需要处理嵌套结构，或者在探索过程中需要回溯，那么栈通常是更合适的工具。 想象一下，你在解析一个复杂的数学表达式，或者在图上做深度优先搜索（DFS），你可能需要深入一个分支，处理完后再回到上一个点继续。栈的LIFO特性，使得它非常适合这种“压入-弹出”的嵌套处理模式，它能帮你记住“回来的路”。函数调用、递归实现，都是这种模式的体现。

举个例子，我在写一个解析器的时候，遇到括号匹配的问题，我自然会想到用栈。因为当我遇到一个左括号，我需要“记住”它，直到我遇到一个右括号，这时我才需要检查最近的那个左括号是否匹配。这种“最近的先处理”的逻辑，就是栈的强项。

反过来，如果我在设计一个游戏，需要管理玩家的行动指令，我希望玩家的指令能按发出顺序执行，那我就会考虑用队列来存储这些指令。

所以，关键在于，不要被数据结构的名字迷惑，而是要深入思考你的问题：数据的入队和出队、入栈和出栈，究竟是为了解决什么样的逻辑问题？一旦你明确了数据应该如何被访问和处理，选择哪种数据结构就水到渠成了。有时候，甚至会发现一个问题需要队列和栈的组合才能优雅地解决，比如某些图算法，或者更复杂的解析任务。