C++ stack and queue

4.4 deque的缺陷

4.5 为什么选择deque作为stack和queue的底层默认容器？

4.6 STL标准库中对于stack和queue的模拟实现

4.6.1 stack.h

#pragma once
#include<deque>
namespace sy
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

	private:
		Container _con;
	};
}

4.6.2 queue.h

#pragma once
#include<deque>

namespace sy
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

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

	private:
		Container _con;
	};
}

5.priority_queue

5.1 priority_queue介绍

cplusplus.com/reference/queue/priority_queue/#google_vignette

priority_queue 是 C++ 标准库中的一种容器适配器，基于堆数据结构实现，用于高效管理具有优先级的元素。默认情况下，元素按从大到小的顺序排列（大顶堆），但可以通过自定义比较器调整排序方式。

• 底层实现：通常基于 vector 或 deque 实现，使用堆算法维护优先级。
• 时间复杂度：插入和删除操作的时间复杂度为 O(log n)，访问顶部元素为 O(1)。
• 默认排序：std::less<T> 导致大顶堆（最大值在顶部），可通过 std::greater<T> 改为小顶堆。

5.1.2 priority_queue的使用

priority_queue - C++ Reference

 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

#include <iostream>
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
using namespace std;
class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d)
	{
		_cout << d._year << "-" << d._month << "-" << d._day;
		return _cout;
	}
private:
	int _year;
	int _month;
	int _day;
};
void TestPriorityQueue()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2025, 10, 29));
	q1.push(Date(2025, 10, 28));
	q1.push(Date(2025, 10, 30));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2025, 10, 29));
	q2.push(Date(2025, 10, 28));
	q2.push(Date(2025, 10, 30));
	cout << q2.top() << endl;
}

int main()
{
	TestPriorityQueue();
	return 0;
}
//运行结果：
//2025 - 10 - 30
//2025 - 10 - 28

5.2 仿函数介绍（简单）

仿函数：本质是一个类，这个类重载operator(),它的对象可以像函数一样使用，使用时候需要包含<functional>。

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

5.2.1 使用

#include <iostream>
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
using namespace std;
void TestPriorityQueue()
{
	// 默认情况下，创建的是大堆，其底层按照小于号比较
	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1;
	for (auto& e : v)
		q1.push(e);
	cout << q1.top() << endl;//9
	// 如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	cout << q2.top() << endl;//0

	// 如果要创建大堆，将第三个模板参数换成less比较方式
	
	//priority_queue<int, vector<int>, less<int>> q2(v.begin(), v.end());

}

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

5.3 priority_queue 模拟实现

5.3.1 priority_queue.h

#pragma once

#include<vector>

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

namespace sy
{
	// 默认是大堆
	template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

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

			AdjustUp(_con.size() - 1);
		}

		void AdjustDown(int parent)
		{
			// 先假设左孩子小
			size_t child = parent * 2 + 1;

			Compare com;
			while (child < _con.size())  // child >= n说明孩子不存在，调整到叶子了
			{
				// 找出小的那个孩子
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}

		const T& top()
		{
			return _con[0];
		}

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

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

	private:
		Container _con;
	};
}

5.4 OJ 使用

215. 数组中的第K个最大元素 - 力扣（LeetCode）

class Solution {
public:
int findKthLargest(vector<int>& nums, int k) 
{
    // 将数组中的元素先放入优先级队列中
    priority_queue<int> p(nums.begin(), nums.end());
    // 将优先级队列中前k-1个元素删除掉
    for(int i= 0; i < k-1; ++i)
    {
        p.pop();
    }
    return p.top();
    }
};

主持人调度（二）_牛客题霸_牛客网

class Solution
{
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) 
    {
        sort(startEnd.begin(), startEnd.end());
        priority_queue<int, vector<int>, greater<int>> heap; // 创建⼀个⼩根堆
        heap.push(startEnd[0][1]); // 先把第⼀个区间放进去
        for(int i = 1; i < n; i++) // 处理剩下的区间
        {
            int a = startEnd[i][0], b = startEnd[i][1];
            if(a >= heap.top()) // 没有重叠
            {
                heap.pop();
                heap.push(b);
            }
            else // 有重叠
            {
                heap.push(b); // 重新安排⼀个⼈
            }
        }
        return heap.size();
    }
};

5.5 test.cpp

#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

#include"Stack.h"
#include"Queue.h"
#include"PriorityQueue.h"

int main()
{
	//sy::stack<int, list<int>> st;
	sy::stack<int, vector<int>> st;

	// 类模板实例化时，按需实例化，使用哪些成员函数就实例化哪些，不会全实例化
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);

	cout << st.top() << endl;
	st.pop();

	//sy::queue<int, list<int>> q;
	sy::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	cout << q.front() << endl;
	q.pop();

	return 0;
}

void test_op1()
{
	srand(time(0));
	const int N = 1000000;

	deque<int> dq;
	vector<int> v;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		v.push_back(e);
		dq.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	sort(dq.begin(), dq.end());
	int end2 = clock();

	printf("vector:%d\n", end1 - begin1);
	printf("deque:%d\n", end2 - begin2);
}

void test_op2()
{
	srand(time(0));
	const int N = 1000000;

	deque<int> dq1;
	deque<int> dq2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		dq1.push_back(e);
		dq2.push_back(e);
	}

	int begin1 = clock();
	sort(dq1.begin(), dq1.end());
	int end1 = clock();

	int begin2 = clock();
	// 拷贝到vector
	vector<int> v(dq2.begin(), dq2.end());
	sort(v.begin(), v.end());
	dq2.assign(v.begin(), v.end());
	int end2 = clock();

	printf("deque sort:%d\n", end1 - begin1);
	printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}

int main()
{
	test_op2();

	return 0;
}

int main()
{
	//priority_queue<int> pq;
	sy::priority_queue<int, vector<int>, Greater<int>> pq;
	//sy::priority_queue<int> pq;
	pq.push(4);
	pq.push(1);
	pq.push(5);
	pq.push(7);
	pq.push(9);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

	return 0;
}

 //仿函数：本质是一个类，这个类重载operator(),他的对象可以像函数一样使用
//template<class T>
//class Less
//{
//public:
//	bool operator()(const T& x, const T& y)
//	{
//		return x < y;
//	}
//};
//
//template<class T>
//class Greater
//{
//public:
//	bool operator()(const T& x, const T& y)
//	{
//		return x > y;
//	}
//};

 //< 升序
 //> 降序
template<class Compare>
void BubbleSort(int* a, int n, Compare com)
{
	for (int j = 0; j < n; j++)
	{
		// 单趟
		int flag = 0;
		for (int i = 1; i < n - j; i++)
		{
			//if (a[i] < a[i - 1])
			if (com(a[i], a[i - 1]))
			{
				swap(a[i - 1], a[i]);
				flag = 1;
			}
		}

		if (flag == 0)
		{
			break;
		}
	}
}

int main()
{
	Less<int> LessFunc;
	Greater<int> GreaterFunc;
	// 函数对象
	cout << LessFunc(1, 2) << endl; 
	cout << LessFunc.operator()(1, 2) << endl;

	int a[] = { 9,1,2,5,7,4,6,3 };
	BubbleSort(a, 8, LessFunc);
	BubbleSort(a, 8, GreaterFunc);

	BubbleSort(a, 8, Less<int>());
	BubbleSort(a, 8, Greater<int>());

	return 0;
}
//运行结果
//1
//1