• 【c++&Leetcode】232. Implement Queue using Stacks


    问题入口

    他人思路(时间复杂度更低)

    • Time complexity:
    • push : O(n);
    • peek : O(1);
    • pop : O(1);
    • empty: O(1);

    依照这位大佬的思路写下的代码:

    1. class MyQueue2 {
    2. public:
    3. stack<int> s1;
    4. stack<int> s2;
    5. MyQueue() {
    6. }
    7. void push(int x) {
    8. while (!s1.empty())
    9. {
    10. s2.push(s1.top());
    11. s1.pop();
    12. }
    13. s1.push(x);
    14. while (!s2.empty())
    15. {
    16. s1.push(s2.top());
    17. s2.pop();
    18. }
    19. }
    20. int pop() {
    21. int ret = s1.top();
    22. s1.pop();
    23. return ret;
    24. }
    25. int peek() {
    26. return s1.top();
    27. }
    28. bool empty() {
    29. return s1.empty();
    30. }
    31. };

    My way

    我不知道为什么死活要用vector,如果我知道c++有stack库我铁定不用vector。

    不过熟悉了一些vector基本操作还不错。请欣赏并不优美的代码:

    1. class MyQueue {
    2. public:
    3. vector<int> stack1;
    4. vector<int> stack2;
    5. int size;
    6. MyQueue() {
    7. size = 0;
    8. }
    9. void push(int x) {
    10. stack1.push_back(x);
    11. size++;
    12. stack2.assign(stack1.rbegin(), stack1.rend());
    13. }
    14. int pop() {
    15. int ret = *(stack2.end()-1);
    16. stack2.pop_back();
    17. size--;
    18. stack1.assign(stack2.rbegin(), stack2.rend());
    19. return ret;
    20. }
    21. int peek() {
    22. return *(stack1.begin());
    23. }
    24. bool empty() {
    25. return size == 0? true:false;
    26. }
    27. };

    扩展

    另外我对迭代器有一些好奇,以下是咨询chatgpt相关问题得到的回答。

    使用迭代器与直接索引访问容器相比,具有一些不同的特点和优势:

    1. **通用性:** 迭代器是一种通用的访问容器元素的方式,适用于各种不同类型的容器(例如,向量、列表、集合、映射等)。这使得您的代码更加通用,能够适用于不同的数据结构,而不需要修改大部分代码。

    2. **安全性:** 使用迭代器可以提高代码的安全性。索引访问容器时,如果索引越界,将导致未定义行为或程序崩溃。而使用迭代器可以更容易地避免这种问题,因为迭代器通常会在容器的开头和结尾进行有效性检查。

    3. **灵活性:** 迭代器可以支持正向和反向迭代,因此可以轻松实现从前向后和从后向前的遍历。这在某些情况下非常有用,例如需要逆序访问容器的情况。

    4. **容器修改:** 迭代器允许在遍历容器时修改容器中的元素。这对于在遍历过程中执行插入、删除或修改操作非常有用。在索引访问中,这样的操作可能导致迭代过程中的错误。

    5. **范围定义:** 迭代器可以用来定义特定范围的元素。通过指定范围的开始和结束迭代器,您可以轻松地操作这个范围内的元素,而无需考虑容器的大小。

    6. **适应性:** 一些容器不支持索引访问,例如 `std::list` 和 `std::set`,但它们仍然支持迭代器,因此迭代器是访问这些容器的唯一方法。

    综上所述,使用迭代器通常是更灵活、更安全、更通用的方法,特别是当涉及不同类型的容器和复杂的操作时。但对于某些简单的情况,直接索引访问也可能更加方便。选择使用哪种方法取决于您的需求和代码的复杂性。

    我可以说迭代器类似于指针吗?因为它们都需要使用 * 运算符来访问值。

    是的,你可以将C++中的迭代器视为某种程度上类似于指针。它们都提供了一种访问元素值的方法,你可以使用`*`运算符对它们进行解引用并访问它们指向的值。但是,迭代器和指针之间存在一些重要的区别:

    1. **抽象层次:** 迭代器提供了比指针更高级的抽象。虽然指针可以用于低级别的数组和内存导航,但迭代器专门设计用于以更安全和更抽象的方式导航数据结构,如容器(例如向量、列表、映射)。

    2. **容器独立性:** 迭代器不仅限于数组或连续的内存块。它们可以与不同类型的容器一起使用,并可以适应不同的容器实现。指针通常用于低级内存操作,不具备容器无关性。

    3. **安全性:** 迭代器通常比指针更安全,因为它们可以包括边界检查,确保不会访问容器的有效范围之外的元素。指针没有内置的这种安全功能。

    4. **复杂性:** 与指针相比,某些迭代器可能更复杂,特别是处理诸如`std::map`或`std::list`等容器时。迭代器可能需要处理非连续内存位置的遍历。

    5. **功能性:** 迭代器可以提供特定于与之关联的容器的附加功能,例如双向或随机访问能力,这些功能可能在指针中不可用。

    因此,虽然迭代器和指针在解引用以访问值的方式上有一些相似之处,但它们用途不同,提供不同级别的抽象和安全性。在与标准容器一起工作时,使用迭代器可以确保更安全和更容器无关的代码。

  • 相关阅读:
    论文复现|Panoptic Deeplab(全景分割PyTorch)
    极客日报:天猫双11交易额5403亿;史上最贵的苹果电脑出现; 超7成受访者认为脸书让美国更糟糕
    文献翻译平台(自用)
    Vue 封装vue-axios
    Linux命令(80)之sort
    Java---Stream进阶
    [红明谷CTF 2021]write_shell %09绕过过滤空格 ``执行
    Mybatis快速入门
    Intel汇编-数组遍历
    【考研数学】概率论与数理统计 —— 第七章 | 参数估计(2,参数估计量的评价、正态总体的区间估计)
  • 原文地址:https://blog.csdn.net/qq_37120435/article/details/133692254