【C++】stack&和queue（stack、queue、priority_queue、deque）

stack

底层结构

stack是一种容器适配器，只能在容器的顶部进行元素的插入、删除和获取元素等操作。

接口使用

void Test1()
{
	stack<int> mystack;//构造空的栈
	mystack.push(1);//入栈
	mystack.push(2);
	mystack.push(3);
	size_t sz = mystack.size();//元素个数
	int t = mystack.top();//获取栈顶元素
	bool emp = mystack.empty();//判断栈是否为空
	mystack.pop();//出栈
	mystack.pop();
	mystack.pop();
	sz = mystack.size();
	emp = mystack.empty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

模拟实现stack

可以通过对vector进行封装得到栈

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

private:
	Container _con;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

queue

结构

queue（队列），是一种容器适配器，元素从容器一端进入队列，另一端出队列。

使用

void Test2()
{
	queue<int> myqueue;//创建空队列
	myqueue.push(1);//插入元素
	myqueue.push(2);
	myqueue.push(3);
	size_t sz = myqueue.size();//有效元素个数
	int t = myqueue.front();//队头元素
	int b = myqueue.back();//队尾元素
	bool em = myqueue.empty();//判断队列是否为空
	myqueue.pop();//出队列
	myqueue.pop();
}
1
2
3
4
5
6
7
8
9
10
11
12
13

模拟实现queue

使用list模拟实现queue

template<class T, class Coninter = list<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()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Coninter _con;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

priority_queue

底层结构

堆，即完全二叉树+条件限制（任意节点都要比孩子节点大\或任意节点都比孩子节点小）
优先级队列的实现是：vector和堆算法，包括make_heap，push_heap，pop_heap

• 关于make_heap，push_heap，pop_heap的使用
  

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;
1
2

priority_queue的类模板参数，第一个参数表示堆中要保存的数据类型，第二个参数表示底层使用的容器，默认使用vector，第三个参数表示比较方式，即创建堆时两个节点数据比较的方式，默认按照小于的方式比较，创建的是大堆。

• 大堆
  
• 小堆
  

使用

内置类型

默认的比较方式创建的是大堆，如果要创建小堆，将第三个模板参数换成greater比较方式。

void Priotity_test()
{
	vector<int> v{ 5,6,7,3,4,2,9,0,8 };
	priority_queue<int> q1;//构造一个空的堆，插入元素
	for (auto& e : v)
	{
		q1.push(e);
	}
	cout << q1.top() << endl;
	priority_queue<int> q2(v.begin(), v.end());//迭代器构造
	cout << q2.top() << endl;
	priority_queue<int, vector<int>, greater<int>> q3(v.begin(), v.end())//使用greater时包含functional头文件
	cout << q3.top() << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

自定义类型（传值）

以日期类为例，要在优先级队列的节点中保存日期类对象，则必须在日期类中对 ‘<’ 进行重载，因为less比较方式中会使用<比较两个节点元素大小：

如果没有进行重载，程序会报错：

在日期类中对<进行重载后，构造堆：

自定义类型（传指针）

上面的程序中都传递的是对象的值，而如果传递了对象的地址，则需要自己写比较方法，因为默认的比较方法只会调用 ‘<’ 或者 ‘>’ 赋值运算符的重载，而不会对接受的参数进行解引用。自己写比较方式又三种方法：函数指针、仿函数、lambda表达式

函数指针

因为要自己写比较方式，而模板参数默认的比较方式是less，如果只将比较方式的函数名作为参数传递，会导致模板参数类型与函数类型不匹配，所以需要将函数的类型作为模板的第三个参数。

函数对象

使用函数对象的关键是创建一个类，在类中对函数调用运算符()进行重载

Compare类：

class Compare
{
public:
	//对函数调用运算符()重载
	bool operator()(Date* d1,Date* d2)const
	{
		return * d1 < *d2;
	}
};
1
2
3
4
5
6
7
8
9

priority_queue模拟实现

成员变量

priority_queue底层所使用的容器，默认为vector

private:
	Container _c;
1
2

向下调整

如果当前节点有孩子节点，找到两个孩子中较大的一个，比较当前节点与孩子节点的大小，如果双亲结点比孩子节点小，则交换两个节点的值；如果当前节点比孩子节点大，则说明已经调整到合适的位置，下面的位置在之前已经调整为正确的顺序，不需要再判断，函数可以返回。

void AdjustDown(size_t parent)
{
	size_t child = parent * 2 + 1;//左孩子
	while (child < _c.size())
	{
		Com com;
		//找较大的孩子
		if (child + 1 < _c.size() && com(_c[child], _c[child + 1]))
		{
			child += 1;
		}
		if (com(_c[parent], _c[child]))
		{
			swap(_c[parent], _c[child]);
			parent = child;
			child = child * 2 - 1;
		}
		else
		{
			return;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

向上调整

找到当前节点的双亲结点，如果双亲结点比当前节点小，交换两个节点内容，并循环向上进行；当找到一个节点的双亲结点比当前节点大，则表明已经调整到位，函数可以退出。

void AdjustUp(size_t child)
{
	while (child)
	{
		Com com;
		size_t parent = (child - 1) / 2;
		if (com(_c[parent], _c[child]))
		{
			std::swap(_c[parent], _c[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			return;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

构造

构造空对象

priority_queue()
	:_c()
{ }
1
2
3

迭代器构造
迭代器的类型写成模板的形式，从倒数第一个非叶子节点开始进行向下调整

template<class Iterator>
priority_queue(Iterator first, Iterator last)
	:_c(first, last)
{
	int sz = _c.size();
	//找到倒数第一个非叶子节点
	//即最后一个节点的前一个节点的根节点
	int root = (sz - 2) / 2;
	while (root >= 0)
	{
		AdjustDown();
		root--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

deque

设计模式
STL标准库中用deque作为stack和queue的底层结构，所以stack和queue我们一般称为容器适配器，容器适配器是一种设计模式，设计模式即一套代码设计经验的总结，适配器这种设计模式是将一个类的接口转换成用户希望的另一个接口。

deque的底层结构

deque(Double Ended Queue)双端队列，是一种双开口的连续空间的数据结构，可以在头尾两端进行插入和删除，时间复杂度都为O(1).

deque底层并不是真正的连续空间，而是由一段段连续的小空间拼接而成，类似于一个动态的二维数组。

• map
  deque采用一块儿map作为主控，这里的map是一小块儿连续的空间，每个节点指向一段连续空间的首地址，如图：
  
• 迭代器
  cur：当前迭代器指向的元素的位置
  first：小段空间中起始位置
  last：小段空间末尾为之前
  node：map中本段地址存放的位置

• map与迭代器的关系
  deque能当作连续的空间进行使用，主要靠中控器map和迭代器iterator的配合使用来实现的
  如图，假设要保存的数据大小为20个字节，而每段空间大小为8字节，前两段空间放满，第三段空间放4字节；进行遍历时，迭代器从第一段空间的first增长到last，检测到空间边界，node指向map中下一个节点的位置，更新first、last和cur，再重复上面的步骤遍历第二段空间
  

deque的优缺点

优点

• 与vector相比，deque进行头插和头删时，不用搬移元素，效率较高。扩容时，也不需要拷贝旧空间的元素，只需要拷贝map保存的空间首地址即可。
• 与list相比，底层空间连续，缓存利用率较高；list中有prev和next，而deque不需要保存这些额外的字段。

缺点
不适合遍历，因为在遍历时，deque的迭代器需要频繁地检测是否移动到某段小空间的边界，导致效率低下。deque应用较少，一般只在STL中作为stack和queue地底层容器。

为什么选择deque作为stack和queue地底层容器

• stack和queue都不需要遍历，只在固定地一端或者两端进行插入和删除操作
• stack中元素增长时，deque相比于vector扩容效率更高，不需要搬移大量元素；对于queue，使用deque相比于list，不需要频繁地申请空间，且缓存利用率高（小段空间是连续的）。

使用deque模拟实现stack和queue时，原理与vector和list相同，只需要将底层容器换成deque即可。