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

C++ -stack、queue

news 2024/10/24 6:54:32

在这里插入图片描述

博客主页：【夜泉_ly】
本文专栏：【C++】
欢迎点赞👍收藏⭐关注❤️

在这里插入图片描述

文章目录

  • 💡 简介
    • 1. 栈
    • 2. 队列
    • 3. 容器适配器的特点
    • 4. 适配器的本质
    • 5. 小结
  • 💡 简单实现
    • 1. 栈的实现
    • 2. 队列的实现
  • 💡 简单使用
    • 1. 用队列实现栈
      • 1 题目描述
      • 2 代码实现1
        • 逻辑详解
        • 代码
        • 总结
      • 3 代码实现2
        • 逻辑详解
        • 代码
        • 总结
    • 2. 用栈实现队列
      • 1 题目描述
      • 2 逻辑详解
      • 3 代码实现
      • 4 总结

💡 简介

栈（Stack）和队列（Queue）是两种常用的数据结构，它们在使用上相对简单，但却在计算机科学中扮演着重要的角色。它们的核心特性和行为使得它们在特定场景下比其他数据结构（如向量或链表）更具优势。

在数据结构-栈、队列-详解中，我用C语言模拟实现了栈和队列，感兴趣的可以去看看。

1. 栈

栈是一种容器适配器，其工作原理类似于电源适配器对电压的转换，但其内部使用的仍然是其他容器。
在这里插入图片描述
栈的默认底层容器是deque（双端队列），但也可以用其他容器实现栈的功能。

栈的核心特点是遵循后进先出（LIFO）原则，即最后入栈的数据最先出栈。栈的基本操作包括：

  • top：获取栈顶元素，但不移除它。
    在这里插入图片描述

  • push：将数据压入栈中。
    在这里插入图片描述

  • pop：移除栈顶元素并返回其值。
    在这里插入图片描述

通过这三种操作，栈能够有效地管理数据，适用于递归算法、表达式求值等场景。

📖例如《剑指offer》面试题6：从尾到头打印链表。
就可以使用栈 后进先出 的特性来完成。

2. 队列

队列同样是一种容器适配器，主要用于按照先进先出（FIFO）原则处理数据。
在这里插入图片描述

与栈不同，队列允许数据在一端插入（入队）并从另一端移除（出队）。队列的核心操作包括：

  • push：将数据入队。
    在这里插入图片描述

  • pop：移除队首元素并返回其值。
    在这里插入图片描述

  • front：获取队首元素，但不移除它。
    在这里插入图片描述

  • back：获取队尾元素，但不移除它。
    在这里插入图片描述

队列可以用于广度优先搜索，例如二叉树的层序遍历。

3. 容器适配器的特点

作为容器适配器，栈和队列并没有提供迭代器。这是因为它们不支持随意遍历元素，必须严格遵循LIFO或FIFO的规则。这种设计确保了数据的顺序性和结构的完整性。
此外，容器适配器通过封装底层容器，提供了更加简单易用的接口，使得开发者能够专注于数据操作，而无需关心内部实现的复杂性。

4. 适配器的本质

⭕适配器的本质是复用

例如容器适配器封装了其他的容器，数据存储在这个容器里面，而容器适配器会根据要求适配出对应的接口。

通过适配器，开发者可以使用不同的数据结构实现特定的行为，而无需重新实现算法或接口。这种灵活性大大提高了代码的复用性和可维护性。

在栈和队列的实现中，适配器模式使得其行为符合实际需求，同时又保持了与其他容器的兼容性。

5. 小结

综上所述，栈和队列作为基本的数据结构，在编程中发挥着重要的作用。理解它们的特点和使用场景，可以帮助开发者在实际应用中更有效地选择合适的数据结构，提升代码的效率与可读性。在今后的编程实践中，掌握栈和队列的使用无疑将为解决复杂问题提供有效的支持。

💡 简单实现

💡C语言版：数据结构-栈、队列-详解

1. 栈的实现

