栈与队列综合实战（一）：用栈实现队列、用队列实现栈

各位同学，今天咱们来点硬核的。前面几章我们把栈和队列的底层原理、基本操作都捋了一遍。但说实话，光会写个入栈出栈，那只是入门水平。真正的嵌入式开发里，你经常会遇到一个尴尬的情况：手头只有栈的库，但项目里需要一个队列；或者只有队列的库，却要模拟栈的行为。

怎么办？自己重写一个？别急，我教你一招——用栈实现队列，用队列实现栈。这可不是炫技，这是实打实的工程技巧。

一、为什么需要这种“套娃”操作？

我在做一个小型RTOS项目时，遇到过这么个事：芯片的硬件FIFO只支持栈操作（后进先出），但我的任务调度器需要队列（先进先出）。重新写一个队列？资源不够。于是我就用两个栈，硬生生模拟出了一个队列。嗯，效果还不错。

说白了，这种技巧的核心思想就是：用两个相同的数据结构，通过“倒腾”数据，改变数据的进出顺序。

二、用栈实现队列

2.1 思路解析

栈是后进先出，队列是先进先出。怎么用栈模拟队列？你想想看，如果我们把数据先压入栈A，再逐个弹出压入栈B，那么栈B的栈顶元素，不就是最早进入栈A的那个元素吗？

举个例子：

• 入队顺序：1 → 2 → 3
• 全部压入栈A：栈底[1,2,3]栈顶
• 从栈A弹出，压入栈B：栈底[3,2,1]栈顶
• 从栈B弹出：得到1（最早入队的元素）

完美实现了先进先出。

2.2 代码实现

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

#define MAX_SIZE 100

// 栈结构体
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// 队列结构体（内部用两个栈）
typedef struct {
    Stack *stack_in;   // 入队栈
    Stack *stack_out;  // 出队栈
} Queue;

// 栈操作
void stack_init(Stack *s) {
    s->top = -1;
}

int stack_push(Stack *s, int val) {
    if (s->top >= MAX_SIZE - 1) return -1;
    s->data[++s->top] = val;
    return 0;
}

int stack_pop(Stack *s, int *val) {
    if (s->top < 0) return -1;
    *val = s->data[s->top--];
    return 0;
}

int stack_is_empty(Stack *s) {
    return s->top == -1;
}

// 队列操作
Queue* queue_create() {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->stack_in = (Stack*)malloc(sizeof(Stack));
    q->stack_out = (Stack*)malloc(sizeof(Stack));
    stack_init(q->stack_in);
    stack_init(q->stack_out);
    return q;
}

void queue_enqueue(Queue *q, int val) {
    stack_push(q->stack_in, val);
}

int queue_dequeue(Queue *q, int *val) {
    // 如果出队栈为空，把入队栈的所有元素倒过来
    if (stack_is_empty(q->stack_out)) {
        int tmp;
        while (!stack_is_empty(q->stack_in)) {
            stack_pop(q->stack_in, &tmp);
            stack_push(q->stack_out, tmp);
        }
    }
    return stack_pop(q->stack_out, val);
}

int queue_is_empty(Queue *q) {
    return stack_is_empty(q->stack_in) && stack_is_empty(q->stack_out);
}

三、用队列实现栈

3.1 思路解析

队列是先进先出，栈是后进先出。怎么用队列模拟栈？这里有个小技巧：每次入“栈”时，把新元素放到队列尾部，然后把前面的所有元素依次出队再入队。这样新元素就跑到队列头部了，出队时自然就是它先出来。

举个例子：

• 当前队列：[1,2]（1在队头，2在队尾）
• 要压入3：先把3入队 → [1,2,3]
• 然后把1和2依次出队再入队 → [2,3,1] → [3,1,2]
• 现在队头是3，出队得到3（后进先出）

3.2 代码实现

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

#define MAX_SIZE 100

// 队列结构体
typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int count;
} Queue;

// 栈结构体（内部用两个队列）
typedef struct {
    Queue *q1;
    Queue *q2;
} StackByQueue;

// 队列操作
void queue_init(Queue *q) {
    q->front = 0;
    q->rear = 0;
    q->count = 0;
}

int queue_enqueue(Queue *q, int val) {
    if (q->count >= MAX_SIZE) return -1;
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->count++;
    return 0;
}

int queue_dequeue(Queue *q, int *val) {
    if (q->count == 0) return -1;
    *val = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->count--;
    return 0;
}

int queue_is_empty(Queue *q) {
    return q->count == 0;
}

// 栈操作
StackByQueue* stack_create() {
    StackByQueue *s = (StackByQueue*)malloc(sizeof(StackByQueue));
    s->q1 = (Queue*)malloc(sizeof(Queue));
    s->q2 = (Queue*)malloc(sizeof(Queue));
    queue_init(s->q1);
    queue_init(s->q2);
    return s;
}

void stack_push(StackByQueue *s, int val) {
    // 先把新元素入队到q2
    queue_enqueue(s->q2, val);
    
    // 把q1的所有元素移到q2
    int tmp;
    while (!queue_is_empty(s->q1)) {
        queue_dequeue(s->q1, &tmp);
        queue_enqueue(s->q2, tmp);
    }
    
    // 交换q1和q2
    Queue *temp = s->q1;
    s->q1 = s->q2;
    s->q2 = temp;
}

int stack_pop(StackByQueue *s, int *val) {
    return queue_dequeue(s->q1, val);
}

int stack_is_empty(StackByQueue *s) {
    return queue_is_empty(s->q1);
}

四、两种实现对比

对比项	栈实现队列	队列实现栈
核心操作	入队栈 + 出队栈	主队列 + 辅助队列
入队/入栈时间复杂度	O(1)	O(n)
出队/出栈时间复杂度	均摊O(1)	O(1)
空间复杂度	O(n)	O(n)
适用场景	频繁入队，偶尔出队	频繁出栈，偶尔入栈

五、知识体系总览

下面这张图，把本章的核心逻辑串起来了。我建议你多看几遍，理解数据是怎么在两个结构之间“倒腾”的。

六、实战中的坑与建议

我做了这么多年嵌入式，总结出几个经验：

1. 不要滥用这种“套娃”实现。能用原生数据结构就用原生的，这种实现只是为了解决特定场景下的兼容问题。
2. 注意内存管理。我见过有人用栈实现队列，结果忘记释放stack_out的内存，导致内存泄漏。嵌入式系统内存本来就紧张，这种错误很致命。
3. 考虑多线程安全。如果你的队列或栈会被多个任务访问，记得加锁。我曾经在一个中断服务函数里直接操作队列，结果数据全乱了。
4. 测试边界条件。空队列出队、满队列入队、只入不出、只出不入……这些情况都要覆盖到。

---

公众号:蓝海资料掘金营，微信deep3321