做个网站好还是做淘宝好,网站打开慢如何优化,pc网站做移动适配,建设网站如何盈利题目描述
题目链接#xff1a;225. 用队列实现栈 - 力扣#xff08;LeetCode#xff09; 题目分析
我们先把之前写的队列实现代码搬过来
用队列实现栈最主要的是实现栈后进先出的特点#xff0c;而队列的特点是先进先出#xff0c;那么我们可以用两个队列来实现
一个队…题目描述
题目链接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);
}