适配器是对已有的东西进行适配、转换。在 C 语言中模拟实现一个栈时，需要考虑是用数组实现还是用链表实现。
这就引出了一个问题：如何做到数组栈和链式栈的快速切换？

在 C++ 中，可以使用模板类来实现这一点：

namespace ly
{template<class T, class Container>class stack{public:// ...private:Container _con;}
}

这里用Container定义了一个容器，至于这个容器具体是什么，不知道。
但这就是想要达到的目的，因为使用更加灵活了：

void test_stack()
{ly::stack<int, std::vector<int>> st1;ly::stack<int, std::list<int>> st2;
}

可以看见，即可以用 vector 实现， 也可以用 list 实现，这取决于传的是什么容器。

下面我将继续完善这个栈：

  • 使用容器的插入、删除方法
    void push(const T& value) { _con.push_back(value); }
    void pop() { _con.pop_back(); }
  • 返回栈顶元素
    T top() const { return _con.back(); }

    ⭕值得一提的是这里不能用 [ ]，因为 list 不支持[]。

  • 判空
    bool empty() const { return _con.empty(); }
  • 返回栈的大小
    size_t size() const { return _con.size(); }

这就完了🤣，很简单吧。
并且数组栈、链式栈在用的角度没有区别，还能做到秒切换。

以下是一个简单的测试函数，演示如何使用这个栈：

void test_stack()
{// 使用 vector 实现的栈ly::stack<int, std::vector<int>> vecStack;  vecStack.push(1);vecStack.push(2);vecStack.push(3);std::cout << " vecStack:";while (!vecStack.empty()){std::cout << vecStack.top() << " ";  // 输出栈顶元素vecStack.pop();  // 弹出栈顶元素}std::cout << std::endl;// 使用 list 实现的栈ly::stack<int, std::list<int>> listStack;  listStack.push(1);listStack.push(2);listStack.push(3);std::cout << "listStack:";while (!listStack.empty()){std::cout << listStack.top() << " ";  // 输出栈顶元素listStack.pop();  // 弹出栈顶元素}
}

Output:

