C++初阶 —— stack/queue

本文主要是介绍C++初阶 —— stack/queue，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

一，容器适配器

deque双端队列

二，stack栈

stack接口

stack模拟实现

三，queue队列

queue接口

queue模拟实现

四，priority_queue优先级队列

priority_queue接口

priority_queue模拟实现

注：Date*，无法转化为const Date* &；

一，容器适配器

• 适配器是一种设计模式，该模式是将一个类的接口转换成用户希望的另一个接口；
• 虽然stack、queue中可以存元素，但在STL中并没有划为容器行列，而是将其称为容器适配器；这是因为他们只是对其他的接口进行了包装，STL中stack、queue默认的底层容器为deque；

deque双端队列

• 是一种双开口的“连续”空间的数据结构；
• 双开口，即头尾两端都可高效插入和删除操作，时间复杂度为O(1)；
• “连续”空间，其实并非真正的连续空间，而是由一段段连续的小空间拼接而成，类似于一个动态的二维数组；
• 与vector比较，头插效率高，无需挪动数据；vector的cpu高速缓存命中率高，但增容代价大且存在空间浪费；
• 与list比较，空间利用率较高；list按需申请或释放空间，任意插入删除效率高，不支持随机访问，cpu高速缓存命中率低；

优缺点

• 非常适合头插/尾插，头删/尾删，默认适合做stack/queue适配器；
• 中间插入/删除数据非常麻烦，效率不高；
• 不适合遍历，遍历时迭代器要频繁的检测是否到达边界；
• deque可以说是一种折中的方案，随机访问不及vector，任意位置插入删除不及list；

 注：

• stack是一种LIFO的特殊线性数据结构，只要满足尾插尾删操作均可作为其底层容器，如vector、list；
• queue是一种FIFO的特性线性数据结构，只要满足尾插头删操作均可作为底层容器，如list；
• stack、queue默认选择deque作为其底层容器，是因为stack、queue没有迭代器无需遍历，只要在一端或两端操作即可，stack增容时deque比vector效率高不需要大量挪动数据，queue元素增长时，不仅效率高，且内存使用率也高；

int main()
{
	deque<int> dq;
	dq.push_back(1);
	dq.push_back(2);
	dq.push_front(3);
	dq.push_front(4);
	cout << dq[0] << endl;
	cout << dq.front() << endl;
	cout << dq.back()<< endl;
	dq.pop_back();
	dq.pop_front();

	deque<int>::iterator it = dq.begin();
	while (it != dq.end())
	{
		cout << *it << " ";
		++it;
	}
	return 0;
}

二，stack栈

• stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，只能从容器的一端进行元素的插入与提取操作；
• stack是作为容器的适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层，元素在特定容器尾部即栈顶被压入和弹出；
• 底层容器可以是任何标准的容器类模板或其他特定的容器类，这些容器类应支持，empty、back、push_back、pop_back操作；
• 标准容器vector、deque、list均符号要求，如stack未指定特定的底层容器，默认使用deque；

stack接口

• stack()，构造空栈；
• empty()，判断释放为空栈；
• size()，返回元素个数；
• top()，返回栈顶元素个数；
• push()，压入元素；
• pop()，弹出元素；

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.top();
	st.pop();
	st.size();
	st.empty();
	return 0;
}

stack模拟实现

template <class T, class container = deque<T>>
class stack
{
public:
	void push(const T& val)
	{
		_con.push_back(val);
	}
	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;
};

int main()
{
	stack<int, list<int>> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	return 0;
}

三，queue队列

• queue是一种容器适配器，专门用于在先进先出中操作，其中从容器一端插入元素，另一端提取元素；
• 队列作为容器适配器实现，容器适配器即将特定容器封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从队尾入队列，从对头出队列；
• 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类，该底层容器应至少支持，empty、size、front、back、push_back、pop_front操作；
• 标准容器类deque和list默认要求，如queue没有实例化指定容器类，默认使用deque；

