力扣 225 用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
思路分析
关于栈的功能，见于是基础的数据结构，且如果知道队列的功能也一定会知道栈的功能，这里不过多赘述，直接上思路
基于栈后进先出，而队列先进先出的特点，我们可以定义两个队列，
这里先描述出栈的实现，假设一个队列里已经放好了值，为1，2，3，4，按照队列出队的话，先取到1，但如果出栈的话，就需要取到4，这里另外一个队列就派上用场了，我们可以将队尾前的所有元素出队，并进入到另一个队列里，最后剩下的就是需要出栈的元素，此时我们在去原队列的队头元素即可。
接下来到入栈的实现，关键在于应该入哪个队，如果两队为空，随便一个，但接下来的话如果要方便上述出栈的实现，我们就需要入队到不为空的队列。
紧接着是返回栈顶元素，我们已经知道，队尾就是我们出栈的元素，所以这里直接返回队列的队尾元素即可。
判断栈为空，直接检测两个队列是否同时为空即可。
力扣不提供队列的实现代码，我们需要自己实现
完整代码
队列的实现代码
代码语言：javascript复制typedef int QueueDataType;
typedef struct QuNode
{
QueueDataType data;
struct QuNode* next;
}QuNode;
typedef struct Queue
{
QuNode* phead;
QuNode* ptail;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
//打印队列
void QueuePrint(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->phead = NULL;
q->ptail = NULL;
q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{
assert(q);
//创建结点
QuNode* newnode = (QuNode*)malloc(sizeof(QuNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = data;
newnode->next = NULL;
//插入
if (q->ptail == NULL)
{
q->phead = q->ptail = newnode;
}
else
{
q->ptail->next = newnode;
q->ptail = newnode;
}
q->size ;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->phead);
QuNode* del = q->phead;
q->phead = q->phead->next;
free(del);
del = NULL;
if (q->phead == NULL)
{
q->ptail = NULL;
}
q->size--;
}
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
assert(q);
assert(q->phead);
return q->phead->data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{
assert(q);
assert(q->ptail);
return q->ptail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
if (q->phead == NULL)
{
return 1;
}
else
{
return 0;
}
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QuNode* cur = q->phead;
while (cur)
{
QuNode* next = cur->next;
free(cur);
cur = next;
}
q->phead = q->ptail = NULL;
q->size = 0;
}
//打印队列
void QueuePrint(Queue* q)
{
assert(q);
QuNode* cur = q->phead;
while (cur->next!=NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
}实现代码
代码语言：javascript复制typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* pst=(MyStack*)malloc(sizeof(MyStack));//动态创建栈
QueueInit(&pst->q1);//栈初始化
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* pst, int x) {
if(QueueEmpty(&pst->q1))//找出不为空的队列将元素入队
{
QueuePush(&pst->q2,x);
}
else
{
QueuePush(&pst->q1,x);
}
}
int myStackPop(MyStack* pst) {
Queue* empty=&pst->q1;//假设法，假设q1为空，后面再判断一下结果，不对再反过来
Queue* noneempty=&pst->q2;
if(QueueEmpty(&pst->q2))
{
empty=&pst->q2;
noneempty=&pst->q1;
}
while(QueueSize(noneempty)>1)//将出栈元素前的所有元素出队，进入到空队列中
{
QueuePush(empty,QueueFront(noneempty));
QueuePop(noneempty);
}
int top=QueueFront(noneempty);//取到出栈元素
QueuePop(noneempty);
return top;
}
int myStackTop(MyStack* pst) {
if(QueueEmpty(&pst->q1))//返回不为空队列的队尾元素
{
return QueueBack(&pst->q2);
}
else
{
return QueueBack(&pst->q1);
}
}
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;
}
