剑指Offer 队列&栈题目集合

2023-12-22 11:44:06

用两个栈实现队列

刷题链接
https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6

题目描述
在这里插入图片描述

思路一
使用两个栈来实现队列的功能。栈 1 用于存储入队的元素,而栈 2 用于存储出队的元素。
1.push方法将元素压入栈 1。
2.pop方法首先检查栈 2 是否为空。如果为空,则将栈 1 中的所有元素移到栈 2。然后,弹出栈 2 中的顶部元素并返回。

在这里插入图片描述

复杂度分析

时间复杂度:在最坏情况下,pop 操作的时间复杂度是 O(n),但在平均情况下,当栈2中有元素时,pop 操作的时间复杂度是 O(1)。这是因为在平均情况下,元素不会每次都从栈1移动到栈2。总体而言,这个实现的 push 操作是 O(1),而 pop 操作的最坏情况下是 O(n),平均情况下是 O(1)。
空间复杂度: O(n),辅助栈的空间,最差的情况下两个栈共存储N个元素。

python3

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        # 入队时直接将元素压入 stack1
        self.stack1.append(x)

    def pop(self) -> int:
        # 如果 stack2 为空,将 stack1 中的元素依次弹出并压入 stack2,实现队列的先进先出
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        # 弹出 stack2 的栈顶元素,即队列头部的元素
        return self.stack2.pop()

C++

class Solution {
  public:
    // 入队操作,将元素压入 stack1
    void push(int x) {
        stack1.push(x);
    }

    // 出队操作,实现队列的先进先出
    int pop() {
        // 如果 stack2 为空,将 stack1 中的元素依次弹出并压入 stack2
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        // 弹出 stack2 的栈顶元素,即队列头部的元素
        int frontElement = stack2.top();
        stack2.pop();
        return frontElement;
    }

  private:
    stack<int> stack1;
    stack<int> stack2;
};

文章来源:https://blog.csdn.net/JulyLi2019/article/details/135146370
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。