力扣刷题 -- 225. 用队列实现栈

1. 题目

 2. 思路分析

思路：1)往非空队列里插入数据（入队列）；

2）将非空队列的前size-1个元素挪到空队列；

3）将非空队列的队尾元素出队列，并返回栈顶元素。

3. 代码实现 

typedef int QDataType;
typedef struct QueueNode {QDataType data;struct QueueNode* next;
} QueueNode;typedef struct Queue {QueueNode* phead;QueueNode* ptail;int size;
} Queue;// 初始化
void QueueInit(Queue* pq) {assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
// 销毁
void QueueDestory(Queue* pq) {assert(pq);QueueNode* pcur = pq->phead;while (pcur) {QueueNode* next = pcur->next;free(pcur);// pcur = NULL;pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
// 队列判空
bool QueueEmpty(Queue* pq) {assert(pq);return pq->phead == NULL;
}
// 入队列
void QueuePush(Queue* pq, QDataType x) {assert(pq);// 申请新的结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL) {perror("malloc fail!\n");exit(1);}newnode->data = x;newnode->next = NULL;// 空队列if (pq->phead == NULL) {pq->phead = pq->ptail = newnode;} else {pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}
// 队列有效元素个数
int QueueSize(Queue* pq) {assert(pq);// QueueNode* pcur = pq->phead;// int size = 0;// while (pcur)//{//	pcur = pcur->next;//	size++;// }// return size;return pq->size;
}
// 出队列
void QueuePop(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));// 只有一个结点时if (pq->phead == pq->ptail) {free(pq->phead);pq->phead = pq->ptail = NULL;} else {QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}
// 取队头元素
QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
// 取队尾元素
QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
//这里是队列结构和相关方法/typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pa=(MyStack*)malloc(sizeof(MyStack));QueueInit(&pa->q1);QueueInit(&pa->q2);return pa;
}
//将元素 x 压入栈顶
void myStackPush(MyStack* obj, int x) {//往非空队列插入数据--判空if(QueueEmpty(&obj->q1)){QueuePush(&obj->q2,x);}else{QueuePush(&obj->q1,x);}
}
//移除并返回栈顶元素
int myStackPop(MyStack* obj) {Queue* emp=&obj->q1;Queue* noemp=&obj->q2;if(QueueEmpty(&obj->q2)){noemp=&obj->q1;emp=&obj->q2;}while(QueueSize(noemp)>1){QueuePush(emp,QueueFront(noemp));QueuePop(noemp);}int top=QueueFront(noemp);QueuePop(noemp);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) {QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);obj=NULL;
}