目录
题目描述:
解析题目
代码解析
1.封装一个队列
1.2封装带两个队列的结构体
1.3封装指向队列的结构体
1.4入栈函数实现
1.5出栈函数实现
1.6取栈顶数据
1.7判空函数实现
题目描述:
解析题目
这个题我是用c语言写的,所以队列的push,pop,destroy,empty等常规操作我都写好了,后面我会单独出一个章节,写 队列的实现,这章主要想梳理做题步骤。
队列是先进先出,栈呢是先进后出,所以我们要用两个队列配合使用,让后进去的,先出来,我们可以选择其中一个空队列,讲所有数据一次push入队,然后利用另外一个队列,将这个非空的队列的队头数据,依次如到另一个空的队列,折旧就把最后一个进队的数据保留下来了 这次在pop一下就完成了 题目的要求 最后进的 第一个出来,而且该队列为空了;同时,再接下来,入过有数据,一定要让它入非空队列,然后再执行上述操作,就可以又把最后一个数据单独留在一个队里中,再pop就完成栈的后进先出的操作了。详解图如下所示:
代码解析
1.封装一个队列
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>typedef 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,那么结构体里面的队列还是有指向,不会销毁,这样会造成内存泄漏,如下图所示: