系列文章目录

上一篇文章：【C++闯关笔记】STL：list 的学习和使用-CSDN博客

下一篇文章：【C++闯关笔记】STL：deque与priority_queue的学习和使用-CSDN博客

---

目录

前言

一、概念

二、使用介绍

1.stack：后进先出

核心特性

核心操作

细节与陷阱

使用场景

2.queue：先进先出

核心特性

核心操作

细节与陷阱

使用场景

三、模拟实现

1.stack模拟实现

2.queue模拟实现

总结

---

---

前言

C++中的stack、queue与数据结构中的栈、队列本质上是一样的，不同之处仅在C++将其它们封装成了类并添加了一些新东西，其他方面与数据的栈、队列完全一致。

---

一、概念

核心概念：它们都是“容器适配器”

首先，要建立一个重要的认知：stack 和 queue 都不是独立的容器，而是“容器适配器”。

你可以把它们想象成对某种底层容器（如 list 、vector等 ）的接口包装和功能限制。它们基于vector、list 或者其他什么底层容器构建，但只暴露了符合特定数据结构（栈或队列）规则的接口。

二、使用介绍

1.stack：后进先出

核心特性

①LIFO: Last-In, First-Out，后进先出。就像一摞盘子，取的总是最上面的那个（也就是最后放上去的）。

②栈顶：我们约定进行操作的那一端称为栈顶，另一端则为栈底。

核心操作

• push(const T& value): 压栈，将元素放入栈顶。

• pop(): 弹栈，移除栈顶元素（并不返回元素！）。

• top(): 访问栈顶元素（返回引用）。

• empty(): 判断栈是否为空。

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

细节与陷阱

①pop( ) 返回 void，不能用来获取值。正确的做法是先通过top( )获取栈顶数据，在pop( )移除栈顶数据；

②警惕空栈。对空栈调用top 和pop 操作是未定义行为，绝大多数情况下会导致程序崩溃；

使用场景

• 函数调用栈：计算机系统最核心的应用，记录函数调用关系和局部变量。

• 表达式求值：处理括号匹配、将中缀表达式转换为后缀表达式。

• 撤销操作：编辑器中的撤销，将操作压栈，撤销时弹出。

• 深度优先搜索：DFS算法通常使用栈来实现。

2.queue：先进先出

核心特性

①FIFO: First-In, First-Out，先进先出。就像现实生活中的排队，先来的人先接受服务。

②出数据的一端称为队头，入数据的一端称为队尾。

核心操作

• push(const T& value): 入队，将元素放入队尾。

• pop(): 出队，移除队首元素（同样不返回元素！）。

• front(): 访问队首元素。

• back(): 访问队尾元素。

• empty(): 判断队列是否为空。

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

细节与陷阱

①front()/back() 和 pop() 也必须分两步走。先通过 front / back 获取数据后，再 pop 出数据。

②警惕空队列。对空队列调用 front()/back() 和 pop() 同样是未定义行为。

使用场景

• 广度优先搜索：BFS算法的核心数据结构。

• 消息队列：在网络通信或多线程中，用于在不同线程或进程间传递数据。

• 缓冲区：例如打印机任务队列，先提交的打印任务先执行。

• 模拟现实排队：银行叫号系统等。

---

三、模拟实现

1.stack模拟实现

考虑到 stack 只在栈顶频繁进行数据的写入写出，那么选择一个插入/删除数据操作效率高的底层容器，进行封装无疑是最好的选择。

vector 的push_back与push_pop 时间复杂度均为O(1)，故这里我们采用封住 vector 来模拟实现stack。

模拟代码如下：

#include <vector>

namespace karsen
{
	template<typename T>
	class stack
	{
	public:
		stack()
		{}

		void push(const T& x)
		{
			_st.push_back(x);
		}

		T& top()
		{
			return _st.back();
		}

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

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

		void pop()
		{
			_st.pop_back();
		}

	private:
		std::vector<T> _st;
	};
}


//以下是更接近库中的实现，deque将在下篇博客介绍
#pragma once
//#include<vector>
#include<deque>
namespace karsen
{
	//template<class T,class Container = vector<T>>
	template<class T,class Container =deque<T> >
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_back();
		}

		const T& top()const
		{
			return _con[_con.size() - 1];
		}

		T& top()
		{
			return _con[_con.size() - 1];
		}
		
		~stack()
		{
			_con.~deque();
		}

		//const T& top()
		//{
		//	return _con[_con.size() - 1];
		//}

		//这是最矛盾的，const修饰的函数承诺不能修改对象，这里却可以通过返回的引用修改
		//T& top()const
		//{
		//	return _con[_con.size() - 1];
		//}

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

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

	private:
		Container _con;
	};
}

2.queue模拟实现

相较于 stack 的单侧数据增删，queue需要在队头/队尾频繁进行数据增删，vector 显然不再适合，此时本质为双向循环链表的 list 就比较合适。

模拟代码如下：

#pragma once
#include<list>

namespace karsen
{
	template<typename T>
	class queue
	{
	public:
		queue()
		{}

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

		void push(const T& x)
		{
			_qu.push_back(x);
		}

		void pop()
		{
			_qu.pop_front();
		}

		T& back()
		{
			return _qu.back();
		}

		T& front()
		{
			return _qu.front();
		}

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

	private:
		std::list<T> _qu;
	};

};



//以下是更接近库中的实现，deque将在下篇博客介绍
#pragma once
//#include<list>
#include<deque>
namespace karsen
{
	template <class T, class Containar = deque<T> >
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

		const T& front()const
		{
			return _con.front();
		}

		T& front()
		{
			return _con.front();
		}

		const T& back()const
		{
			return _con.back();
		}

		T& back()
		{
			return _con.back();
		}

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

		size_t size()
		{
			return _con.size();
		}
	private:
		Containar _con;
	};
}

---

总结

本文介绍了stack与queue的概念以及使用，最后给出了 vector 模拟实现的stack代码；用 list 模拟实现的 queue代码。

值得一提的是STL源码中，stack与queue都是基于deque进行封装的，deque不仅提供O(1)的头尾操作，并且没有vector扩容时带来的时间损耗。

最后，如果希望进一步探究栈与队列的使用，可参考：

【数据结构】栈_栈 数据结构-CSDN博客

【数据结构】队列_数据结构队列-CSDN博客

读完点赞，手留余香~