stack和queue在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque容器。

文章目录

一、容器适配器

容器适配器 是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。 之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。

说白了就是通过一种容器来实现另一种容器的功能，比如用链表实现栈，栈的push操作就可以用链表的push_back来实现，而栈的pop操作用链表的pop_back实现，至于链表的其他接口（栈用不到的接口，比如头插头删）则不对外进行暴露，因此虽然表面上看上去是一个栈，但是在底层实现上确是一个链表。
STL中的stack和queue在底层上默认用的是双端队列deque：
在这里插入图片描述

Container是一个缺省参数，我们在使用的时候可以自定义这个容器适配器，比如不想用deque而想用vector或list，直接在实例化对象的时候传入vector或list即可。

二、stack

stack是STL中的栈，其功能和数据结构中的栈一样。
常用接口：

成员函数功能
empty()判断栈是否为空
size()获取栈中有效元素个数
top()获取栈顶元素
push(x)将元素x入栈
pop()栈顶元素出栈
swap()交换两个栈中的数据
#include <iostream>
#include <stack>
#include <list>
using namespace std;

int main()
{
	stack<int, list<int>> st;//用list作为容器适配器
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	cout << st.size() << endl; //4
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl; //4 3 2 1

	stack<int, list<int>> st1;
	st1.swap(st);//交换st到st1

	cout << st.size() << endl; //0
	while (!st.empty())
	{
		cout << st.top() << " ";//空
		st.pop();
	}
	cout << endl; 

	return 0;
}

模拟实现stack

#include<deque>
namespace hjl //防止命名冲突
{
	template<class T, class Container = std::deque<T>>
	class stack
	{
	public:
		//元素入栈
		void push(const T& x)
		{
			_con.push_back(x);
		}
		//元素出栈
		void pop()
		{ 
			_con.pop_back();
		}
		//获取栈顶元素
		T& top()
		{
			return _con.back();
		}
		const T& top() const
		{
			return _con.back();
		}
		//获取栈中有效元素个数
		size_t size() const
		{
			return _con.size();
		}
		//判断栈是否为空
		bool empty() const
		{
			return _con.empty();
		}
		//交换两个栈中的数据
		void swap(stack<T, Container>& st)
		{
			_con.swap(st._con);
		}
	private:
		Container _con;
	};
}

三、queue

queue是STL中的队列，功能和数据结构中的队列一样。

成员函数功能
empty()判断队列是否为空
size()获取队列中有效元素个数
front()获取队头元素
back()获取队尾元素
push(x)将x入到队尾
pop()队头出队列
swap()交换两个队列中的数据
#include <iostream>
#include <list>
#include <queue>
using namespace std;

int main()
{
	queue<int, list<int>> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	cout << q.size() << endl; //4
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();//队头出队列
	}
	cout << endl; //1 2 3 4
	return 0;
}

模拟实现queue

#include<deque>
namespace hjl //防止命名冲突
{
	template<class T, class Container = std::deque<T>>
	class queue
	{
	public:
		//队尾入队列
		void push(const T& x)
		{
			_con.push_back(x);
		}
		//队头出队列
		void pop()
		{
			_con.pop_front();
		}
		//获取队头元素
		T& front()
		{
			return _con.front();
		}
		const T& front() const
		{
			return _con.front();
		}
		//获取队尾元素
		T& back()
		{
			return _con.back();
		}
		const T& back() const
		{
			return _con.back();
		}
		//获取队列中有效元素个数
		size_t size() const
		{
			return _con.size();
		}
		//判断队列是否为空
		bool empty() const
		{
			return _con.empty();
		}
		//交换两个队列中的数据
		void swap(queue<T, Container>& q)
		{
			_con.swap(q._con);
		}
	private:
		Container _con;
	};
}

四、priority_queue

priority_queue又被称为优先级队列，它和队列的区别在于，默认使用vector作为底层存储数据的容器，并且在vector上又使用了堆算法将vector中元素构成堆的结构，这也就意味着如果入队一组无序的数据，在出队列时会变成有序，默认情况下priority_queue是大堆，也就是降序。
在这里插入图片描述

它相比于队列多了第三个参数，这个参数默认是less，建大堆（也就是降序，大数先出队列），也可以换成greater，建小堆（升序，小数先出队列）。

其接口和队列一样，只是在入队和出队时作了排序

