当前位置： 首页 > article >正文

探密 C++ STL — 深入理解 Stack 和 Queue 的实现与应用

article 2024/11/14 0:01:41

目录

引言

1. 什么是 Stack？

1.1 Stack 的概念

1.2 Stack 的操作

1.3 最小栈的实现

1.4 栈的模拟实现

2. 什么是 Queue？

2.1 Queue 的概念

2.2 Queue 的操作

2.3 队列的模拟实现

3. Priority Queue（优先级队列）

3.1 Priority Queue 的概念

3.2 Priority Queue 的操作

3.3 自定义优先级的优先级队列

4. 容器适配器与底层实现

4.1 容器适配器的概念

4.2 为什么选择 deque 作为默认容器？

4.3 栈和队列的模拟实现

结论

引言

在计算机科学中，数据结构是存储和组织数据的方式，使得我们可以高效地进行数据的访问和修改。在众多数据结构中，stack（栈）和 queue（队列）是两种非常基础且广泛应用的线性数据结构。C++ 提供了非常方便的标准库（STL）来实现 stack 和 queue，并且它们被广泛应用于各种算法和解决方案中。

本文将深入介绍 stack 和 queue 的基本概念、如何使用它们，以及它们在 C++ STL 中的实现细节。通过多个代码示例，我们将理解它们的实现原理，并探索如何灵活运用这些数据结构来解决实际编程问题。

1. 什么是 Stack？

1.1 Stack 的概念

stack 是一种后进先出（LIFO, Last In First Out）的数据结构，这意味着最后插入的数据将最先被移除。栈可以想象成一个物理的堆叠，比如书本堆。只有在最上面的书本可以被移除或被添加到堆中。

栈的典型应用场景包括函数调用栈、括号匹配、撤销操作等。C++ 中的 stack 是通过 STL 提供的容器适配器，底层可以使用 deque 或其他符合条件的容器来实现。

1.2 Stack 的操作

C++ 中，stack 提供了以下基本操作：

  • push()：将元素压入栈顶。

  • pop()：移除栈顶元素。

  • top()：返回栈顶元素。

  • empty()：检查栈是否为空。

  • size()：返回栈中元素的个数。

以下是 stack 的常用代码示例：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << "Stack top: " << s.top() << std::endl; // 输出 3
    s.pop();
    std::cout << "Stack top after pop: " << s.top() << std::endl; // 输出 2

    return 0;
}

在这个示例中，我们创建了一个整数栈，并依次向栈中插入 1、2 和 3。随后，通过 top() 查看栈顶元素并使用 pop() 将其移除。

1.3 最小栈的实现

最小栈是一个扩展版本的栈，它除了支持基本的栈操作外，还可以在常数时间内返回栈中的最小元素。我们可以使用两个栈来实现一个最小栈：

  • 一个栈存储所有元素。

  • 另一个栈存储当前栈中的最小值。

以下是最小栈的代码实现：

#include <stack>

class MinStack {
public:
    void push(int x) {
        elemStack.push(x);
        // 如果最小值栈为空，或者当前值小于等于最小值栈顶，则将其压入最小值栈
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }

    void pop() {
        if (elemStack.top() == minStack.top()) {
            minStack.pop();
        }
        elemStack.pop();
    }

    int top() {
        return elemStack.top();
    }

    int getMin() {
        return minStack.top();
    }

private:
    std::stack<int> elemStack; // 存储栈中的所有元素
    std::stack<int> minStack;  // 存储当前栈中的最小值
};

在这里，我们使用两个栈 elemStack 和 minStack。minStack 用于保存栈中的最小元素，这样当调用 getMin() 时，可以在 O(1) 时间内返回最小值。

1.4 栈的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的 vector，因此使用 vector 可以完全模拟实现一个栈：

#include <vector>

class Stack {
public:
    void push(int x) {
        elements.push_back(x);
    }

    void pop() {
        if (!elements.empty()) {
            elements.pop_back();
        }
    }

    int top() {
        return elements.back();
    }

