当前位置：网站首页>用队列实现栈

用队列实现栈

2022-07-15 08:33:00 【染指流年灬】

之前面试一直不刷题，因为感觉工作中用不到，为了卷而卷，这是有点知名度的力扣面试题，学撤销重做的时候想起，之前的面试中被问过两三次了，紧张了，几分钟都构思不到， 有点兴趣还是记录一下。

题目

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空

思路

我们用两个队列A、B来模拟栈，这里将A看作是栈，B看作是实现栈操作所需的临时队列。

  1. 入栈：直接将元素添加进队列

  2. 出栈：将A队列中队尾元素以外的都挪到B队列中，使得栈顶元素能够被取出。然后再将A的末尾元素"出栈"。 然后，将AB的引用交换， 这样A更新之后的内容看起来就像出栈。

在这里插入图片描述

  1. 返回栈顶元素：和出栈同理，只是在返回A的末尾元素后， A的末尾元素也得进入B队列。

  2. 判断栈是否为空：如果AB同时为空，则为空栈。

原网站

版权声明
本文为[染指流年灬]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43149049/article/details/125782164

边栏推荐

猜你喜欢

随机推荐