💓 博客主页：倔强的石头的CSDN主页
📝Gitee主页：倔强的石头的gitee主页
⏩ 文章专栏：《数据结构与算法 经典例题》C语言
期待您的关注
目录
一、问题描述
二、前置知识
三、解题思路
四、C语言实现代码
🍃队列实现代码：
🍃基于队列实现栈的代码：
一、问题描述
原题摘自
225. 用队列实现栈 - 力扣（LeetCode）
二、前置知识
关于栈的详细讲解请阅读这篇文章
【数据结构与算法】使用数组实现栈：原理、步骤与应用-CSDN博客
关于队列的详细讲解请阅读这篇文章
【数据结构与算法】使用单链表实现队列：原理、步骤与应用-CSDN博客
三、解题思路
使用两个队列（Queue）实现栈（Stack）的功能是一种常见的数据结构练习。栈是一种后进先出（LIFO）的数据结构，而队列则是先进先出（FIFO）的。解题的关键就在于如何通过巧妙地使用两个队列的先进先出，来可以模拟栈的后进先出行为。
以下是使用两个队列实现栈的基本步骤和原理：
栈的结构定义：包含两个队列的结构
- 初始化：初始化两个空队列，在任意时刻，我们只会使用其中一个队列来进行入栈和出栈操作，而另一个队列则保持为空。
- 入栈（Push）：
- 将元素添加到非空队列的末尾。
- 如果两个队列都为空，则选择任意一个队列添加元素。
- 出栈（Pop）：
- 如果两个队列都为空，说明栈也为空，此时不能进行出栈操作。
- 将非空队列中的元素（除了最后一个）逐个出队并入队到另一个队列中，直到只剩下最后一个元素。此时，该元素就是栈顶元素，我们将其出队并返回。
- 查看栈顶元素（Peek）：
- 如果两个队列都为空，说明栈也为空，此时不能查看栈顶元素。
- 如果队列的实现允许查看队尾数据，会比较简单，直接返回非空队列的队尾数据即可
- 如果队列实现只允许查看队首数据，那么也需要移动元素
- 我们将非空队列的元素（除了最后一个）逐个出队并入队到另一个队列中，直到只剩下最后一个元素。此时，该元素就是栈顶元素，将其保存下来，入队到另一个队列中，并在本队列出队（这样做是为了保持只有一个非空队列）然后返回该元素。
这里画图解释队列元素的移动过程（注意：为方便理解对队列的结构进行了简化）
四、C语言实现代码
🍃队列实现代码：
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q)
{assert(q);//接收的地址必须是有效的（队列必须存在）q->head = q->tail = NULL;q->size = 0;
}// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL)//判定是否申请成功{perror("newnode error\n");exit(1);}newnode->data = data;newnode->next = NULL;if (q->head == NULL)//对空队列入队的处理{q->head = q->tail = newnode;}else //对非空队列入队的处理{q->tail->next = newnode;q->tail = newnode;}q->size++;
}// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(q->head);//队列不能为空if (q->head == q->tail)//对只有一个元素的队列的出队处理{free(q->head);q->head = q->tail = NULL;}else //对存在多个元素的队列的出队处理{QNode* next = q->head->next;free(q->head);q->head = next;}q->size--;
}// 获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);assert(q->head);//队列不能为空return q->head->data;
}// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{assert(q);assert(q->head);return q->tail->data;
}// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);return q->size;
}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);return q->size == 0;
}// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);while (q->head)//释放所有节点{QNode* next = q->head->next;free(q->head);q->head = next;}q->head = q->tail = NULL;q->size = 0;
}
🍃基于队列实现栈的代码：
typedef struct
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* stack = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(stack->q1));//调用队列的初始化函数QueueInit(&(stack->q2));return stack;
}void myStackPush(MyStack* obj, int x)
{assert(obj);if (QueueEmpty(&(obj->q1)))//将数据插入到非空队列{QueuePush(&(obj->q2), x);}elseQueuePush(&(obj->q1), x);
}int myStackPop(MyStack* obj)
{assert(obj);assert(obj->q1.size || obj->q2.size);//必须存在一个非空队列才能出栈
Queue* empty = &(obj->q1);//假设q1是空队列
Queue* nempty = &(obj->q2);
if (!QueueEmpty(&(obj->q1)))//进行判断并调整
{empty = &(obj->q2);nempty = &(obj->q1);
}
while (nempty->size > 1)//移动元素至最后一个
{QueuePush(empty, QueueFront(nempty));QueuePop(nempty);
}
int top = QueueFront(nempty);//返回最后的元素
QueuePop(nempty);
return top;
}int myStackTop(MyStack* obj)
{assert(obj);assert(obj->q1.size || obj->q2.size);//必须存在一个非空队列才能获取元素
//如果队列的实现允许查看队尾数据，会比较简单
/*if (QueueEmpty(&(obj->q1)))return QueueBack(&(obj->q2));
elsereturn QueueBack(&(obj->q1));*///如果队列的实现不允许查看队尾数据，依然需要移动元素
Queue* empty = &(obj->q1);//假设q1是空队列
Queue* nempty = &(obj->q2);
if (!QueueEmpty(&(obj->q1)))//进行判断并调整
{empty = &(obj->q2);nempty = &(obj->q1);
}
while (nempty->size > 1)//移动元素至最后一个
{QueuePush(empty, QueueFront(nempty));QueuePop(nempty);
}
int top = QueueFront(nempty);//返回最后的元素
QueuePush(empty, QueueFront(nempty));QueuePop(nempty);
return top;
}bool myStackEmpty(MyStack* obj) {return obj->q1.size == 0 && obj->q2.size == 0;
}void myStackFree(MyStack* obj) {QueueDestroy(&(obj->q1));
QueueDestroy(&(obj->q2));
free(obj);//动态申请的空间不要忘记释放
}
最后附上通过代码截图