 vecStack:3 2 1
listStack:3 2 1

每次传模板参数比较麻烦，因此库里面也没要求每次都传：
在这里插入图片描述
deque 是什么，在我之后的文章中会讲。
这里可以直接给 vector：

template<class T, class Container = vector<T>>

⭕栈需不需要提供构造、析构？

不用，因为这是自定义类型，它会调用自己成员的构造、析构。而容器是已经实现好的，构造、析构就是现成的。

2. 队列的实现

大部分类似于栈的实现，这里直接引出问题：队列能不能用 vector 适配？可以，但不推荐。
强制适配：

void pop()
{ _con.erase(_con.begin());
}

erase 是 list 和 vector 都提供的接口，因此能用。

但这样强制适配好吗？这样不好。
如果在VS写出下面这几句代码：

std::queue<int, vector<int>> q; 
q.push(1);
q.pop();

再运行：
在这里插入图片描述
在这里插入图片描述

⭕库里面支持list，不支持vector。
⭕库里面pop调的pop_front，而vector没有pop_front。

💡 简单使用

下面的题目我在数据结构-栈、队列-相关练习中曾经讲过，不过是用C语言写的，有兴趣的可以去看看。

1. 用队列实现栈

题目链接：
225. 用队列实现栈
(https://leetcode.cn/problems/implement-stack-using-queues/description/)

1 题目描述

在此问题中，需要实现一个栈（Stack），但仅允许使用队列（Queue）来完成操作。
在这里插入图片描述

并且题目指出：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。
因此，必须通过一些巧妙的方式，利用队列的特性来模拟出栈的行为。

2 代码实现1

逻辑详解

数据成员

  • 根据题目要求，该类有两个队列 queue1 和 queue2，用于存储栈的元素。可以根据队列的大小和使用情况选择其中一个进行操作。

构造函数

  • MyStack 的构造函数是空的，因为这个类的实例并不需要初始化其他内容。

push

  • 当调用 push 时，如果 queue1 为空，则将元素 x 放入 queue2 中，否则放入 queue1 中。

这一步其实也可以就用一个队列来入元素，但我当时没这么想。

pop

  • pop 方法是最关键的函数。它负责从当前的主队列中弹出元素。
  • 首先检查 queue2 是否为空：
    • 如果为空，则表示当前的 queue1 是操作的主队列。将 queue1 中除了最后一个元素外的所有元素依次转移到 queue2 中，直到 queue1 只剩一个元素。
    • 取出 queue1 中的最后一个元素（即要弹出的元素），并将其返回。
  • 如果 queue2 不为空，操作类似，从 queue2 转移到 queue1。

这一设计确保了最后被放入的元素总是能在 pop() 方法中被弹出，符合栈的特性。
top

  • top 返回当前栈顶的元素而不移除它。它会检查 queue1 和 queue2，返回非空队列的最后一个元素（即栈顶元素）。
    empty

  • empty 方法用来检查栈是否为空。检查两个队列是否都为空就行。

代码

以下是实现的代码：

class MyQueue 
{stack<int> stackPush;stack<int> stackPop;
public:MyQueue() {}void checkSTPopEmpty(){if(stackPop.empty()){while(!stackPush.empty()){stackPop.push(stackPush.top());stackPush.pop();}}}void push(int x) { stackPush.push(x);}int pop() {checkSTPopEmpty();int tmp = stackPop.top();stackPop.pop();return tmp;}int top() {checkSTPopEmpty();return stackPop.top();}bool empty() { return stackPop.empty()&&stackPush.empty();}
};
总结

这个实现利用了两个队列通过转移元素的方式来模拟栈的行为，相对高效。push 操作的平均时间复杂度为 O(1)，而 pop 和 top 操作的平均时间复杂度为 O(1)。尽管个别操作可能在转移时有 O(n) 的复杂度，但整体表现是非常好的。
但是在空间上，题目提出了进一步的要求：

进阶：你能否仅用一个队列来实现栈。

3 代码实现2

相信只要会用两个队列实现，很快就能想到用一个队列实现的方法。

逻辑详解

要仅使用一个队列来实现队列的功能，可以采用一种不同的策略：在 push 操作时，将新元素加入队列的末尾，然后通过队列中的元素调整队列，以保持后进先出的顺序。

数据成员

  • 根据题目要求，仅使用一个队列 queue1 来存储所有的元素。

构造函数

  • MyQueue 的构造函数为空，无需额外初始化。

push

  • 首先，将元素 x 放入 queue1 的末尾。
  • 然后，通过循环，将队列中除新加入的元素外的其他元素依次移到队列的末尾。这样可以确保队列的顺序满足先进先出的特性，即最新加入的元素总是位于队列的前端。

pop

  • 直接从队列的前端弹出元素，并返回该元素。

top

  • 返回队列前端的元素，但不从队列中移除它。

empty

  • 检查 queue1 是否为空，以确定队列是否为空。
代码

以下是实现的代码：

class MyStack 
{queue<int> queue1;
public:MyStack() {}void push(int x) {   queue1.push(x);for (int i = 0; i < queue1.size() - 1; i++) {queue1.push(queue1.front());queue1.pop();}}int pop() {int tmp = queue1.front();queue1.pop();return tmp;}int top() {  return queue1.front();}bool empty() { return queue1.empty();}
};
总结

这种方法虽然可以使用单个队列来实现队列的功能，但在 push 操作中，由于需要调整队列中所有元素的位置，因此时间复杂度为 O(n)。
相较于使用两个栈或两个队列的方法，该实现可能在性能上有所下降。
但它展现了如何使用基础数据结构的灵活性来实现特定功能。

2. 用栈实现队列

题目链接：
232. 用栈实现队列
(https://leetcode.cn/problems/implement-queue-using-stacks/description/)

1 题目描述

在此问题中，需要实现一个队列，但仅允许使用栈来完成操作。

在这里插入图片描述
队列是先进先出（FIFO）的数据结构，而栈是后进先出（LIFO）的数据结构。
因此，和前面的题目一样，需要利用栈的特性来模拟队列的行为。

2 逻辑详解

数据成员

这个类有两个栈 stackPush 和 stackPop，分别用于存储加入队列的元素和用于弹出的元素。

构造函数

MyQueue 的构造函数是空的，实例的初始化不需要额外的设置。

checkSTPopEmpty

  • 这是一个辅助函数，负责检查 stackPop 是否为空。
  • 如果为空，则将 stackPush 中的所有元素逐个弹出并推入到 stackPop 中。这样确保了最新入栈的元素在 stackPop 中的最上面，符合队列的先入先出特性。

push

  • 该方法简单地将元素 x 推入 stackPush 中。所有的新元素都会在 stackPush 中存储。

pop

  • 当调用 pop() 时，首先调用 checkSTPopEmpty 来确保 stackPop 中有元素可以弹出。
  • 然后从 stackPop 中弹出并返回栈顶元素。

peek

  • peek 方法同样使用 checkSTPopEmpty() 确保 stackPop 中有元素，然后返回栈顶元素而不移除它。

empty

  • 检查两个栈是否都为空，以判断队列是否为空。

3 代码实现

以下是实现的代码：

class MyQueue 
{stack<int> stackPush;stack<int> stackPop;public:MyQueue() {}void checkSTPopEmpty(){if(stackPop.empty()){while(!stackPush.empty()){stackPop.push(stackPush.top());stackPush.pop();}}}void push(int x) { stackPush.push(x);}int pop(){checkSTPopEmpty();int tmp = stackPop.top();stackPop.pop();return tmp;}int peek() {checkSTPopEmpty();return stackPop.top();}bool empty() { return stackPop.empty()&&stackPush.empty();}
};

4 总结

使用两个栈的实现方法来模拟队列有效地解决了先进先出的问题。push 操作的时间复杂度为 O(1)，而 pop 和 peek 操作的平均时间复杂度为 O(1)，在最坏的情况下可能需要 O(n) 的时间进行转移，但整体性能仍然可以接受。
在这里插入图片描述

希望本篇文章对你有所帮助！并激发你进一步探索编程的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！


http://www.mrgr.cn/news/57369.html

相关文章：

  • Java多线程编程(一)
  • ES6运算符
  • #Swift 下标 Subscript - Access the elements of a collection
  • 排序算法 —— 快速排序（理论+代码）
  • Vue-插槽slot
  • 基于PHP的在线小说阅读平台
  • Golang | Leetcode Golang题解之第503题下一个更大元素II
  • 如何在 Debian VPS 上使用 mod_wsgi 和 Apache 运行 Django，并使用 virtualenv Python 环境
  • 【thinkphp8】00007 内置服务器，切换php版本
  • 13_Linux开机流程：以Red Hat Enterprise Linux 7（RHEL 7）为例
  • PTA数据库编程练习合集
  • PostgreSQL（十三）pgcrypto 扩展实现 AES、PGP 加密，并自定义存储过程
  • 10.21-10.23
  • 偷懒总结篇|贪心算法|动态规划|单调栈|图论
  • iPhone图片/照片/视频复制到win10系统的简单方法 - 照片导出
  • R语言统计分析——置换检验3
  • CMOS 图像传感器：像素寻址与信号处理
  • 【ShuQiHere】如何在 Linux 上虚拟化 macOS Catalina
  • 生成式AI的新篇章：从快思维到慢思维
  • 人生是不断排毒的过程
  • Codeforces Round 881 (Div. 3)（A~F1题解）
  • Linux的调度算法
  • ★ Linux ★ 基础开发工具的使用（上）
  • STM32--JQ8900语音模块
  • 嘘，偷偷复制某客巴巴的少许文字……
  • keil新建工程HC32L176MATA