使用栈实现队列

队列 是一种遵循 FIFO（先进先出）原则的线性数据结构，其中插入操作从队尾执行，删除操作从队头执行。栈是一种遵循 LIFO（后进先出）原则的线性 数据结构，其中插入和删除操作都从栈顶执行。

让我们来理解一下使用栈实现队列。

假设我们有如下所示的队列

现在我们将执行三次入队操作，如下所示

enqueue(5);

enqueue(2);

enqueue(3);

执行上述三次入队操作后，队列将如下图所示

在上面的 栈 中，我们可以看到栈顶元素是 3。如果我们对上述栈执行删除操作，则元素 3 将从栈中删除。另一方面，队列中的删除操作是从队头执行的，队头元素是 5。为了使用栈实现队列，我们需要考虑两个栈。

假设我们有两个栈，分别命名为 Stack1 和 Stack2，如下所示

正如我们所观察到的，上面的栈是空的。现在，我们将执行对 Stack1 的 push 操作。首先，我们将 push 5，然后是 2，最后我们将 push 元素 3，如下所示

现在我们将从 Stack1 中逐个弹出元素，并将它们推入 Stack2，如下所示

一旦元素被插入到 Stack2 中，栈顶元素是 5，它将被从 Stack 2 中弹出，如下所示

一旦栈顶元素从 Stack2 中弹出，所有元素将从 Stack2 移回 Stack 1，如下所示

有两种方法可以使用栈实现队列

• 使出队操作耗时
• 使入队操作耗时

第一种方法：使出队操作耗时

如果我们通过使出队操作耗时来实现队列，则意味着入队操作的时间复杂度为 O(1)，出队操作的时间复杂度为 O(n)。

在这种情况下，当我们在栈中插入元素时，元素被添加到栈顶，因此需要 O(1) 的时间。

在出队操作的情况下，我们需要考虑两个栈，名为 Stack1 和 Stack2。首先，我们将元素插入 Stack1，然后我们从 Stack1 中删除所有元素。一旦所有元素都从 Stack1 中弹出，它们就会被添加到 Stack2 中。栈顶元素将从 Stack2 中弹出，然后所有元素从 Stack2 移回 Stack1。在这里，数据执行了两次出队操作，因此时间复杂度为 O(n)。

C 语言实现

输出

第二种方法：使入队操作耗时。

如果我们通过使入队操作耗时来实现队列，则意味着入队操作的时间复杂度为 O(n)，出队操作的时间复杂度为 O(1)。

首先，我们将考虑两个栈，名为 stack1 和 stack2。在入队操作的情况下，首先将 stack1 中的所有元素弹出并推入 stack2。一旦 stack1 中的所有元素都推入 stack2，新元素将被添加到 stack1 中。在 stack1 中添加新元素后，所有元素将从 stack1 移回 stack2。在这里，入队操作的时间复杂度将为 O(n)。

在 stack1 中，最旧的元素将位于栈顶，因此执行出队操作所需的时间将为 O(1)。

C 语言实现

输出