题解43 | 好吧其实一个也行#两个队列实现栈#

两个队列实现栈

https://www.nowcoder.com/practice/9fc5ae0e203f4d079b68dee34818832a

#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param order string字符串vector 
     * @return string字符串vector
     */
    queue<int>q1;//一个队列也能实现栈
    queue<int>q2;//q2:???你创立我干嘛

    void push(int element){
        q1.push(element);
    } //等价于将元素 element 压入栈顶。

    int pop(){
        int s = q1.size();
        s--;
        while (s--) {
            q1.push(q1.front());
            q1.pop();
        }
        int f = q1.front();
        q1.pop();
        return f;
    } //循环移动并返回队列尾(栈顶)元素

    int top(){
        return q1.back();
    } //返队列回栈顶元素。
    
    bool empty() {
        return q1.empty();
    }//如果队列栈是空的,返回 true ;否则,返回 false 。
};

算法基本思想:

使用两个队列q1和q2来实现栈的功能。push操作直接将元素压入q1队列中。pop操作需要将q1队列中的元素移动到q2队列中,直到q1队列中只剩下一个元素,然后将该元素弹出并返回。top操作直接返回q1队列的队尾元素。empty操作判断q1队列是否为空。

时间复杂度:

push操作的时间复杂度为O(1);

pop操作的时间复杂度为O(n),其中n为栈中元素的个数;

top操作的时间复杂度为O(1);

empty操作的时间复杂度为O(1)。

空间复杂度:

使用了两个队列,因此空间复杂度为O(n),其中n为栈中元素的个数。

2024考研数据结构 文章被收录于专栏

本人考研刷算法题,立此专栏练习强化。

全部评论

相关推荐

06-02 15:53
阳光学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务