今日写题work05

题目：用队列实现栈

思路

队列的特点是先进先出，而栈的特点是后进先出。所以想要用队列实现模拟栈，我们可以使用两个队列，一个队列负责压栈，一个队列负责出栈。压栈很简单就是检空再调用队列的push就好，那出栈呢？这里可以利用另外一个空队列，先把一部分数据给空队列，原来的队列只保留最后一个数据就好，这时再对这个队列出栈，再Pop掉。始终保持一个队列有数据，一个队列为空。两个队列相互交换数据，达到模拟实现栈的效果。

这里的结构实际就是一个套娃，栈包含队列，队列里包含链表

具体实现

首先手搓一个队列，如果是其他语言也可以直接调用库，这里是用c语言。接着实现题目给的函数。

myStackCreate

MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst==NULL){perror("Malloc Failed\n");return NULL;}QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}

这里创建栈要想清楚结构，有三层，其中两层你已经再队列里完成。所以，这里我们还需要再创建一个栈，动态开辟一个指针，用这个指针来维护栈和实现各种功能

myStackPush

void myStackPush(MyStack* obj, int x) {if(!(QueueEmpty(&obj->q1))){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}

这里压栈还是比较简单，首先检查一下队列是否为空，如果为空就入队另一个队列。当然刚开始入队，两个都为空。所以在检查完一个队列为空后，直接就入队到另一个队列就行了。不用再多余判断了。

myStackPop

int myStackPop(MyStack* obj) {Queue* empty=&obj->q1;Queue* nonempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;nonempty=&obj->q1;}while(QueueSize(nonempty) > 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int ret=QueueFront(nonempty);QueuePop(nonempty);return ret;
}

这里出栈是有点复杂，设计到两个队列相互转化。所以，为了逻辑清晰。我们直接创建两个新队列，分别命名为empty和nonempty。这样容易区分，不容易逻辑混乱。

这里我们可以直接选择一个队列赋值给empty，另一个队列赋值给nonempty。在进行检空，如果不对，在进行交换就行。接下来就是依次出队，把头部元素依次入队到empty,依次Pop nonempty队列。当只剩一个数据，循环停止。退出循环后，把剩余的数据出队，Pop队列，返回。这样就实现了后进先出的效果。

myStackTop

int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

这里可以检空再调用QueueBack，这里也把这个函数体现的淋漓尽致。虽然，从队列定义看，这个函数是不合理的。但是这个函数，再很多地方都会用到。所以我们不妨写一下。c++STL中就也有这个函数。

myStackEmpty

bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

这里返回的是两个队列的检空，因为这个栈是由这两两个队列实现的

myStackFree

void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj=NULL;
}

这里释放，可不能直接free栈。我们这里队列还需要一个一个释放。如果你直接释放掉栈，那就会内存泄漏。所以我们先调用下队列的销毁函数把两个队列释放掉,再free栈，最后记得置空

代码

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列头部yuansu
QDataType QueueFront(Queue* pq);
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
//获取队列中有效数据个数
int QueueSize(Queue* pq);
//检测队列是否为空（检空）
bool QueueEmpty(Queue* pq);
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;
}
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("Malloc Failed\n");return;}newnode->next = NULL;newnode->data = x;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);/*QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}*/if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}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;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst==NULL){perror("Malloc Failed\n");return NULL;}QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!(QueueEmpty(&obj->q1))){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* empty=&obj->q1;Queue* nonempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;nonempty=&obj->q1;}while(QueueSize(nonempty) > 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int ret=QueueFront(nonempty);QueuePop(nonempty);return ret;
}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);obj=NULL;
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

总结

这里复杂的主要是结构，在具体的函数实现上，如果你思路清晰，其实是比较简单的。比较复杂的就是，出栈这个函数，需要多想一下

题目链接：225. 用队列实现栈 - 力扣（LeetCode）