朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode--225.用队列实现栈
数 据 结 构 专 栏:数据结构
个 人 主 页 :stackY、
LeetCode 专 栏 :LeetCode刷题训练营
LeetCode--225.用队列实现栈:https://leetcode.cn/problems/implement-stack-using-queues/
目录
1.题目介绍
2.实例演示
3.解题思路
3.1创建栈
3.2出栈操作
3.3压栈操作
3.4获取栈顶元素
3.5判断栈是否为空
3.6释放栈
4.完整代码
1.题目介绍
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
1. void push(int x) 将元素 x 压入栈顶。
2. int pop() 移除并返回栈顶元素。
3. int top() 返回栈顶元素。
4. boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。注意:
1. 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
2. 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
2.实例演示
3.解题思路
3.1创建栈
使用两个队列来实现栈的功能,首先我们得写出一个队列,队列的功能是先进先出,栈的功能是后进先出,在创建栈的时候需要有两个队列,然后为栈创建一块空间,并且将两个队列都进行初始化:
代码演示:
typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { //先为栈创建一块空间 MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); if(obj == NULL) { perror("malloc fail"); return NULL; } //分别对两个队列进行初始化 QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; }
3.2出栈操作
题目要求删除之后返回栈顶的元素。
栈的功能是先入后出,然而队列的功能是先入先出,那么我们该怎么操作呢?我们现在有两个队列,出栈是出的最后一个数据(第n个数据),我们可以先将一个队列的前n-1个数据依次插入到另外一个队列中(每插入一个然后再删除一个),这时原来的队列中就剩下最后一个数据,这时再将最后一个数据删除,这样子就达成了出栈时出最后一个数据的操作:我们在这里先假设第一个队列为空,第二个队列不为空,然后进行判断,如果不符合就交换,然后就是导数据的过程,然后就可以进行删除了:
代码演示:
int myStackPop(MyStack* obj) { //假设q1为空 //q2不为空 Queue* pEmptyQ = &obj->q1; Queue* pNoEmptyQ = &obj->q2; //判断是否正确,不正确则交换 if(!QueueEmpty(&obj->q1)) { pEmptyQ = &obj->q2; pNoEmptyQ = &obj->q1; } //导数据 //一直取到第Size-1个,这时就剩下的最后一个数据 while(QueueSize(pNoEmptyQ) > 1) { //将不为空的队列中的数据插入到为空的队列 QueuePush(pEmptyQ, QueueFront(pNoEmptyQ)); QueuePop(pNoEmptyQ); } //删除最后一个数据 int top = QueueFront(pNoEmptyQ); QueuePop(pNoEmptyQ); return top; }
3.3压栈操作
由于我们是用两个队列来实现栈的功能,所以压栈操作也就是插入数据的操作需要将数据插入到队列中,那么怎么插入呢?对应前面的删除,我们需要将数据插入到不为空的队列中,那么第一次插入的时候两个队列都为空,这时随便插入即可:
代码演示:
void myStackPush(MyStack* obj, int x) { //判断是否为空 if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } }
3.4获取栈顶元素
这里的栈顶的元素就表示的是不为空的队列中的队尾的数据,所以只需要将不为空的队列的队尾的数据直接返回:
代码实现:文章来源:https://www.toymoban.com/news/detail-461428.html
int myStackTop(MyStack* obj) { //q1不为空返回q1的队尾数据 if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } //q2不为空返回q2的队尾数据 else { return QueueBack(&obj->q2); } }
3.5判断栈是否为空
判断栈是否为空就是判断两个队列是否为空:
代码演示:
bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); }
3.6释放栈
对栈的释放我们先要销毁实现栈的两个队列,然后再将栈空间释放:
代码实现:
void myStackFree(MyStack* obj) { //先销毁两个队列 QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); //再释放栈空间 free(obj); }
4.完整代码
//链式结构:表示队列 typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; //队列的结构 typedef struct Queue { //头指针 QNode* phead; //尾指针 QNode* ptail; //队列中有效元素个数 int size; }Queue; //初始化队列 void QueueInit(Queue* pq); //销毁队列 void QueueDestroy(Queue* pq); //队尾入队列 void QueuePush(Queue* pq, QDataType x); //检测队列是否为空 bool QueueEmpty(Queue* pq); //对头出队列 void QueuePop(Queue* pq); //获取队头的元素 QDataType QueueFront(Queue* pq); //获取队尾的元素 QDataType QueueBack(Queue* pq); //获取队列有效元素的个数 int QueueSize(Queue* pq); //初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail= NULL; pq->size = 0; } //销毁队列 void QueueDestroy(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 QueuePush(Queue* pq, QDataType x) { assert(pq); //创建新的结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->next = NULL; newnode->data = x; //第一次尾插 if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } //有效元素++ pq->size++; } //检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); //1.判断头、尾指针 /* return pq->phead == NULL && pq->ptail == NULL; */ //2.判断有效元素个数 return pq->size == 0; } //队头出队列 void QueuePop(Queue* pq) { assert(pq); //判空 assert(!QueueEmpty(pq)); //一个结点 if (pq->phead->next == NULL) { //直接释放 free(pq->phead); pq->phead = pq->ptail = NULL; } //多个结点 else { //记录头的下一个 QNode* 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; } //获取队列有效元素的个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { //先为栈创建一块空间 MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); if(obj == NULL) { perror("malloc fail"); return NULL; } //分别对两个队列进行初始化 QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { //判断是否为空 if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj) { //假设q1为空 //q2不为空 Queue* pEmptyQ = &obj->q1; Queue* pNoEmptyQ = &obj->q2; //判断是否正确,不正确则交换 if(!QueueEmpty(&obj->q1)) { pEmptyQ = &obj->q2; pNoEmptyQ = &obj->q1; } //导数据 //一直取到第Size-1个,这时就剩下的最后一个数据 while(QueueSize(pNoEmptyQ) > 1) { //将不为空的队列中的数据插入到为空的队列 QueuePush(pEmptyQ, QueueFront(pNoEmptyQ)); QueuePop(pNoEmptyQ); } //删除最后一个数据 int top = QueueFront(pNoEmptyQ); QueuePop(pNoEmptyQ); return top; } int myStackTop(MyStack* obj) { //q1不为空返回q1的队尾数据 if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } //q2不为空返回q2的队尾数据 else { return QueueBack(&obj->q2); } } 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); */
今天的博客就分享到这里,喜欢的老铁留下你的三连,感谢感谢!我们下期再见!!文章来源地址https://www.toymoban.com/news/detail-461428.html
到了这里,关于栈和队列OJ题:LeetCode--225.用队列实现栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!