深圳极速网站建设电话,jimdo做的网站,个人网站的建设目标,上海网站建设工资多少目录 题目#xff1a;
解题#xff1a; 代码讲解#xff1a;
1.构建
2.creat
3.压栈
4.出栈
5.判空
6.释放 题目#xff1a; 请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、top、po…
目录 题目
解题 代码讲解
1.构建
2.creat
3.压栈
4.出栈
5.判空
6.释放 题目 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。
提示
1 x 9最多调用100 次 push、pop、top 和 empty每次调用 pop 和 top 都保证栈不为空 首先要实现队列 队列的实现-CSDN博客 解题 整体思路
利用队列的功能函数实现栈的基本功能。 //Create类似于初始化MyStack* myStackCreate() { //不传参希望你创造一个结构体去初始化再返回MyStack* obj (MyStack*)malloc(sizeof(MyStack)); //开辟空间QueueInit(obj-q1); //-的优先级高于QueueInit(obj-q2); //-的优先级高于return obj;}void myStackPush(MyStack* obj, int x) { //往不为空的入数据if (!QueueEmpty(obj-q1)) //往不为空的队列录入数据{QueuePush(obj-q1, x);}else{QueuePush(obj-q2, x);}}//利用捯元素实现(需要实现删除功能)//错误开辟一块额外的空间只不过存储的是相同的值int myStackPop(MyStack* obj) { //返回Pop的值Q* E_Queue obj-q1; //假设q1是空链表Q* None_E_Queue obj-q2; if (!QueueEmpty(obj-q1)) //肯定一个为空、一个不为空{E_Queue obj-q2;None_E_Queue obj-q1;}while (QueueSize(None_E_Queue) 1) //QueueSize : 元素个数{QueuePush(E_Queue, QueueFront(None_E_Queue)); //将头元素传递QueuePop(None_E_Queue);}QDatetype top QueueFront(None_E_Queue);QueuePop(None_E_Queue);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); //不能只释放objobj只是含有q1 q2两个成员q1 、q2只包含指针只释放该空间本质是释放掉phead 、ptail 、size 三个成员无法释放队列的节点} 代码讲解
1.构建
typedef struct { //第三层嵌套- Q q1; //两个链表 Q q2; } MyStack; 两个队列组成一个栈 2.creat MyStack* myStackCreate() { //不传参希望你创造一个结构体去初始化再返回 MyStack* obj (MyStack*)malloc(sizeof(MyStack)); //开辟空间 QueueInit(obj-q1); //-的优先级高于 QueueInit(obj-q2); //-的优先级高于 return obj; } creat功能可以理解为开辟空间、初始化 3.压栈 void myStackPush(MyStack* obj, int x) { //往不为空的入数据 if (!QueueEmpty(obj-q1)) //往不为空的队列录入数据 { QueuePush(obj-q1, x); } else { QueuePush(obj-q2, x); } } 压栈往不为空的队列Push元素 4.出栈 int myStackPop(MyStack* obj) { //返回Pop的值 Q* E_Queue obj-q1; //假设q1是空链表 Q* None_E_Queue obj-q2; if (!QueueEmpty(obj-q1)) //肯定一个为空、一个不为空 { E_Queue obj-q2; None_E_Queue obj-q1; } while (QueueSize(None_E_Queue) 1) //QueueSize : 元素个数 { QueuePush(E_Queue, QueueFront(None_E_Queue)); //将头元素传递 QueuePop(None_E_Queue); } QDatetype top QueueFront(None_E_Queue); QueuePop(None_E_Queue); return top; } 出栈 需要注意的是当我们需要分情况对两个对象操作的时候如果存在可以进行区分的方法可以采用假设法。
可以先假设q1是空链表。当q1不会空只需更该指针指向。 5.判空 bool myStackEmpty(MyStack* obj) { //判空 return QueueEmpty(obj-q1) QueueEmpty(obj-q2); //只有一个有元素当两者都是空栈才会空 } 进行判空时需要两个都为空stack才会为空 6.释放 void myStackFree(MyStack* obj) { QueueDestroy(obj-q1); QueueDestroy(obj-q2); free(obj); //不能只释放objobj只是含有q1 q2两个成员q1 、q2只包含指针只释放该空间本质是释放掉phead 、ptail 、size 三个成员无法释放队列的节点 } 释放 需要注意的是需要进行两方面的释放1.对队列各个节点的释放在调用队列函数时开辟了节点。 2.对creat函数中malloc的my_stack空间的释放。my_stack只包括两个队列phead、ptail、和size三个元素。
