leetcode：用队列实现栈（后进先出）

题目描述

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

题目分析

我们先把之前写的队列实现代码搬过来

用队列实现栈最主要的是实现栈后进先出的特点，而队列的特点是先进先出，那么我们可以用两个队列来实现

• 一个队列存数据
• 另一个队列在出数据的时候导数据 

具体的接口有下面几个

初始化

我们先创建一个结构体来封装两个队列

初始化两个队列

销毁

我们要分析清楚这个结构，pst存q1,q2两个队列，需要先销毁q1和q2，然后释放pst

入栈

入栈我们入到不为空的队列中去，当q1不为空则入队列q1，否则入队列q2

出栈

出栈的时候就需要导数据了，比如数据都在q1中，q2为空，这时我们先判断空队列是哪一个，然后将非空队列前n-1个数据导入到空队列中，最后留一个数据就是栈顶数据，也是队列的队头数据，可以用QFront接口，先用top保存这个数据，接着pop掉这个数据，返回top

判空

返回栈顶元素

直接取不为空队列的队尾数据

代码示例

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//创建
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//把队列的头尾封装在一个结构体中//初始化
void QInit(Queue* pq);
//销毁
void QDestroy(Queue* pq);//入队列
void QPush(Queue* pq, QDataType x);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//返回队列有效元素个数
int QSize(Queue* pq);//初始化
void QInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
//销毁
void QDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
//入队列
void QPush(Queue* pq, QDataType x)
{assert(pq);//创建newnodeQNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
//出队列
void QPop(Queue* pq)
{assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL){pq->ptail = NULL;//防止ptail成为野指针}pq->size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
//取队尾数据
QDataType QBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
//判空
bool QEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}
//返回队列有效元素个数
int QSize(Queue* pq)
{assert(pq);return pq->size;
}typedef struct MyStack{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QInit(&(pst->q1));QInit(&(pst->q2));return pst;
}void myStackPush(MyStack* obj, int x) {if (!QEmpty(&(obj->q1))){QPush(&(obj->q1), x);}else{QPush(&(obj->q2), x);}
}int myStackPop(MyStack* obj) {Queue* empty = &(obj->q1);Queue* nonempty = &(obj->q2);if (!QEmpty(&(obj->q1))){empty = &(obj->q2);nonempty = &(obj->q1);}while (QSize(nonempty) > 1){QPush(empty, QFront(nonempty));QPop(nonempty);}int top = QFront(nonempty);QPop(nonempty);return top;}int myStackTop(MyStack* obj) {if (!QEmpty(&(obj->q1))){return QBack(&(obj->q1));}else{return QBack(&(obj->q2));}
}bool myStackEmpty(MyStack* obj) {return QEmpty(&(obj->q1)) && QEmpty(&(obj->q2));
}void myStackFree(MyStack* obj) {QDestroy(&(obj->q1));QDestroy(&(obj->q2));free(obj);
}