[ C++ ] STL---stack与queue

stack简介

stack的常用接口

queue简介

queue的常用接口

stack的模拟实现

queue的模拟实现

stack简介

1. stack是具有后进先出操作的一种容器适配器，其只能从容器的一端进行元素的插入与删除操作；

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出；

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

empty：判空操作

back：获取尾部元素操作

push_back：尾部插入元素操作

pop_back：尾部删除元素操作

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque；

stack官方文档：stack - C++ Reference

stack的常用接口

int main()
{
	stack<int> st;
	//入栈顺序:1,2,3,4
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);

	cout << "size=" << st.size() << endl;
	while (!st.empty())//判断栈是否为空
	{
		//非空取栈顶元素
		cout << st.top() << " ";
		//出栈
		st.pop();
	}
	cout << endl;
	return 0;
}

运行结果：

queue简介

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素；

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素；元素从队尾入队列，从队头出队列；

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类，该底层容器至少支持以下操作:

empty：检测队列是否为空

size：返回队列中有效元素的个数

front：返回队头元素的引用

back：返回队尾元素的引用

push_back：在队列尾部入队列

pop_front：在队列头部出队列

4. 标准容器类deque和list满足了这些要求，默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque；

queue官方文档：queue - C++ Reference

queue的常用接口

int main()
{
	queue<int> q;
	//入队列顺序:1 2 3 4
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	//计算队列中元素的个数
	cout << "size=" << q.size() << endl;
	//取队列的尾部元素
	cout << "back=" << q.back() << endl;
	while (!q.empty())//判断队列是否为空
	{
		//非空取队列头部元素
		cout << q.front() << " ";
		//出队列
		q.pop();
	}
	cout << endl;
	return 0;
}

运行结果：

stack的模拟实现

容器适配器：

已有的基本容器vector/list/deque相当于一台设备，这台设备支持的操作很多，比如插入，删除，迭代器访问等等，我们的需求是这个容器表现出来的是栈的特性: 先进后出，入栈出栈等等，此时，没有必要重新动手写一个新的数据结构，而是把原来的容器重新封装一下，改变它的接口，就可以把它当做栈使用；
容器适配器就是由基本的容器适配(改造)所形成的容器，比如stack，可以将stack理解成只是对vector/deque/list的访问受某种规则约束(只能从尾部访问)，所以没有必要将stack做成一个基本容器，使用其它的基本容器进行封装改造即可，所以stack在STL中只是一个“容器适配器”，而不是一个基础容器；

template<class T, class Container = deque<T>>
class stack
{
public:
    //构造函数,拷贝构造函数,析构函数,赋值运算符重载均不需要实现
    //对于自定义类型的成员变量_con,编译器自动调用类的默认成员函数
     
	//入栈
	void push(const T& x)
	{
		_con.push_back(x);
	}
	//出栈
	void pop()
	{
		_con.pop_back();
	}
	//获取栈顶元素
	const T& top()
	{
		return _con.back();
	}
	//获取栈中元素个数
	size_t size()
	{
		return _con.size();
	}
	//检测栈是否为空
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;//成员变量为容器(vector/list/deque)
};

queue的模拟实现

template<class T, class Container = 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()
	{
		return _con.empty();
	}
private:
	Container _con;
};

总结：

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；

queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list；