ledcode【用队列实现栈】

目录

题目描述：

解析题目

 代码解析

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，那么结构体里面的队列还是有指向，不会销毁，这样会造成内存泄漏，如下图所示：