温州市住房和城乡建设网站,商城在线,平面设计网站编辑招聘,淘宝客wordpress引流题目一 用队列实现栈
请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、top、pop 和 empty#xff09;。
实现 MyStack 类#xff1a;
void push(int x) 将元素 x 压入栈顶。 int pop() 移除…题目一 用队列实现栈
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的返回 true 否则返回 false 。
注意
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list 列表或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。
来源力扣LeetCode 链接https://leetcode.cn/problems/implement-stack-using-queues 我们先来分析下题目
要求用两个队列实现一个栈 并且实现四种操作
我们来看第一个Push操作
栈的特点是什么 先进后出
队列的特点是什么 先进先出
来看图 有思路了
图上是两个队列
我们假设 注意啊 是假设
第一行的图 它就是一个栈
那么我们可以判断出 它的数据插入顺序就是 1 2 3 4
这个时候队列的头就是栈的尾
如果我们这个时候需要删除栈的头数据应该怎么办呢
我们都知道队列的数据只能是从头开始出
也就是说 比如要将队列前面的1 2 3 全部出完之后才能开始出 4
但是我们不可能会抛弃之前的数据啊
这个时候我们就想到了第二个队列的用处了
只需要将我Pop的数据使用第二个队列来接受就可以
实现起来的图大概是这样子 这个时候我们就能删除掉头数据了
如果需要再删除一个怎么办呢
那么只需要将上面的操作再重复一次就好了
这个时候的插入数据只需要往不为空的队列插入数据就可以了
要求首元素就是返回队列的尾
要求尾元素就是返回队列的头
也就是两个步骤
1.保持一个队列为空一个队列存数据
2.出栈把前面的数据倒入空队列
接下来我们来实现代码
把所有的队列代码以及接口函数拷贝进去
第一步 定义结构体
我们来看这个 我们应该怎么定义我们的Stack结构体呢
既然是两个队列的实现的
那么是不是可以放两个队列的结构在里面
仔细一想好像可行
我们来试试
typedef struct {Queue q1;Queue q2;
} MyStack;
画个图方便大家理解 三个结构体的关系一目了然 第二步 实现创建初始化
MyStack* myStackCreate() {MyStack*pst ( MyStack*)malloc(sizeof( MyStack));if(pstNULL){perror(malloc fail);return NULL;}QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}
第三步 插入数据
这里要判断队列是否为空不为空就插入数据两个都为空就随机一个队列插入数据
看代码
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}
第四步 删除数据
这是最难的部分需要我们倒数据
我们先写出两个指针来判断空和非空
如果说我们的判断不正确的话 那么我们就将这两个指针翻转一下就好了
代码整体表现不变
int myStackPop(MyStack* obj) {Queue*emptyQ obj-q1;Queue*nonemptyQ obj-q2;if(!QueueEmpty(obj-q1)){emptyQ obj-q2;nonemptyQobj-q1;}//倒数据while(QueueSize(nonemptyQ)1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}//记录删除值 删掉int top QueueFront(nonemptyQ);QueuePop(nonemptyQ);return top;
}
第五步 返回头的值
这里我们可以分两种情况讨论
如果1不为空就返回1的尾值
如果2不为空就返回2的尾值
int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}
第六步 判空
这步就很简单只需要判断1和2是否都为空都为空即空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1)QueueEmpty(obj-q2);
}
第七步 释放
这里要依次释放销毁类似套娃
void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
} 源码
typedef int QDateType;
typedef struct QueueNode
{struct QueueNode* next;QDateType date;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//队进
void QueuePush(Queue* pq, QDateType x);
//队出
void QueuePop(Queue* pq);
//判断为空
bool QueueEmpty(Queue* pq);
//个数
int QueueSize(Queue* pq);
//队尾
QDateType QueueBack(Queue* pq);
//对头
QDateType QueueFront(Queue* pq);
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//两个结构体依次销毁 先销毁QNodeQNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}//再置空Queuepq-head pq-tail NULL;pq-size 0;
}
//队进
void QueuePush(Queue* pq, QDateType x)
{assert(pq);//开辟新节点QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}//赋值newnode-next NULL;newnode-date x;//判断是否为空if (pq-head NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}//个数要pq-size;
}
//队出
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head!NULL);//只有一个节点if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{//保存下一位QNode* next pq-head-next;free(pq-head);pq-head next;//迭代}//个数要--pq-size--;
}
//判断为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
//大小
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
//队尾
QDateType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-date;
}
//对头
QDateType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-date;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack*pst ( MyStack*)malloc(sizeof( MyStack));if(pstNULL){perror(malloc fail);return NULL;}QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}int myStackPop(MyStack* obj) {Queue*emptyQ obj-q1;Queue*nonemptyQ obj-q2;if(!QueueEmpty(obj-q1)){emptyQ obj-q2;nonemptyQobj-q1;}//倒数据while(QueueSize(nonemptyQ)1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}//记录删除值 删掉int top QueueFront(nonemptyQ);QueuePop(nonemptyQ);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) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}
以上便是本文所有内容了如有错误请各位大佬不吝赐教感谢留言
