手撕队列模拟栈

破碎的山岚2026/8/22大约 5 分钟

两个队列实现栈

队列先进先出（FIFO），栈后进先出（LIFO），两者顺序正好相反，所以要用两个队列"倒一手"。

核心就一个字：搬。
入栈：元素直接进队列；
出栈：把前 n-1 个元素搬到另一个队列，剩下的最后一个就是栈顶，弹出它。

动画演示

图中说明：

上面两个队列：Queue1 / Queue2，紫色三角 = head（队头），青色三角 = rear（队尾）；
黄色 = 正在被搬移的元素；
底部是逻辑上的栈视图（LIFO），top 指向栈顶。

可以看到：pop() 时把前面的元素全部搬走，只留下最后进入的那个弹出。

所以核心思路就是：

保证每次新入栈的元素，都被放到队列的“最后”，然后把原来的元素全部搬到另一个队列，让新元素成为队头，从而实现出栈。

1. 队列结构

typedef struct
{
    int *data;
    int head;
    int rear;
    int size;
} Queue;

使用循环队列：

head → 队头
rear → 队尾

初始化：

Queue* initQueue(int k)
{
    Queue* obj = malloc(sizeof(Queue));

    obj->data = malloc(sizeof(int) * k);
    obj->head = -1;
    obj->rear = -1;
    obj->size = k;

    return obj;
}

head == -1 表示队列为空。

2. 两个队列实现一个栈

typedef struct
{
    Queue *queue1;
    Queue *queue2;
} MyStack;

规则非常简单：

queue1、queue2
    ↓
始终只有一个队列存放栈内元素

例如：

栈：

1
2
3   ← 栈顶

可能存成：

queue1：
1 2 3

queue2：
空

3. 入栈 Push

如果 queue1 不为空，就继续往 queue1 里放。

如果 queue1 为空，就使用 queue2。

void myStackPush(MyStack* obj, int x)
{
    if (isEmpty(obj->queue1))
        enQueue(obj->queue2, x);
    else
        enQueue(obj->queue1, x);
}

所以：

push(1)
push(2)
push(3)

queue1：1 2 3

4. 出栈 Pop：真正的核心

假设：

queue1：

1 2 3

栈顶应该是：

但队列只能从：

开始出队。

所以把前面的元素全部搬到另一个队列：

queue1              queue2

1 2 3      →        1 2

最后：

queue1 = 3
queue2 = 1 2

然后弹出 3。

代码：

int myStackPop(MyStack* obj)
{
    if (isEmpty(obj->queue1))
    {
        while (obj->queue2->head != obj->queue2->rear)
        {
            enQueue(obj->queue1,
                    deQueue(obj->queue2));
        }

        return deQueue(obj->queue2);
    }

    while (obj->queue1->head != obj->queue1->rear)
    {
        enQueue(obj->queue2,
                deQueue(obj->queue1));
    }

    return deQueue(obj->queue1);
}

这里最关键的一句话：

把除了最后一个元素之外的所有元素搬走，最后留下的那个就是栈顶。

5. 栈顶 Top

这里要特别注意：

不能固定使用 queue2->rear。

哪个队列非空，就应该看哪个队列的 rear：

int myStackTop(MyStack* obj)
{
    if (isEmpty(obj->queue1))
        return obj->queue2->data[obj->queue2->rear];

    return obj->queue1->data[obj->queue1->rear];
}

因为真正保存栈元素的队列可能是 queue1，也可能是 queue2。

6. 判空

两个队列都为空，栈才为空：

bool myStackEmpty(MyStack* obj)
{
    return isEmpty(obj->queue1)
        && isEmpty(obj->queue2);
}

7. 最终记忆

整个题实际上只有一个核心动作：

Push：
    直接入当前非空队列

Pop：
    把前 n-1 个元素搬到另一个队列
    最后一个元素就是栈顶

Top：
    看当前非空队列的 rear

Empty：
    两个队列都空

可以浓缩成一句话：

