用队列实现栈（C语言详解）——从错误思路到本质理解（结尾全代码）

目录一、问题本质二、整体结构设计三、两种核心方法非常关键一、方法一push时调整搬运到空队列二、方法二pop时调整你的方法三、两种方法本质对比重点四、正确思路关键转折五、核心实现六、执行过程有图有真相七、参数传递关键细节八、为什么不用全局变量九、为什么不用 Queue*十、内存释放高频考点十三、进阶思考一、问题本质题目要求«使用队列FIFO实现栈LIFO»---核心矛盾队列先进先出FIFO栈后进先出LIFO 关键点«❗不是“怎么存数据”而是“怎么控制顺序”»---二、整体结构设计typedef struct { Queue q1; Queue q2; } MyStack;---内存结构必须理解MyStack├──q1一个队列│ ├── phead → 节点 → 节点 → ...│ ├── ptail│ └── size└── q2另一个队列├── phead → 节点 → ...├── ptail└── size 每个队列本质是一个链表---三、两种核心方法非常关键在用队列实现栈时本质都是«❗通过“搬运元素”来改变顺序从而模拟 LIFO»但策略分为两种---一、方法一push时调整搬运到空队列核心思路push 时新元素先进空队列再把旧元素全部搬过来---执行过程示意原队列1 2push(3)步骤q2: 3q1: 1 2↓q2: 3 1 2↓交换 q1 和 q2最终q1: 3 1 2---特点操作| 复杂度push| O(n)pop| O(1)top| O(1)---本质理解在 push 时就把顺序排好保证队头永远是栈顶---二、方法二pop时调整你的方法核心思路pop 时把前 n-1 个元素搬到另一个队列剩下最后一个栈顶---执行过程示意q1: 1 2 3q2: 空pop()↓q1: 3q2: 1 2↓删除 3---特点操作| 复杂度push| O(1)pop| O(n)top| O(1)---本质理解平时不调整在需要取栈顶时才“临时整理顺序”---三、两种方法本质对比重点维度| 方法一push调整| 方法二pop调整调整时机| push 时| pop 时思维方式| 提前整理| 延迟处理push| 慢O(n)| 快O(1)pop| 快O(1)| 慢O(n)---四、统一本质最重要这两种方法本质是一样的都是在“移动元素顺序”只是选择了不同的时机------六、进阶还有第三种一个队列push 后旋转队列把新元素转到最前面四、正确思路关键转折 push简单pop时调整顺序就是向非空的队列push数据pop是借助另一个空链表转换一下前size-1个最后一个就是栈顶进行pop操作即可---五、核心实现---1️⃣ push入栈void myStackPush(MyStack* obj, int x) { if(!QueueEmpty((obj-q1))) { QueuePush((obj-q1),x); } else{ QueuePush((obj-q2),x); } } 只负责存---2️⃣ pop出栈——核心int myStackPop(MyStack* obj) { Queue* NoEmpty (obj-q1), *Empty (obj-q2); if(QueueEmpty((obj-q1))) { NoEmpty (obj-q2); Empty (obj-q1); }// 搬运前 n-1 个元素while(QueueSize(NoEmpty) 1) { QueuePush(Empty, QueueFront(NoEmpty)); QueuePop(NoEmpty); }// 剩下的就是栈顶int top QueueFront(NoEmpty);QueuePop(NoEmpty);return top;}--- 本质每次 pop把前 n-1 个搬走最后一个就是栈顶---3️⃣ top取栈顶int myStackTop(MyStack* obj) { if(!QueueEmpty((obj-q1))) return QueueBack((obj-q1)); else return QueueBack((obj-q2)); }---4️⃣ 判空bool myStackEmpty(MyStack* obj) { return QueueEmpty((obj-q1)) QueueEmpty((obj-q2)); } ---六、执行过程有图有真相---初始状态q1: 1 → 2 → 3q2: 空---pop过程① 搬运前两个q1: 1 → 2 → 3q2: 空↓q1: 3q2: 1 → 2---② 删除最后一个pop 3--- 成功实现“后进先出”---七、参数传递关键细节---✅ 必须传指针QueuePush(obj-q1, x);---❌ 错误写法QueuePush(obj-q1, x); 只会修改副本原数据不变---八、为什么不用全局变量如果写成Queue q1;Queue q2;--- 问题- ❌ 多个栈共享数据- ❌ 数据混乱- ❌ 不符合接口设计--- 正确MyStack 内部管理自己的队列---九、为什么不用 Queue*Queue* q1;Queue* q2;---❌ 问题- 需要额外 malloc- 需要多次 free- 容易内存泄漏--- 当前场景Queue 很小 不需要共享 ✔ 用值更简单---十、内存释放高频考点---❌ 错误free(obj);---✔ 正确void myStackFree(MyStack* obj) { QueueDestroy((obj-q1)); QueueDestroy((obj-q2)); free(obj); }--- 原理链表节点是多次 malloc必须逐个释放---十一、复杂度分析操作| 时间复杂度push| O(1)pop| O(n)top| O(1)---十二、这一题真正考察的能力--- 1. 数据结构本质«❗结构 ≠ 用法而是行为控制»--- 2. 顺序控制能力关键不是存数据而是调整顺序--- 3. 内存管理谁申请 → 谁释放--- 4. 封装设计MyStack 管理 QueueQueue 管理节点---十三、进阶思考 有没有办法push O(n)pop O(1) 或者只用一个队列实现栈下一篇可以写单队列“旋转法”---✅ 总结«这题的本质不是“用队列”而是❗在受限结构下构造另一种行为LIFO»---typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType val; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; void QueueInit(Queue* pq) { assert(pq); pq-phead NULL; pq-ptail NULL; pq-size 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur pq-phead; while (cur) { QNode* next cur-next; free(cur); cur next; } pq-phead pq-ptail NULL; pq-size 0; } // 队尾插入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc fail); return; } newnode-next NULL; newnode-val x; if (pq-ptail NULL) { pq-phead pq-ptail newnode; } else { pq-ptail-next newnode; pq-ptail newnode; } pq-size; } // 队头删除 void QueuePop(Queue* pq) { assert(pq); assert(pq-size ! 0); /*QNode* next pq-phead-next; free(pq-phead); pq-phead next; if (pq-phead NULL) pq-ptail NULL;*/ // 一个节点 if (pq-phead-next NULL) { free(pq-phead); pq-phead pq-ptail NULL; } else // 多个节点 { QNode* next pq-phead-next; free(pq-phead); pq-phead next; } pq-size--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(pq-phead); return pq-phead-val; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq-ptail); return pq-ptail-val; } int QueueSize(Queue* pq) { assert(pq); return pq-size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq-size 0; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* pst (MyStack*)malloc(sizeof(MyStack)); QueueInit((pst-q1)); QueueInit((pst-q2)); return pst; } void myStackPush(MyStack* obj, int x) { assert(obj); if(!QueueEmpty((obj-q1))) { QueuePush((obj-q1),x); } else{ QueuePush((obj-q2),x); } } int myStackPop(MyStack* obj) { //将前size-1个导入空队列 在pop //假设法找到非空队列、 Queue* NoEmpty (obj-q1), *Empty (obj-q2); if(QueueEmpty((obj-q1))) { NoEmpty (obj-q2); Empty (obj-q1); } while(QueueSize(NoEmpty) 1) { QueuePush(Empty,QueueFront(NoEmpty)); QueuePop(NoEmpty); } //此时NoEmpty就剩下1个在删除 int top QueueFront(NoEmpty); QueuePop(NoEmpty); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty((obj-q1))) { return QueueBack((obj-q1)); } else { return QueueBack((obj-q2)); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty((obj-q1)) QueueEmpty((obj-q2)); } void myStackFree(MyStack* obj) { QueueDestroy((obj-q1)); QueueDestroy((obj-q2)); free(obj); } /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj myStackCreate(); * myStackPush(obj, x); * int param_2 myStackPop(obj); * int param_3 myStackTop(obj); * bool param_4 myStackEmpty(obj); * myStackFree(obj); */