leetcode：225. 用队列实现栈

一、题目

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

函数原型：

typedef struct { 

} MyStack;

MyStack* myStackCreate() 

void myStackPush(MyStack* obj, int x) 

int myStackPop(MyStack* obj) 

int myStackTop(MyStack* obj) 

bool myStackEmpty(MyStack* obj) 

void myStackFree(MyStack* obj) 

二、思路

利用队列实现栈：

1.我的栈的结构

“我的栈”是一个结构体，存放两个队列即可

2.我的栈创建及其初始化

函数返回值是“我的栈”结构体指针，动态申请一个“我的栈”大小内存空间，然后初始化“我的栈”结构体中中的两个队列，最后返回“我的栈”的结构体指针

3.我的栈入栈

“我的栈”中有两个队列，选择一个空队列进行存储数据。由于栈的入栈和队列的入队都是从尾部进行存储数据的，所以直接对空队列进行入队操作即可。

如何找到空队列？

利用假设法，假设q1为空队列，q2为非空队列；判断q1是否为空，如果不为空，则将空队列设为q2，非空队列设为q1.

4.我的栈出栈

由于栈删除元素是从栈顶删除，而队列删除元素是从队头删除，所以需要先将非空队列中的前n-1个元素出队并入队到空队列中，第n个元素直接出队无需入队。即可完成“我的栈”的出栈。

5.我的栈取栈顶元素

取栈顶元素是在栈尾部进行的，所以可以对非空队列的取队尾元素。

6.我的栈判空

只要对两个队列判空即可，只有当两个队列都为空时，“我的栈”才判断为空。

7.我的栈销毁

首先对“我的栈”中两个队列进行队列销毁，然后再对动态申请的“我的栈”空间进行动态内存释放。

三、代码

typedef int QDataType;//队列的结构定义
typedef struct QueueNode{QDataType val;struct QueueNode *next;
}QNode;//用结构体管理队列
typedef struct Queue{QNode* phead;QNode* ptail;int size;
}Queue;//队列的初始化
void QueueInit(Queue* pq)
{pq->phead=NULL;pq->ptail=NULL;pq->size=0;
}//入队
void QueuePush(Queue *pq,QDataType x)
{assert(pq);QNode *newnode=(QNode*)malloc(sizeof(QNode));if(newnode==NULL){perror("malloc fail");exit(-1);}newnode->val=x;newnode->next=NULL;if(pq->phead==NULL)//队列为空pq->phead=pq->ptail=newnode;else{pq->ptail->next=newnode;pq->ptail=newnode;}pq->size++;
}//出队
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);//空队列if(pq->phead==pq->ptail){pq->ptail=NULL;}QNode* tmp=pq->phead;pq->phead=tmp->next;free(tmp);tmp=NULL;pq->size--;
}//取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}//取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}//判空
bool QueueEmpty(Queue *pq)
{assert(pq);return pq->phead==NULL;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode *cur=pq->phead;while(cur){QNode* tmp=cur;cur=cur->next;free(tmp);tmp=NULL;}pq->phead=pq->ptail=NULL;pq->size=0;
}typedef struct {Queue q1;Queue q2;
} MyStack;//我的栈创建及其初始化
MyStack* myStackCreate() {MyStack *ps=(MyStack*)malloc(sizeof(MyStack));QueueInit(&ps->q1);QueueInit(&ps->q2);return ps;
}void myStackPush(MyStack* obj, int x) {//利用假设法Queue *empty=&obj->q1;Queue *noneempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noneempty=&obj->q1;}QueuePush(noneempty,x);//QueuePush(&obj->q1,x);
}//我的栈-出栈
int myStackPop(MyStack* obj) {// while(obj->q1.size>1)// {//     QueuePush(&obj->q2,QueueFront(&obj->q1));//     QueuePop(&obj->q1);//     //QueuePush(&obj->q2,QueuePop(&obj->q1));// }// int stackpop=QueueFront(&obj->q1);// QueuePop(&obj->q1);// while(obj->q2.size)// {//     QueuePush(&obj->q1,QueueFront(&obj->q2));//     QueuePop(&obj->q2);//     //QueuePush(&obj->q1,QueuePop(&obj->q2));// }// return stackpop;//利用假设法Queue *empty=&obj->q1;Queue *noneempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noneempty=&obj->q1;}while(noneempty->size>1){QueuePush(empty,QueueFront(noneempty));QueuePop(noneempty);}int stackpop=QueueFront(noneempty);QueuePop(noneempty);return stackpop;
}//我的栈-出栈
int myStackTop(MyStack* obj) {Queue* empty=&obj->q1;Queue* noneempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noneempty=&obj->q1;}return QueueBack(noneempty);
}//我的栈-判空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}//我的栈-销毁
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}/*** 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);
*/