【leetcode】225.用队列实现栈

分析：

队列遵循先入先出的原则，栈遵循后入先出的原则

也就是说，使用队列实现栈时，入队操作正常，但是出队要模拟出栈的操作，我们需要访问的是队尾的元素；题目允许使用两个队列，我们可以先将存有数据的队列中除队尾元素外的所有元素依次出队，存入空队列中，再访问原队列中的队头元素即可

1.使用两个队列构造栈：

C语言中没有定义队列的结构，我们需要自定义队列及其相关操作

如下：结构MyStack由两个队列结构q1和q2构成

为我们创建的栈结构进行动态内存申请并进行初始化

//由两个队列构成栈结构
typedef struct {Queue q1;Queue q2;} MyStack;
//创建栈
MyStack* myStackCreate() {//myStack未具有两个队列的栈结构类型MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//内存开辟失败if(obj == NULL){perror("malloc fail");exit(-1);}//开辟成功，初始化else{QueueInit(&obj->q1);QueueInit(&obj->q2);}return obj;
}

2.压栈操作

模拟栈的压栈操作，数据正常入队即可

📖Note:

我们要将数据插入非空的队列，保证每次都存在一个空队列可以进行数据的存储

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

3.移除并返回栈顶元素

模拟栈的出栈操作：访问并移除的是非空队列的队尾元素

步骤：将存有数据的队列中除队尾元素外的所有元素依次出队，存入空队列中，再访问并移除原队列中的队头元素即可，如下图：

上述操作后，q1和q2的结构如下:

此时，将队列q1中的元素（相当于后入的栈顶元素）先存储，再出队列q1（即清空队列q1，供下次压栈操作使用），返回存储的值即可

int myStackPop(MyStack* obj) {Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(!QueueEmpty(&obj->q1)){nonempty = &obj->q1;	empty = &obj->q2;	}//非空队列前n-1个入空队列并出队，剩下最后一个即为栈顶元素while(QueueSize(nonempty) > 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top = QueueFront(nonempty);QueuePop(nonempty);//清空队列return top;
}

4.返回栈顶元素

栈顶元素即非空队列的队尾数据

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

5.判断是否为空栈 

myStack是由两个队列构成的栈结构，当两个队列都为空时栈即为空

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

6.空间释放

创建栈时为其动态申请了空间，操作结束需要进行空间释放，否则会造成内存泄漏

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

 完整参考代码如下：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;#define bool int
#define true 1
#define false 0//队列初始化
void QueueInit(Queue* pq);
//队列销毁
void QueueDestroy(Queue* pq);
//数据入队
void QueuePush(Queue* pq, QDataType x);
//数据出队
void QueuePop(Queue* pq);
//访问队头数据
QDataType QueueFront(Queue* pq);
//访问队尾数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//求队列的大小
int QueueSize(Queue* pq);//队列初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}
//队列销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->head = pq->tail = NULL;
}
//数据入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;}//空队列时插入if (pq->tail == NULL){pq->head = pq->tail = newnode;}//非空队列时插入else{pq->tail->next = newnode;//链接新元素pq->tail = newnode;//更新队尾}
}
//数据出队
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;pq->head = pq->head->next;free(del);del = NULL;}
}
//访问队头数据
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;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);/*if (pq->tail == pq->head == NULL){return true;}else{return false;}*/return pq->head == NULL && pq->tail == NULL;
}
//求队列的大小
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;
}//由两个队列构成栈结构
typedef struct {Queue q1;Queue q2;} MyStack;
//创建栈
MyStack* myStackCreate() {//myStack未具有两个队列的栈结构类型MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//内存开辟失败if(obj == NULL){perror("malloc fail");exit(-1);}//开辟成功，初始化else{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) {Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(!QueueEmpty(&obj->q1)){nonempty = &obj->q1;	empty = &obj->q2;	}//非空队列前n-1个入空队列并出队，剩下最后一个即为栈顶元素while(QueueSize(nonempty) > 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top = QueueFront(nonempty);QueuePop(nonempty);//清空队列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);
}