您现在的位置是：首页 >技术交流 >队列实现栈（你看我讲的是不是最细的就完了）网站首页技术交流
队列实现栈（你看我讲的是不是最细的就完了）
最伟大的成就往往起源于最强烈的热情。 -- 诺曼·文森特·皮尔
目录
?4.myStackPop出队列操作并返回剩下的一个元素，也就是栈顶的元素
题目描述:
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
注意:这里myStack.pop()和myStack.top()都是先保存栈顶的元素，然后再返回栈顶的元素，只是myStack.pop()还要删除栈顶的元素。所以上述的解释为啥这两个函数返回的都是2，就是这个原因。一定要理解上述的MyStack类的函数，才能后续更好的写代码。
还有一个队列实现栈的，大家可以自行下去试试手。
做题链接：队列实现栈
?一.队列实现栈
?二.使用两个队列来模拟实现栈
思路讲解：我们使用两个队列来回倒数据，利用队列先进先出的性质，每次等一个队列往另一个队列倒数据还剩下一个时，这便是队列的尾，也就是栈的头了。不清楚？没关系啊，老样子画图理解：
创建好两个栈了，关键就是如何实现栈的功能？ 
这时我们把队列1的前4个数据往队列2里面入数据，然后剩下的5就是栈顶的元素了，直接pop掉即可，因为这符合栈的数据后进先出的规则，出的数据就是队列1剩下的5。
思路还是比较简单的，具体就要看如何写代码：
先大致看一下接口函数：
typedef struct {
} MyStack;
MyStack* myStackCreate() {
}
void myStackPush(MyStack* obj, int x) {
}
int myStackPop(MyStack* obj) {
}
int myStackTop(MyStack* obj) {
}
bool myStackEmpty(MyStack* obj) {
}
void myStackFree(MyStack* obj) {
}?1.栈结构体包含两个队列
typedef struct {//栈结构体包含两个队列
Queue q1;//队列1
Queue q2;//队列2
} MyStack;
?2.创建一个结构体的指针
平常我们写栈和队列的时候，都是定义一个结构体的变量，然后使用传结构体变量的地址，也就是传参的方式，但是今天这个接口函数是使用的返回值的形式，我们要注意。
MyStack* myStackCreate()
{
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));//创建一个结构体的指针
if(obj==NULL)
return NULL;
QueueInit(&obj->q1);//初始化队列1
QueueInit(&obj->q2);//初始化队列2
return obj;//返回结构体的指针
}?3.myStackPush入栈操作
入栈开始我们画图就说了，也就是这里的入队列，第一次两个队列都为空，然后随便往哪个队列入数据即可。
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
//这里是队列1尾非空，那么就是队列1有数据了，那就继续入数据
{
QueuePush(&obj->q1,x);
}
else//这里就是当队列1为空时，那么队列2为空或者不为空，那么都往队列2入数据
{
QueuePush(&obj->q2,x);
}
}?4.myStackPop出队列操作并返回剩下的一个元素，也就是栈顶的元素
这个函数就是开始倒数据了，把一个队列的数据倒到另一个队列里面去，然后队列还剩下一个没倒过去的数据，这个就是栈顶的元素，返回栈顶的元素，然后删除栈顶的元素。
int myStackPop(MyStack* obj)
{
Queue*pEmpty=&obj->q1;//这时我们不知道那个队列是空的，这里我们假设队列1为空
Queue*pNonEmpty=&obj->q2;
if(!QueueEmpty(pEmpty))
{
pEmpty=&obj->q2;//如果我们假设错误，就交换一下即可
pNonEmpty=&obj->q1;
}
while(QueueSize(pNonEmpty)>1)//QueueSize是队列里面的函数，求此时队列元素的个数
{ //这里因为我们需要返回剩下的一个元素，所以循环条件为大于1
QueuePush(pEmpty,QueueFront(pNonEmpty));//把队列头的元素依次往另一个队列里面倒
QueuePop(pNonEmpty);//然后依次pop出这个队列的元素
}
int top=QueueFront(pNonEmpty);//这就是剩下的那个元素
QueuePop(pNonEmpty);
return top;
}?5.myStackTop返回栈顶的元素
这个实现就非常简单了，上面的pop函数其实差不多都已经实现了。
int myStackTop(MyStack* obj)
{
if(!QueueEmpty(&obj->q1))//如果队列1不为空，返回队列尾的元素
return QueueBack(&obj->q1);//也就是剩下的那个元素，也就是栈顶的元素
else
return QueueBack(&obj->q2);
}☘️6.myStackEmpty判断空
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1)//两个队列都为空时，栈也就为空了，所以使用逻辑符且
&&QueueEmpty(&obj->q2);
}?7. myStackFree释放模拟的栈
void myStackFree(MyStack* obj)
{
QueueDestroy(&obj->q1);//销毁队列1和2
QueueDestroy(&obj->q2);
free(obj);//再释放栈的结构体指针
}
?三.完整代码
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* rear;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType x);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
void QueueInit(Queue* q)
{
assert(q);
q->front=NULL;
q->rear = NULL;
q->size=0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc
");
return;
}
newnode->data = x;
newnode->next = NULL;
//当只要一个结点
if (q->rear == NULL)
{
q->rear = q->front = newnode;
}
//当有两个结点的时候
else
{
q->rear->next = newnode;
q->rear = newnode;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->front);
//当只要一个结点时
if (q->front->next == NULL)
{
free(q->front);
q->front = q->rear = NULL;
}
else//当有两个及两个以上的结点的时候
{
Queue* next = q->front->next;
free(q->front);
q->front = NULL;
q->front = next;
}
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->front->data;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL
&& q->rear == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
Queue* next = cur->next;
free(cur);
cur = NULL;
cur = next;
}
q->front = q->rear = NULL;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->rear);
return q->rear->data;
}
typedef struct {//栈结构体包含两个队列
Queue q1;//队列1
Queue q2;//队列2
} MyStack;
MyStack* myStackCreate()
{
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));//创建一个结构体的指针
if(obj==NULL)
return NULL;
QueueInit(&obj->q1);//初始化队列1
QueueInit(&obj->q2);//初始化队列2
return obj;//返回结构体的指针
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
//这里是队列1尾非空，那么就是队列1有数据了，那就继续入数据
{
QueuePush(&obj->q1,x);
}
else//这里就是当队列1为空时，那么队列2为空或者不为空，那么都往队列2入数据
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj)
{
Queue*pEmpty=&obj->q1;//这时我们不知道那个队列是空的，这里我们假设队列1为空
Queue*pNonEmpty=&obj->q2;
if(!QueueEmpty(pEmpty))
{
pEmpty=&obj->q2;//如果我们假设错误，就交换一下即可
pNonEmpty=&obj->q1;
}
while(QueueSize(pNonEmpty)>1)//QueueSize是队列里面的函数，求此时队列元素的个数
{ //这里因为我们需要返回剩下的一个元素，所以循环条件为大于1
QueuePush(pEmpty,QueueFront(pNonEmpty));//把队列头的元素依次往另一个队列里面倒
QueuePop(pNonEmpty);//然后依次pop出这个队列的元素
}
int top=QueueFront(pNonEmpty);//这就是剩下的那个元素
QueuePop(pNonEmpty);
return top;
}
int myStackTop(MyStack* obj)
{
if(!QueueEmpty(&obj->q1))//如果队列1不为空，返回队列尾的元素
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);//销毁队列1和2
QueueDestroy(&obj->q2);
free(obj);//再释放栈的结构体指针
}
站长推荐
- SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述