C++ 使用栈实现队列

在本文中，您将学习如何在 C++ 中使用栈实现队列，并了解其实现。

将栈数据结构实现为队列，其中底层数据结构是 push（添加元素）和 pop（移除元素）操作。

栈是后进先出 (LIFO) 的数据结构，而队列是先进先出 (FIFO) 的数据结构。栈将顶部元素弹出，并将新元素推入栈顶。另一方面，队列将元素入队（插入）到底部，同时将元素出队（移除）到顶部。

队列的实现

使用栈数据结构，有两种方法可以实现队列。一种方法使用一个栈，另一种使用两个栈。

使用两个栈

此方法确保最旧的插入元素始终位于 stack1 的顶部，以便 deQueue 操作可以简单地从 stack1 弹出。stack2 用于将元素放置在 stack1 的顶部。

enqueue(x)

• 当 stack1 不为空时，将所有元素从 stack1 推送到 stack2。
• 将 x 推送到 stack1。
• 将所有元素推回 stack1。

dequeue(x)

• 如果 stack1 为空，则显示错误消息。
• 从 stack1 弹出一个项目并返回它。

示例

让我们举一个例子来说明如何在 C++ 中使用两个栈实现队列。

输出

使用一个栈

队列也可以仅使用一个用户栈来实现，并且它使用递归。

enqueue(x)

• 将 x 推送到 stack_。

dequeue(x)

• 如果 stack_ 为空，则显示错误消息。
• 如果 stack_ 只有一个元素，则返回它。
• 递归地将 stack_ 中的所有项弹出，将其放入名为 ret 的变量中，将其推回 stack_，然后返回 ret。

Dequeue() 的第三步确保总是返回最后弹出的项。当stack_中只剩下一个项时，递归停止，从 dequeue() 中的 stack_ 返回最后一个元素，并将剩余的项推回 stack_。

示例

让我们举一个例子来说明如何在 C++ 中使用一个栈实现队列。

输出

C++ 中使用栈实现队列的优点

使用两个栈在 C++ 中实现队列有几个优点，尤其是在特定情况下的简单性和效率方面。以下是一些优点：

• 简单性：实现起来并不太困难。有两个栈：stack1 用于入队操作，stack2 用于出队操作。它可能有助于代码的理解和维护。
• 出队函数的有效性：在摊还意义上，出队操作的时间复杂度为 O(1)。原因是只有当 stack2 为空时，组件才会从 stack1 转移到 stack2。一旦转移，stack2 可以高效地多次出队，直到再次为空，此时会启动另一次转移。
• 空间效率：O(n) 是空间复杂度，其中 n 是队列中的元素数量。这是因为每个元素只存储在 stack1 或 stack2 中。在其他队列实现中，通过使用更多数据结构可以实现更高的空间复杂度。
• 灵活性：此方法允许您选择自己选择的底层数据结构（栈）。在栈比其他数据结构更有意义或更有效的情况下，这可能是有益的。
• 入队操作：入队操作的时间复杂度为O(1)，因为它们直接将元素推入 stack1。然而，在入队操作频繁而出队操作不频繁的情况下，其他数据结构（如链表或动态数组）可能更有效。