2026/8/22大约 4 分钟
用两个栈实现队列
要修改指针变量本身时，要传入二级指针
这道题的核心其实只有一句话：
一个栈负责入队，一个栈负责出队。
因为栈是 LIFO（后进先出），而队列要求 FIFO（先进先出），所以利用两个栈把顺序翻转一次，就能实现队列。
一、先实现一个栈
使用柔性数组成员：
typedef int stackData_t;
typedef struct
{
int top; // 栈顶索引
int capacity; // 容量
stackData_t data[]; // 柔性数组
} Stack_t;创建栈时一次性申请结构体和数组空间：
Stack_t *stack_init(stackData_t size)
{
Stack_t *st = malloc(sizeof(Stack_t)
+ size * sizeof(stackData_t));
if (st == NULL)
return NULL;
st->top = 0;
st->capacity = size;
return st;
}基本操作：
int stack_push(Stack_t *st, stackData_t item)
{
if (st->top >= st->capacity)
return -1;
st->data[st->top++] = item;
return 0;
}
int stack_pop(Stack_t *st)
{
if (st->top <= 0)
return -1;
return st->data[--st->top];
}
stackData_t stack_top(Stack_t *st)
{
if (st->top <= 0)
return -1;
return st->data[st->top - 1];
}
bool stack_empty(Stack_t *st)
{
return st->top == 0;
}二、两个栈如何实现队列
定义：
typedef struct
{
Stack_t *pushStack;
Stack_t *popStack;
} MyQueue;两个栈的职责固定：
pushStack
↓
只负责入队
popStack
↓
只负责出队比如连续入队：
1 2 3此时：
pushStack：1 2 3
popStack ：空如果直接从 pushStack 弹出，会得到：
3 2 1这不符合队列的 FIFO。
所以当 popStack 为空时，把 pushStack 全部倒过去：
pushStack popStack
1 2 3 → 3 2 1此时 popStack 的栈顶就是：
1也就实现了先进先出。
三、创建队列
MyQueue *myQueueCreate()
{
MyQueue *obj = malloc(sizeof(MyQueue));
if (obj == NULL)
return NULL;
obj->pushStack = stack_init(10);
obj->popStack = stack_init(10);
return obj;
}四、入队
入队非常简单，直接进入 pushStack：
void myQueuePush(MyQueue *obj, int x)
{
stack_push(obj->pushStack, x);
}例如：
push(1)
push(2)
push(3)
pushStack：
1 2 3五、出队
真正的关键在这里：
int myQueuePop(MyQueue *obj)
{
if (stack_empty(obj->popStack))
{
while (!stack_empty(obj->pushStack))
{
stack_push(obj->popStack,
stack_pop(obj->pushStack));
}
}
return stack_pop(obj->popStack);
}核心逻辑：
popStack 有数据
↓
直接 pop
popStack 没数据
↓
pushStack 全部倒过去
↓
再 pop为什么不能每次都倒？
例如：
第一次：
pushStack：1 2 3
popStack ：空
倒入：
pushStack：空
popStack ：3 2 1
pop → 1此时：
popStack：3 2下一次 pop：
直接 pop → 2不需要再次搬运。
这就是这道题最关键的优化。
六、查看队头
peek 和 pop 的前半部分完全一样，只是不真正弹出元素：
int myQueuePeek(MyQueue *obj)
{
if (stack_empty(obj->popStack))
{
while (!stack_empty(obj->pushStack))
{
stack_push(obj->popStack,
stack_pop(obj->pushStack));
}
}
return stack_top(obj->popStack);
}区别只有：
pop → stack_pop()
peek → stack_top()七、判断队列是否为空
两个栈都为空，队列才为空：
bool myQueueEmpty(MyQueue *obj)
{
return stack_empty(obj->pushStack)
&& stack_empty(obj->popStack);
}因为存在这种情况：
pushStack：空
popStack ：1 2 3此时队列当然不是空的。
八、释放队列
因为 MyQueue 里面有两个动态申请的栈，所以需要全部释放：
void stack_destory(Stack_t **st)
{
(*st)->capacity = 0;
(*st)->top = 0;
free(*st);
*st = NULL;
//如果操作的是整个st,那么就需要一个二级指针，因为在修改一个函数参数的值
//要get真实地址
//分开操作变量的话就不需要，因为一级指针对应的就是真实地址
}void myQueueFree(MyQueue *obj)
{
stack_destory(&obj->popStack);
stack_destory(&obj->pushStack);
free(obj);
}这里使用二级指针：
&obj->popStack
&obj->pushStack是因为 stack_destory() 不仅要 free()，还希望把原来的指针设置成 NULL。
九、最终把整个思路串起来
队列
入队 → pushStack
│
│ popStack为空
↓
整体倒入
↓
popStack
│
pop / peek例如：
push 1
push 2
push 3
pushStack：
1 2 3
第一次 pop：
pushStack popStack
空 ← 3 2 1
pop → 1
第二次 pop：
pushStack popStack
空 3 2
直接 pop → 2十、这道题真正要记住的
pushStack：只负责入队
popStack：只负责出队
popStack 有数据：
直接操作
popStack 没数据：
把 pushStack 全部倒过去本质就是：
两个“后进先出”的栈，通过翻转一次顺序，实现“先进先出”的队列。
栈、队列、指针、动态内存、柔性数组、一级/二级指针
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int stackData_t;
typedef struct
{
int top;//栈顶索引
int capacity;//容量
stackData_t data[];
}Stack_t;
Stack_t *stack_init(stackData_t size)
{
Stack_t* st =(Stack_t *)malloc(sizeof(Stack_t) + size * sizeof(stackData_t));
st->top = 0;
st->capacity = size;
return st;
}
void stack_destory(Stack_t **st)
{
(*st)->capacity = 0;
(*st)->top = 0;
free(*st);
*st = NULL;
//如果操作的是整个st,那么就需要一个二级指针，因为在修改一个函数参数的值
//要get真实地址
//分开操作变量的话就不需要，因为一级指针对应的就是真实地址
}
int stack_size(Stack_t *st)
{
return st->top;
}
stackData_t stack_top(Stack_t* st)
{
if (st->top <= 0)
{
perror("stack empty:");
return -1;
}
return st->data[st->top - 1];
}
bool stack_empty(Stack_t* st)
{
return st->top == 0;
}
int stack_push(Stack_t* st, stackData_t item)
{
if (st->top >= st->capacity)
{
perror("push overflow error:");
return -1;
}
st->data[st->top++] = item;
return 0;
}
int stack_pop(Stack_t* st)
{
if (st->top <= 0)
{
perror("pop error:");
return -1;
}
return st->data[--st->top];
}
typedef struct
{
Stack_t *pushStack;
Stack_t *popStack;
}MyQueue;
MyQueue* myQueueCreate()
{
MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
pst->popStack=stack_init(10);
pst->pushStack=stack_init(10);
return pst;
}
void myQueuePush(MyQueue* obj, int x) {
stack_push(obj->pushStack, x);
}
int myQueuePop(MyQueue* obj)
{
if (stack_empty(obj->popStack))
{
while (!stack_empty(obj->pushStack))
{
stack_push(obj->popStack,
stack_pop(obj->pushStack));
}
}
return stack_pop(obj->popStack);
}
int myQueuePeek(MyQueue* obj) {
if (stack_empty(obj->popStack))
{
while (!stack_empty(obj->pushStack))
{
stack_push(obj->popStack,
stack_pop(obj->pushStack));
}
}
return stack_top(obj->popStack);
}
bool myQueueEmpty(MyQueue* obj) {
return stack_empty(obj->pushStack)
&& stack_empty(obj->popStack);
}
void myQueueFree(MyQueue* obj) {
stack_destory(&obj->popStack);
stack_destory(&obj->pushStack);
free(obj);
}