【C++进阶】深入STL之 栈与队列：数据结构探索之旅

void test_stack()
{
	stack<int, vector<int>> st; // 构造栈
	st.push(1); // 将元素val压入stack中
	st.push(2);
	st.push(3);
	st.push(4);
	printf("栈中有效元素个数为：%d", st.size()); // 返回stack中元素的个数
	while (!st.empty()) // 检测stack是否为空
	{
		printf("%d ", st.top()); // 返回栈顶元素的引用
		st.pop(); // 将stack中尾部的元素弹出
	}
}

void test_queue()
{
	queue<int, list<int>> q; // 构造队列
	q.push(1); // 在队尾将元素val入队列
	q.push(2);
	q.push(3);
	q.push(4);
	printf("队列中有效元素个数为：%d", q.size()); // 返回stack中元素的个数
	while (!q.empty()) // 检测queue是否为空
	{
		printf("%d ", q.front()); // 返回队头元素
		q.pop(); // 将队头元素出队列
	}
}

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()
	{
		return _con.back();
	}
	bool empty()
	{
		return _con.empty();
	}
	size_t size()
	{
		_con.size();
	}
private:
	Container _con;
};

template<class T, class Container = deque<T>>
class queue
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}
	void pop()
	{
		_con.pop_front();
	}
	bool empty()
	{
		return _con.empty();
	}
	const T& front()
	{
		return _con.front();
	}
	size_t size()
	{
		_con.size();
	}
private:
	Container _con;
};

void test_priority_queue()
{
	std::priority_queue<int> q; // 构造优先级队列
	q.push(1); // 在优先级队列中插入元素x
	q.push(43);
	q.push(233);
	q.push(43);
	q.push(4);
	q.push(73);
	q.push(2);
	while (!q.empty()) // 检测优先级队列是否为空
	{
		printf("%d ", q.top()); // 返回堆顶元素
		q.pop(); // 删除堆顶元素
	}
}

// 仿函数，数据的比较方法
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 T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
	priority_queue() // 无参构造
	{}

	template<class InputIterator>
	priority_queue(InputIterator first, InputIterator last) // 迭代器构造
		:_con(first,last)
	{
		// 向下调整建堆
		for (int i = (_con.size() - 2) / 2; i >= 0; i--)
		{
			AdjustDown(i);
		}
	}
	void AdjustUp(int child) // 向上调整
	{
		int parent = (child - 1) / 2;
		Compare com;
		while (child > 0)
		{
			if (com(_con[child], _con[parent]))
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
	void AdjustDown(int parent) // 向下调整
	{
		int child = parent * 2 + 1;
		Compare com;
		while (com(child , _con.size()))
		{
			if ((child + 1 < _con.size()) &&
				com(_con[child + 1], _con[child]))
			{
				child++;
			}
			if (com(_con[child] , _con[parent]))
			{
				swap(_con[child], _con[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
	void push(const T& x)
	{
		_con.push_back(x);
		AdjustUp(_con.size() - 1); // 在插入新元素时，我们要调整容器里面的元素
	}
	size_t size()
	{
		return _con.size();
	}
	const T& top()
	{
		return _con[0];
	}
	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back(); 
		AdjustDown(0); // 删除时，依旧要调整元素
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};