C++中的stack和queue

一丶stack
- 1. stack的介绍
- 2. stack的使用
- 3. stack的模拟实现
二丶queue
- 1. queue的介绍
- 2. queue的使用
- 3. queue的模拟实现

一丶stack

1. stack的介绍

stack的文档介绍

关于stack：
1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其只能从容器的一端进行元素的插入和提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下的操作：

empty: 判空操作
back: 获取尾部元素操作
push_back: 尾部插入元素操作
pop_back: 尾部删除元素操作

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

stack的示意图如下：
stack示意图

2. stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

3. stack的模拟实现

对于这里的模拟实现，我们使用vector或者list来模拟实现stack。

设计思路是这样的：我们在设计stack的方法时，内部直接使用vector或者list的方法，stack的方法内部封装着库中某容器的现有方法。

namespace bit
{
	//模板和函数的参数是类似的
	//函数参数传递的是数据对象 而模板传参数递的是类型
	//函数参数可以给缺省值 而模板参数也可以给缺省值
	template<class T, class Container = list<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

	private:
		Container _con;
	};
}

测试代码：

#include <iostream>

using namespace std;

#include <stack>
#include <queue>

#include "Stack.h"

void test_stack()
{
	//bit::stack<int, vector<int>> s;
	/*bit::stack<int, list<int>> s;*/
	bit::stack<int> s;

	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;

}

int main()
{
	test_stack();
	
	return 0;
}

二丶queue

1. queue的介绍

queue的文档介绍

关于queue:
1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类，该底层容器应至少支持以下操作：

empty: 检测队列是否为空
size: 返回队列中有效元素的个数
front: 返回对头元素的引用
back: 返回队尾元素的引用
push_back: 在队列尾部入队列
pop_front: 在队列头部出队列

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

以下是queue的示意图：
queue示意图

2. queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是则返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

3. queue的模拟实现

和stack一样，这里我们同样使用底层容器来实现queue容器适配器。只不过这里我们用list而不用vector。

由于vector底层是数组，queue要求尾插和头删。尾插方面，list的效率和vector的效率相差不大，但在头删方面，list的效率要远远高于vector，这是选择list的原因。

#pragma once
#include <vector>
#include <list>
//我们采用像Stack一样的方式  来模拟实现Queue
//queue的模拟实现  不建议使用vector
//因为vector采用了尾插和头删
//尾插的效率和list没有区别  但是头删就不一样了
//要不断地挪动数据 效率十分低

//stack之所以可以采用vector是因为stack只涉及
//尾部的操作 因此可以使用list和vector两个
namespace bit
{
	template<class T, class Container = list<T>>
	class Queue
	{
	public:
		bool empty()
		{
			return _con.empty();
		}

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

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

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

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

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

	private:
		Container _con;
	};

}

测试代码：

#include <iostream>

using namespace std;

#include <stack>
#include <queue>

#include "Queue.h"
void test_queue()
{
	//bit::Queue<int, list<int>> q;
	bit::Queue<int> q;
	
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);		//队头至队尾是1 2 3 4

	while (!q.empty())
	{
		cout << "size:" << q.size() << endl;
		cout <<"front:" << q.front() << " ";
		cout << "back:" << q.back() << " ";
		cout << endl;
		q.pop();
	}

}


int main()
{
	test_queue();
	
	return 0;
}