C++ -stack、queue

博客主页：【夜泉_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）原则，即最后入栈的数据最先出栈。栈的基本操作包括：

pop：移除栈顶元素并返回其值。

push：将数据压入栈中。

top：获取栈顶元素，但不移除它。

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

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

2.队列

队列同样是一种容器适配器，主要用于按照先进先出（FIFO）原则处理数据。

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

back：获取队尾元素，但不移除它。

front：获取队首元素，但不移除它。

pop：移除队首元素并返回其值。

push：将数据入队。

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

3.容器适配器的特点

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

4.适配器的本质

⭕适配器的本质是复用

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

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

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

5.小结

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

💡 简单实现

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

1.栈的实现

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

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

namespace ly {template<classT,classContainer>classstack{public:// ...private: Container _con;}}

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

voidtest_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(); }
• 判空
  bool empty() const { return _con.empty(); }
• 返回栈的大小
  size_t size() const { return _con.size(); }

返回栈顶元素
T top() const { return _con.back(); }

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

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

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

voidtest_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<classT,classContainer= vector<T>>

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

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

2.队列的实现

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

voidpop(){ _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 方法用来检查栈是否为空。检查两个队列是否都为空就行。

代码

以下是实现的代码：

classMyQueue{ stack<int> stackPush; stack<int> stackPop;public:MyQueue(){}voidcheckSTPopEmpty(){if(stackPop.empty()){while(!stackPush.empty()){ stackPop.push(stackPush.top()); stackPush.pop();}}}voidpush(int x){ stackPush.push(x);}intpop(){checkSTPopEmpty();int tmp = stackPop.top(); stackPop.pop();return tmp;}inttop(){checkSTPopEmpty();return stackPop.top();}boolempty(){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 是否为空，以确定队列是否为空。

代码

以下是实现的代码：

classMyStack{ queue<int> queue1;public:MyStack(){}voidpush(int x){ queue1.push(x);for(int i =0; i < queue1.size()-1; i++){ queue1.push(queue1.front()); queue1.pop();}}intpop(){int tmp = queue1.front(); queue1.pop();return tmp;}inttop(){return queue1.front();}boolempty(){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 代码实现

以下是实现的代码：

classMyQueue{ stack<int> stackPush; stack<int> stackPop;public:MyQueue(){}voidcheckSTPopEmpty(){if(stackPop.empty()){while(!stackPush.empty()){ stackPop.push(stackPush.top()); stackPush.pop();}}}voidpush(int x){ stackPush.push(x);}intpop(){checkSTPopEmpty();int tmp = stackPop.top(); stackPop.pop();return tmp;}intpeek(){checkSTPopEmpty();return stackPop.top();}boolempty(){return stackPop.empty()&&stackPush.empty();}};

4 总结

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

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