制作图片的免费网站,海南专业网站开发公司,友汇网网站建设管理后台设置,微网站 下载255.用队列实现栈
不出意外大概率这几天都会更新 leetcode#xff0c;如果没有做新的题#xff0c;大概就会把 leetcode 之前写过的题整理#xff08;单链表的题目居多一点#xff09;出来写成博客
今天讲的题蛮容易出错的#xff08;注意传参啊#xff0c;最好把队列的…255.用队列实现栈
不出意外大概率这几天都会更新 leetcode如果没有做新的题大概就会把 leetcode 之前写过的题整理单链表的题目居多一点出来写成博客
今天讲的题蛮容易出错的注意传参啊最好把队列的实现写过一遍写起来就容易一点 题目 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。 实现 MyStack 类 void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 题目链接 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 文字 和 画图 分析 首先思考一下 栈 和 队列 两者之间 的区别 栈先进后出用数组实现 队列先进先出用链表实现 栈 队列 2. 最大的问题就是 出元素 明显一个队列我们不好模拟出栈这里我们就要借助 两个队列去实现 栈是出 存进去的最后一个元素而队列是出 存进去的第 一 个元素要想两者对等即第一个元素也就是最后 一个元素 我们把存放所有元素的那一个队列除了最后一个元素 其它的元素都移到没有存放元素的那一个队列这样就做 到第一个元素也就是最后一个元素 3. 存入元素 这里我们需要确保其中一个队列始终为空有利于后面的 出元素另一个队列专门存入元素由于后续的出元素 导致我们无法确保哪一个队列存元素哪一个队列为空 如果 q1存元素进行一次出元素之后它就为空了 这里我们用了一个方法再定义两个指针 nonEmpty 和 Empty用来存放 两个队列 的地址开始nonEmpty存放 q1的地址Empty存放q2的地址判断 q1是否为空如 果为空nonEmpty存放q2的地址Empty存放q1的地址 也可以用 if ,else语句直接判断 代码
typedef int QLType;
typedef struct QueueNode
{QLType val;struct QueueNode* next;
}QN;//创建节点
typedef struct QueueList
{QN* head;QN* tail;int size;
}QL;//创建队列
void QNInit(QL* pphead)
{pphead-head pphead-tail NULL;pphead-size 0;
}//队列初始化
QLType QLTop(QL* pphead)
{return pphead-head-val;
}//返回列队的头节点元素
QLType QLtail(QL* pphead)
{return pphead-tail-val;
}//返回列队的尾节点元素
int QLSize(QL* pphead)
{return pphead-size;
}//返回队列里面有效元素个数
bool QLEmpty(QL* pphead)
{return pphead-head NULL;
}//判断队列是否为空
void QNPop(QL* pphead)
{QN* cur pphead-head;pphead-head pphead-head-next;free(cur);pphead-size--;
}//出队列存储的第一个元素
void QNPush(QL* pphead, QLType x)
{QN* newnode (QN*)malloc(sizeof(QN));newnode-next NULL;newnode-val x;if (newnode NULL){perror(malloc);return;}if (QLEmpty(pphead)){pphead-head pphead-tail newnode;}else{pphead-tail-next newnode;pphead-tail newnode;}pphead-size;
}//存入队列元素//以上都是服务队列的创建typedef struct
{QL q1;QL q2;
}MyStack//存放两个队列MyStack* myStackCreate()
{MyStack* obj (MyStack*)malloc(sizeof(MyStack));QNInit(obj-q1);QNInit(obj-q2);return obj;
} //两个队列的初始化void myStackPush(MyStack* obj, int x)
{if(!QLEmpty(obj-q1)){QNPush(obj-q1, x);}else{QNPush(obj-q2, x);}
}//存放元素int myStackPop(MyStack* obj)
{QL *nonEmpty obj-q1;QL *Empty obj-q2;if(QLEmpty(obj-q1)){nonEmpty obj-q2;Empty obj-q1;}while(QLSize(nonEmpty) 1){QNPush(Empty, QLTop(nonEmpty));QNPop(nonEmpty);}int top QLTop(nonEmpty);QNPop(nonEmpty);return top;
}//出元素int myStackTop(MyStack* obj)
{if(!QLEmpty(obj-q1)){return QLtail(obj-q1);}else{return QLtail(obj-q2);}
}//返回栈顶元素bool myStackEmpty(MyStack* obj)
{return QLEmpty(obj-q1) QLEmpty(obj-q2);
}//判断两个栈是否都为空void myStackFree(MyStack* obj)
{free(obj);
}//销毁空间