    bool empty() {
        return elements.empty();
    }

    size_t size() {
        return elements.size();
    }

private:
    std::vector<int> elements;
};

在这个实现中，使用 vector 来模拟 stack 的行为，支持基本的栈操作，例如 push()、pop()、top() 和 empty()。

2. 什么是 Queue？

2.1 Queue 的概念

queue 是一种先进先出（FIFO, First In First Out）的数据结构，意味着最早插入的数据最先被移除。队列可以想象成排队买票的场景，最先排队的人最先买到票。

队列的典型应用包括任务调度、宽度优先搜索（BFS）等。C++ 中的 queue 同样是通过 STL 提供的容器适配器，底层可以使用 deque 或其他符合条件的容器来实现。

2.2 Queue 的操作

C++ 中，queue 提供了以下基本操作：

  • push()：将元素插入队尾。

  • pop()：移除队头元素。

  • front()：返回队头元素。

  • back()：返回队尾元素。

  • empty()：检查队列是否为空。

  • size()：返回队列中元素的个数。

以下是 queue 的常用代码示例：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << "Queue front: " << q.front() << std::endl; // 输出 1
    q.pop();
    std::cout << "Queue front after pop: " << q.front() << std::endl; // 输出 2

    return 0;
}

在这个示例中，我们创建了一个整数队列，并依次向队列中插入 1、2 和 3。随后，通过 front() 查看队头元素并使用 pop() 将其移除。

2.3 队列的模拟实现

因为 queue 的接口中存在头删和尾插的操作，因此使用 vector 来封装效率太低，可以借助 list 来模拟实现 queue：

#include <list>

class Queue {
public:
    void push(int x) {
        elements.push_back(x);
    }

    void pop() {
        if (!elements.empty()) {
            elements.pop_front();
        }
    }

    int front() {
        return elements.front();
    }

    int back() {
        return elements.back();
    }

    bool empty() {
        return elements.empty();
    }

    size_t size() {
        return elements.size();
    }

private:
    std::list<int> elements;
};

在这个实现中，我们使用 list 来模拟 queue 的行为，因为 list 支持在头部和尾部进行高效的插入和删除操作。

3. Priority Queue（优先级队列）

3.1 Priority Queue 的概念

优先级队列是一种特殊的队列，它的每个元素都有一个优先级，出队时总是优先级最高的元素最先被移除。C++ 中的 priority_queue 默认是一个大顶堆，意味着优先级最大的元素会最先出队。

3.2 Priority Queue 的操作

C++ 中，priority_queue 提供了以下基本操作：

  • push()：将元素插入队列中。

  • pop()：移除优先级最高的元素。

  • top()：返回优先级最高的元素。

  • empty()：检查队列是否为空。

  • size()：返回队列中元素的个数。

以下是 priority_queue 的常用代码示例：

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);

    std::cout << "Priority Queue top: " << pq.top() << std::endl; // 输出 4
    pq.pop();
    std::cout << "Priority Queue top after pop: " << pq.top() << std::endl; // 输出 3

    return 0;
}

在这个示例中，我们创建了一个整数优先级队列，并依次向队列中插入 3、1、4 和 2。由于优先级队列是一个大顶堆，所以每次 top() 都返回最大的元素。

3.3 自定义优先级的优先级队列

我们可以通过自定义比较器来实现一个小顶堆或者具有自定义优先级的优先级队列。例如，下面是一个实现小顶堆的示例：

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 使用 greater<int> 作为比较器来实现小顶堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(2);

    std::cout << "Min Heap top: " << minHeap.top() << std::endl; // 输出 1
    minHeap.pop();
    std::cout << "Min Heap top after pop: " << minHeap.top() << std::endl; // 输出 2

    return 0;
}

在这个示例中，我们使用了 greater<int> 作为比较器，使得 priority_queue 的行为变成了小顶堆，从而每次 top() 返回最小的元素。

4. 容器适配器与底层实现

4.1 容器适配器的概念