成员函数功能
push(x)插入元素x到队尾然后排序
pop()弹出队头元素（堆顶元素）
top()访问队头元素（堆顶元素）
size()获取队列中有效元素个数
empty()判断队列是否为空
swap()交换两个队列的内容
#include <iostream>
#include <functional>
#include <queue>
using namespace std;
int main()
{
	priority_queue<int> q;
	q.push(3);
	q.push(6);
	q.push(0);
	q.push(2);
	q.push(9);
	q.push(8);
	q.push(1);
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl; //9 8 6 3 2 1 0

	priority_queue<int,vector<int>,greater<int>> q1;
	q1.push(3);
	q1.push(6);
	q1.push(0);
	q1.push(2);
	q1.push(9);
	q1.push(8);
	q1.push(1);
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl; //0 1 2 3 6 8 9
	return 0;
}

使用优先级队列排序日期类

自定义类要使用less，必须要重载操作符<，要使用greater，必须要重载操作符>，并且也可以传入一个自定义的仿函数：

#include<iostream>
#include<assert.h>
#include<queue>
#include<vector>
#include <functional>
using namespace std;

class Date
{
public:
	Date(int year = 0, int month = 0, int day = 0);
	void Print();
	//比较日期的大小
	friend bool operator>(const Date& a,const Date& b);
	friend bool operator<(const Date& a, const Date& b);
	friend bool operator==(const Date& a, const Date& b);

	//日期减日期
	int operator-(const Date& d);

	friend ostream& operator<<(ostream& out, const Date& d);

private:
	int _year;
	int _month;
	int _day;
};

//获取某年某月的天数，因为要多次调用，可以写成内联函数
inline int GetMonthDay(int year, int month)
{
	static int dayArray[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
	int day = dayArray[month];
	if (month == 2 && ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)))
	{
		day = 29;
	}
	return day;
}
//构造函数
Date::Date(int year, int month, int day)
{
	//检查日期的合法性
	if (year >= 0
		&& month > 0 && month < 13
		&& day>0 && day <= GetMonthDay(year, month))
	{
		_year = year;
		_month = month;
		_day = day;
	}
	else
	{
		cout << "非法日期";
		cout << year << "-" << month << "-" << day << endl;
	}
}


//比较大小只需要实现>和==即可，其他比较操作符都可以用这两个操作符实现，提高代码复用率
bool operator>(const Date& a, const Date& b)
{
	if (a._year > b._year)
	{
		return true;
	}
	else if (a._year == b._year)
	{
		if (a._month > b._month)
		{
			return true;
		}
		else if (a._month == b._month)
		{
			if (a._day > b._day)
			{
				return true;
			}
		}
	}
	return false;
}

bool operator<(const Date& a, const Date& b)
{
	return !(a == b) && !(a > b);
}

bool operator==(const Date& a, const Date& b)
{
	return a._year == b._year && a._month == b._month && a._day == b._day;
}

ostream& operator<<(ostream& out, const Date& d)
{
	cout << d._year << "-" << d._month << "-" << d._day << endl;
	return out;
}
struct cmp
{
	bool operator()(Date a, Date b) 
	{
		return a > b;
	}
};

int main()
{
	//priority_queue<Date,vector<Date>,greater<Date>> q;
	//priority_queue<Date, vector<Date>, less<Date>> q;
	priority_queue<Date, vector<Date>,cmp> q;//传入仿函数cmp
	q.push(Date(1, 5, 15));
	q.push(Date(10, 4, 6));
	q.push(Date(7, 7, 1));
	q.push(Date(10, 12, 8));
	q.push(Date(5, 11, 9));
	q.push(Date(10, 7, 1));

	while (!q.empty())
	{
		cout << q.top();
		q.pop();
	}

	return 0;
}

在这里插入图片描述

模拟实现priority_queue

#include<vector>
#include<iostream>
namespace hjl
{
	//比较方式（使内部结构为大堆）
	template<class T>
	struct less
	{
		bool operator()(const T& l, const T& r)
		{
			return l < r;
		}
	};
	//比较方式（使内部结构为小堆）
	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)
		{
			return l > r;
		}
	};
	//仿函数默认为less
	template<class T, class  Container = std::vector<T>,class Compare=less<T>>
	class priority_queue
	{
	public:
		//向上调整算法，每push一个数都要调用向上调整算法，保证插入后是一个大堆
		void AdjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent],_con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent= (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		//向下调整算法，每次调用pop都要进行向下调整算法重新构成大堆
		void AdjustDwon(int parent)
		{
			Compare com;
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() &&com( _con[child] ,_con[child + 1]))
				{
					child++;
				}
				if (com(_con[parent] ,_con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		//迭代器初始化
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)//在这里传迭代器进行初始化
		{
			for (size_t i = 1; i <_con.size(); i++)
			{
				AdjustUp(i);//向上调整建堆
			}
		}

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

			AdjustUp(_con.size() - 1);
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDwon(0);
		}
		T top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

在这里插入图片描述

# 容器 # c++
Logo
向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

avatar 云原生

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生