queue接口

• queue()，构造空队列；
• empty()，判断释放为空栈；
• size()，返回有效元素个数；
• front()，返回对头元素引用；
• back()，返回队尾元素引用；
• push()，在队尾将元素入队列；
• pop()，将对头元素出队列；

int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.front();
	q.back();
	q.pop();
	q.size();
	q.empty();
	return 0;
}

queue模拟实现

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

int main()
{
	queue<int, list<int>> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	while (!st.empty())
	{
		cout << st.front() << " ";
		st.pop();
	}
	return 0;
}

四，priority_queue优先级队列

• 优先级队列，默认使用vector作为底层容器；
• vector上使用堆算法，将元素构造成堆结构；
• 优先级队列其实是堆，默认为大堆；

priority_queue接口

• priority_queue()，构造空优先级队列；
• priority_queue(InputIterator first，InputIterator last)，用指定范围构造优先级队列；
• push，插入元素；
• pop，删除堆顶元素；
• top，返回堆顶元素；
• size，返回有效元素个数；
• empty，检测是否为空；

int main()
{
	vector<int> v = { 1,2,3,4 };
	priority_queue<int> pq(v.begin(), v.end());
	pq.push(3);
	pq.push(5);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

priority_queue模拟实现

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)
	{
		while (first != last)
		{
			push(*first);
			++first;
		}
	}

	void push(const T& val)
	{
		_con.push_back(val);
		AdjustUp(_con.size() - 1);
	}
	void pop()
	{
		std::swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		AdjustDown(0);
	}
	const T& top()const
	{
		return _con.front();
	}
	size_t size()const
	{
		return _con.size();
	}
	bool empty()const
	{
		return _con.empty();
	}

	void AdjustDown(size_t parent)
	{
		size_t child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && compare()(_con[child], _con[child + 1]))
				child++;
			if (compare()(_con[parent], _con[child]))
			{
				std::swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}
	void AdjustUp(size_t child)
	{
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (compare()(_con[parent], _con[child]))
			{
				std::swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}

private:
	container _con;
};

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;
	}
};

注，嵌套依赖名字需添加关键字typename

template<class container>
void print(const container& con) 
{
	//无法确定container::iterator是类型，还是静态成员变量
	//需在前添加typename
	typename container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		++it;
	}
}

附，自定义compare仿函数，控制比较结果；

class Date
{
	friend ostream& operator<<(ostream& _cout, const Date& d);
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& date) const
	{
		return (_year < date._year) ||
			(_year == date._year && _month < date._month) ||
			(_year == date._year && _month == date._month && _day < date._day);
	}
	bool operator>(const Date& date) const
	{
		return (_year > date._year) ||
			(_year == date._year && _month > date._month) ||
			(_year == date._year && _month == date._month && _day > date._day);
	}
private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& _cout, const Date& date)
{
	_cout << date._year << "-" << date._month << "-" << date._day << endl;
	return _cout;
}

//自定义compare仿函数，控制比较结果
class pDateLess
{
public:
	bool operator()(const Date* pdate1, const Date* pdate2) 
	{
		return *pdate1 < *pdate2;
	}
};

int main()
{
	priority_queue<Date*, vector<Date*>, pDateLess> pq;
	pq.push(new Date(2000, 1, 1));
	pq.push(new Date(2001, 1, 1));
	pq.push(new Date(2002, 1, 1));
	while (!pq.empty())
	{
		cout << *pq.top();
		pq.pop();
	}
	return 0;
}

注：Date*，无法转化为const Date* &；

//const Date*&，是对类型const Date*的引用
//但实际传递的类型为Date*，无法转化为const Date* &
bool operator()(const Date*& pdate1, const Date*& pdate2) 
{
	return *pdate1 < *pdate2;
}

这篇关于C++初阶 —— stack/queue的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！