容器适配器是一种设计模式，通过对底层容器进行封装，提供不同的接口来实现特定的数据结构。stack 和 queue 就是典型的容器适配器，它们默认使用 deque 作为底层容器。

4.2 为什么选择 deque 作为默认容器？

  • deque 支持在头部和尾部的高效插入和删除操作，这对于 stack 和 queue 来说非常重要。

  • deque 在扩容时不需要搬移大量元素，相比于 vector，deque 的效率更高。

  • 由于 stack 和 queue 不需要遍历操作，deque 的迭代器复杂性并不会影响它们的使用。

4.3 栈和队列的模拟实现

STL 中的 stack 和 queue 默认使用 deque 作为底层实现，但它们也可以使用其他符合条件的容器来实现。例如，可以使用 list 或 vector 来模拟实现栈和队列：

#include <deque>

// 使用 deque 作为底层容器来实现 stack
namespace bite {
    template<class T, class Con = std::deque<T>>
    class Stack {
    public:
        void push(const T& x) { _c.push_back(x); }
        void pop() { _c.pop_back(); }
        T& top() { return _c.back(); }
        size_t size() const { return _c.size(); }
        bool empty() const { return _c.empty(); }
    private:
        Con _c;
    };
}

在这个实现中，我们使用模板参数 Con 来定义底层容器，默认为 deque，但用户可以自定义底层容器类型，例如 vector 或 list。

结论

通过本文的详细讲解，相信大家对 stack、queue 和 priority_queue 有了更加深入的理解。我们从它们的基本概念和操作入手，逐步探索了它们的实际应用和实现方式。无论是使用 STL 中现成的容器，还是手动模拟实现这些数据结构，理解其底层的原理和操作方式对于写出高效可靠的代码都是至关重要的。

在编程过程中，选择合适的数据结构来解决问题是非常关键的技能。栈和队列作为最基础的数据结构之一，具有简单而强大的特性，能为各种复杂问题提供解决方案。希望通过这篇文章，大家能更好地掌握它们，并在日后的编程实践中灵活运用。


http://www.kler.cn/a/389568.html

相关文章：

  • ReactPress技术揭秘
  • 【秋招笔试-支持在线评测】11.13花子秋招(已改编)-三语言题解
  • 在Flutter中，禁止侧滑的方法
  • 【Mode Management】AUTOSAR架构下唤醒源检测函数EcuM_CheckWakeup详解
  • NUXT3学习日记一（在我git中拉取代码、文件讲解）
  • Stored procedures in PostgreSQL
  • 前端上传大文件，后端报错Content-Type ‘application/octet-stream‘ is not supported【解决】
  • Spring Boot2.x教程：（十二）日志分割后续
  • #渗透测试#SRC漏洞挖掘#Python自动化脚本的编写04之通过面向对象编程学生管理信息系统01
  • 20241108，LeetCode 每日一题，用 Go 计算字符串中最长无重复字符
  • 创元集团携手火山引擎，数据飞轮驱动美妆品牌数字化转型
  • 一个基于Zookeeper+Dubbo3+SpringBoot3的完整微服务调用程序示例代码
  • C语言中，“extern”关键字的含义与用法
  • 网页版五子棋——用户模块（服务器开发）
  • 金山云C++面试题及参考答案
  • jenkins配置前端自动部署
  • MSB8041此项目需要 MFC 库。从 Visual Studio 安装程序(单个组件选项卡)为正在使用的任何工具集和体系结构安装-错误解决
  • 2024 年度分布式电力推进（DEP）系统发展探究
  • VBA08-if语句
  • 互动电影《催眠麦克风》官宣定档2.21预售正式开始
  • Kafka-linux环境部署
  • ssm077铁岭河医院医患管理系统+vue(论文+源码)_kaic
  • http协议与内外网的划分
  • uni-app资源管理与图标使用全解
  • Android 获取 SHA1 值的详细步骤
  • 【系统架构设计师】2024年下半年真题论文: 论面向服务的架构设计（包括解题思路和参考素材）