网站推广制作教程,php网站开发技术期末题库,网站技术开发设计,wordpress文章页横幅目录
题目描述#xff1a;
解析题目 代码解析
1.封装一个队列
1.2封装带两个队列的结构体
1.3封装指向队列的结构体
1.4入栈函数实现
1.5出栈函数实现
1.6取栈顶数据
1.7判空函数实现 题目描述#xff1a; 解析题目
这个题我是用c语言写的#xff0c;所以队列的pu…目录
题目描述
解析题目 代码解析
1.封装一个队列
1.2封装带两个队列的结构体
1.3封装指向队列的结构体
1.4入栈函数实现
1.5出栈函数实现
1.6取栈顶数据
1.7判空函数实现 题目描述 解析题目
这个题我是用c语言写的所以队列的pushpopdestroyempty等常规操作我都写好了后面我会单独出一个章节写 队列的实现这章主要想梳理做题步骤。
队列是先进先出栈呢是先进后出所以我们要用两个队列配合使用让后进去的先出来我们可以选择其中一个空队列讲所有数据一次push入队然后利用另外一个队列将这个非空的队列的队头数据依次如到另一个空的队列折旧就把最后一个进队的数据保留下来了 这次在pop一下就完成了 题目的要求 最后进的 第一个出来而且该队列为空了同时再接下来入过有数据一定要让它入非空队列然后再执行上述操作就可以又把最后一个数据单独留在一个队里中再pop就完成栈的后进先出的操作了。详解图如下所示 代码解析 1.封装一个队列
#includestdio.h
#includeassert.h
#includestdbool.h
#includestdlib.htypedef int QDataType;
//定义节点
typedef struct QueueNode
{QDataType data;struct QueueNode* next;}QNode;
//定义指向头和尾的指针
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq)
{pq-head pq-tail NULL;pq-size 0;}
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode *cur pq-head;while (cur){QNode* next cur-next; free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;}
QNode* BuyQNode(QDataType x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc:fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
//进队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode BuyQNode(x);if (pq-head NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL pq-tail NULL;}
//出队
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* del pq-head;//结构体成员head 是QNode 类型指针pq-head pq-head-next;free(del);}pq-size--;}
//队头
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;} //队尾
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;}//个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
1.2封装带两个队列的结构体
因为是用ledecode写的代码所以写的代码都按照他给定的封装结构编写具体代码如下
//两个队列封装在一个结构体中 重定义为 Mystack
typedef struct {Queue q1;Queue q2;
} MyStack;1.3封装指向队列的结构体
题目中已经给了接口函数我们只能在接口函数内部完成要求具体代码如下
MyStack* myStackCreate() {MyStack *obj ( MyStack *)malloc(sizeof(MyStack));//定义一个结构体指针变量QueueInit(obj-q1);//初始化QueueInit(obj-q2);return obj;}
因为题目给是返回的是mystack*结构指针变量所以 函数内部我们定义一个指针变量用来接收在堆上申请的同类型的空间地址这样虽然出了子程序后变量obj会被释放但是地址我们已经返回并且堆上的空间已经被返回我们可以通过地址访问这块空间。
1.4入栈函数实现
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}}
这个就很简单如果队列1为空就把数据入队反之入队列2。
1.5出栈函数实现
int myStackPop(MyStack* obj) {
//写一个判断队列1和队列2谁为空的代码Queue *emptyQueue obj-q1; //定义一个指针变量 emptyQueue,就要取出obj-q1的地址来匹配Queue *noemptyQueue obj-q2;if(!QueueEmpty(obj-q1)){noemptyQueue obj-q1;emptyQueue obj-q2;}
//将不为空的队列除了最后一个数据其他数据都入到另一个空队中while(QueueSize(noemptyQueue)1){QueuePush(emptyQueue,QueueFront(noemptyQueue));//取队头数据依次如另一个队中QueuePop(noemptyQueue);//出一个数据要pop一下}int top QueueFront(noemptyQueue);//因为要返回 栈的数据所以用一个整形变量接收QueuePop(noemptyQueue);return top;
} 用两个结构体指针变量接收队列1 和2 判断出他们中为不空的队列然后依次入空的队列保留最后一个数据取出返回就完成啦每个代码的解析我都写出来了。
1.6取栈顶数据
int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
} 就是将不为空的队列的队尾数据返回就行。
1.7判空函数实现
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2);} 表达式 的意思是 两个队列同时为空 才为真 返回true 否则返回false
1.8销毁函数实现
void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);}
我们需要先将队列1和队列2 销毁再将0bj这个指针变量置空如果直接置空obj那么结构体里面的队列还是有指向不会销毁这样会造成内存泄漏如下图所示