两个队列实现栈，本质就是“搬家”：每次出栈时，把前面的元素全部搬走，只留下最后进入的那个元素。

这就是这道题的“剑魂”。

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct
{
	int* data;
	int head;
	int rear;
	int size;

}Queue;

typedef struct
{
	Queue* queue1;
	Queue* queue2;

}MyStack;

Queue* initQueue(int k)
{
	Queue* obj = (Queue *)malloc(sizeof(Queue));
	obj->data = (int*)malloc(sizeof(int)*k);
	obj->head = -1;
	obj->rear = -1;
	obj->size = k;
	return obj;
}

void enQueue(Queue* obj, int item)
{
	if (obj->head == -1)
	{
		obj->head = 0;
	}
	obj->rear = (obj->rear + 1) % obj->size;
	obj->data[obj->rear] = item;
}

int deQueue(Queue* obj)
{
	int a = obj->data[obj->head];
	if (obj->head == obj->rear)
	{
		obj->head = -1;
		obj->rear = -1;
		return a;
	}
	obj->head = ((obj->head + 1) % obj->size);
	return a;
}

bool isEmpty(Queue* obj)
{
	return obj->head == -1;
}

MyStack* myStackCreate() {
	MyStack* my_stack = (MyStack*)malloc(sizeof(MyStack));
	my_stack->queue1 = initQueue(10);
	my_stack->queue2 = initQueue(10);
	return my_stack;
}

void myStackPush(MyStack* obj, int x) {
	if (isEmpty(obj->queue1))
	{
		enQueue(obj->queue2, x);
	}
	else
	{
		enQueue(obj->queue1, x);
	}
}

int myStackPop(MyStack* obj) {
	//看哪一个不为空
	if (isEmpty(obj->queue1))
	{
		while (obj->queue2->head != obj->queue2->rear)
		{
			enQueue(obj->queue1, deQueue(obj->queue2));
		}
		return deQueue(obj->queue2);
	}

	while (obj->queue1->head != obj->queue1->rear)
	{
		enQueue(obj->queue2, deQueue(obj->queue1));
	}

	return deQueue(obj->queue1);
}

int myStackTop(MyStack* obj) {
	// 哪个队列非空，就看哪个队列的 rear
	if (isEmpty(obj->queue1))
	{
		return obj->queue2->data[obj->queue2->rear];
	}
	return obj->queue1->data[obj->queue1->rear];
}

bool myStackEmpty(MyStack* obj) {
	return isEmpty(obj->queue1) && isEmpty(obj->queue2);
}

void myStackFree(MyStack* obj) {
	free(obj->queue1->data);
	obj->queue1->data = NULL;
	free(obj->queue1);
	obj->queue1 = NULL;
	free(obj->queue2->data);
	obj->queue2->data = NULL;
	free(obj->queue2);
	obj->queue2 = NULL;
	free(obj);
	obj = NULL;
}

四个操作一句话

操作	做法	时间复杂度
`push`	哪个队列非空就入哪个队列	O(1)
`pop`	把前 `n-1` 个搬到另一队列，弹出最后一个	O(n)
`top`	看非空队列的 `rear`	O(1)
`empty`	两个队列都为空	O(1)

空间复杂度 O(n)：两个队列加起来最多存 n 个元素。

两个注意点

pop 里的 while (head != rear)：循环结束后队列只剩 1 个元素，它就是要弹出的栈顶。head == rear 时队列只有 1 个元素，直接弹出。
top 千万别写死 queue2->rear。任意时刻只有一个队列存元素，另一个是空的。若 queue1 非空而还拿 queue2->rear（此时为 -1）去取 queue1->data，就是数组越界。所以必须"哪个非空看哪个"。

和上一题对比

两个栈实现队列：一个栈负责入，一个栈负责出，倒一次就 FIFO。
两个队列实现栈：出栈时把前面的全搬走，只留最后一个，就是 LIFO。

一句话总结：

队列模拟栈 = 出栈时"搬家"：把前 n-1 个元素搬走，最后留下的就是栈顶。