STL之stack、queue、priority-创新互联

容器适配器

  容器适配器，简言之是可以用不同容器来快速实现自己的工具。像stack、queue、priority_queue都是容器适配器。

网站建设哪家好，找创新互联！专注于网页设计、网站建设、微信开发、微信小程序、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了右江免费建站欢迎大家使用！stack模拟实现

• 主要接口定义如下：

namespace lz
{template>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() const
		{	return _con.size();
		}
		//判断栈是否为空
		bool empty() const
		{	return _con.empty();
		}
		//交换两个栈中的数据
		void swap(stack& st)
		{	_con.swap(st._con);
		}
	private:
		Container _con;
	};
}
分析：
  1. 因为是容器适配器，所以我们用容器模板参数即可。如果使用库中的原生stack，底层容器是deque（queue也一样）。

+ 构造函数和析构函数：
  因为使用容器，所以内部不需要自己申请任何空间，扩容等一系列问题都不需要考虑。

+ push：
  栈push需要给容器底部插，所以用push_back()。
```cpp
// push：const T& x：用_con做push，也就是deque，const保护，&防止改变
void push(const T& x)
{_con.push_back(x);	// _con.push_back();
}

• pop：
  涉及出栈，要删最后一个，所以pop_back()。

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

• top：

// top：T& 是因为我们调用的deque使用了back()，back()可以改变，所以deque的back()返回值本身是个引用，所以这里可以使用引用，且我们要的就是得到top()也能做修改。
T& top()
{return _con.back();
}

• size：
  _con的size。

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

• empty：

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

stack完整代码

//#pragma once
//#include//#include//using namespace std;
//
//namespace lz
//{//	template>//	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() const
//		{//			return _con.size();
//		}
//		//判断栈是否为空
//		bool empty() const
//		{//			return _con.empty();
//		}
//		//交换两个栈中的数据
//		void swap(stack& st)
//		{//			_con.swap(st._con);
//		}
//	private:
//		Container _con;
//	};
//}
 // cpp
//#include"l3stack.h"
//
//int main()
//{//    lz::stackst;
//    st.push(1);
//    st.push(2);
//    st.push(3);
//    st.push(4);
//    st.push(5);
//    cout<< "st.size() = "<< st.size()<< endl;
//    while (!st.empty())
//    {//        cout<< st.top()<< " ";
//        st.pop();
//    }
//    
//    return 0;
//}

queue模拟实现

• queue的主要接口：

template>class queue

  {public:

    queue();

    void push(const T& x);

    void pop();

    T& back();

    const T& back()const;

    T& front();

    const T& front()const;

    size_t size()const;

    bool empty()const;

  private:

    Con _c;

  };

};

• queue和stack的区别
    区别在queue有front()、back()和queue的pop()必须出头。
• pop()

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

• front()

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

• back()

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

queue完整代码

//#pragma once
//#include//#include//#include//using namespace std;
//
//namespace lz
//{//	template>//	class queue
//	{//	public:
//		//元素入栈
//		void push(const T& x)
//		{//			_con.push_back(x);
//		}
//		//元素出栈
//		void pop()
//		{//			_con.pop_front();
//		}
//
//		T& back()
//		{//			return _con.back();
//		}
//
//		T& front()
//		{//			return _con.front();
//		}
//
//		//获取栈顶元素
//		T& top()
//		{//			return _con.back();
//		}
//		
//		//获取栈中有效元素个数
//		size_t size() const
//		{//			return _con.size();
//		}
//		//判断栈是否为空
//		bool empty() const
//		{//			return _con.empty();
//		}
//		//交换两个栈中的数据
//		void swap(queue& q)
//		{//			_con.swap(q._con);
//		}
//	private:
//		Container _con;
//	};
//}

// queue.cpp
//#include"l3queue.h"
//
//int main()
//{//    lz::queue>q;
//    q.push(1);
//    q.push(2);
//    q.push(3);
//    q.push(4);
//    cout<< "queue.size = "<< q.size()<< endl;
//    while (!q.empty())
//    {//        cout<< q.front()<< endl;
//        q.pop();
//    }
//
//    return 0;
//}

priority_queue模拟实现

• 关于原生priority_queue：
    STL原生底层实现使用：默认是大根堆，仿函数是：less<>。且底层数据结构是：vector，因为拿数组建堆方便。
  用法如下：

priority_queue, less>q1;

• 全部代码：

#pragma once
#include#includeusing namespace std;

// 默认是大根堆，就写大根堆
namespace lz
{// 仿函数：
	templateclass less
	{public:
		bool operator()(const T& l, const T& r)const
		{	return l< r;
		}
	};

	templateclass greater
	{public:
		bool operator()(const T& l, const T& r)const
		{	return l >r;
		}
	};

	// compare：进行比较的仿函数
	template, class Compare = std::less>class priority_queue
	{public:
		void adjust_up(size_t child)
		{	Compare com;
			int parent = (child-1)/2;
			// 孩子>0也可
			while (parent >= 0)
			{		if (com(_con[parent], _con[child]))	// 大根堆，	调< :孩子>父亲，就换所以父亲在前面
				{std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}

		// 向下调整
		void adjust_down(size_t parent)
		{	Compare com;
			// 每次都用右孩子
			size_t child = parent * 2 + 1;
			// 允许孩子最多是 size-1 合理
			while (child< _con.size())
			{		// 右孩子存在且更大 则child 变右孩
				if (child + 1< _con.size() && com(_con[child], _con[child + 1]))	// 大根  比如 less<  ，小的放前面 ：
					child++;
				if (com(_con[parent], _con[child]))
				{std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}

		priority_queue()
		{	// 函数体不写就可以，
			// 会自动调用容器构造，
			// 但是不写不写，下面有迭代器构造函数
			// 编译器就不会自己生成pq的默认构造函数。
		}

		templatepriority_queue(InputIteartor first, InputIteartor last)
		{	// 迭代器模板中，会自动往后
			while (first != last)
			{		_con.push_back(*first);
				++first;
			}
			// 数组已经好了，但是不符合堆， 向下调整规范堆：从倒数第一个父节点开始到堆顶做向下调整 
			for (int i = (_con.size()-1-1)/2; i >= 0; --i)
			{		adjust_down(i);
			}
		}

		size_t empty()
		{	return _con.size() == 0;
		}

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

		void push(const T& x)
		{	_con.push_back(x);
			adjust_up(_con.size()-1);
		}

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

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

	private:
		Container _con;
	};
}

代码分析

• 1. 构造函数
       实现迭代器构造函数和无参的默认构造函数，因为我们写了迭代器构造函数，编译器发现你有自己写构造函数，就不会生成无参构造函数了，所以需要自己再写无参构造函数。
• 2. 仿函数less、greater

1. less用在大顶堆，使用<。
2. greater用在小顶堆，使用>。
3. 发现中文名字和大小顶堆的英文相反，而英文和符号又相符。

  仿函数都使用模板参数，重载()。重载()是规定，这个仿函数起比较作用，返回值即可。

• 3. 向上向下调整算法

void adjust_up(size_t child)
{Compare com;
	int parent = (child-1)/2;
	// 孩子>0也可
	while (parent >= 0)
	{if (com(_con[parent], _con[child]))	// 大根堆，	调< :孩子>父亲，就换所以父亲在前面
		{	std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

		// 向下调整
void adjust_down(size_t parent)
{Compare com;
	// 每次都用右孩子
	size_t child = parent * 2 + 1;
	// 允许孩子最多是 size-1 合理
	while (child< _con.size())
	{// 右孩子存在且更大 则child 变右孩
		if (child + 1< _con.size() && com(_con[child], _con[child + 1]))	// 大根  比如 less<  ，小的放前面 ：
			child++;
		if (com(_con[parent], _con[child]))
		{	std::swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

  向上调整是给当前孩子位置，不断求爹，向上调。因为开头从1个节点开始，所以后续用向上调整都能使得堆条件满足。
  向下调整是给当前爹位置，不断求儿子，向下调。

• 4. 重要函数：
• push：给堆底尾插，然后向上调整。

void push(const T& x)
{_con.push_back(x);
	adjust_up(_con.size()-1);
	//adjust_down(_)
}

• pop：我们要做弹出堆顶，交换堆顶和最后一个元素，利用底层容器deque的pop_back()，相当于做了删尾，为什么用最后一个和堆顶交换，因为最后一个一定是比较小（大顶堆时，小顶堆相反），符合在叶子节点的条件，所以我们再做向下调整，

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

全部代码

#pragma once
#include#includeusing namespace std;

// 默认是大根堆，就写大根堆
namespace lz
{// 仿函数：
	templateclass less
	{public:
		bool operator()(const T& l, const T& r)const
		{	return l< r;
		}
	};

	templateclass greater
	{public:
		bool operator()(const T& l, const T& r)const
		{	return l >r;
		}
	};

	// compare：进行比较的仿函数
	template, class Compare = std::less>class priority_queue
	{public:
		void adjust_up(size_t child)
		{	Compare com;
			int parent = (child-1)/2;
			// 孩子>0也可
			while (parent >= 0)
			{		if (com(_con[parent], _con[child]))	// 大根堆，	调< :孩子>父亲，就换所以父亲在前面
				{std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}

		// 向下调整
		void adjust_down(size_t parent)
		{	Compare com;
			// 每次都用右孩子
			size_t child = parent * 2 + 1;
			// 允许孩子最多是 size-1 合理
			while (child< _con.size())
			{		// 右孩子存在且更大 则child 变右孩
				if (child + 1< _con.size() && com(_con[child], _con[child + 1]))	// 大根  比如 less<  ，小的放前面 ：
					child++;
				if (com(_con[parent], _con[child]))
				{std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}

		priority_queue()
		{	// 函数体不写就可以，
			// 会自动调用容器构造，
			// 但是不写不写，下面有迭代器构造函数
			// 编译器就不会自己生成pq的默认构造函数。
		}

		templatepriority_queue(InputIteartor first, InputIteartor last)
		{	// 迭代器模板中，会自动往后
			while (first != last)
			{		_con.push_back(*first);
				++first;
			}
			// 数组已经好了，但是不符合堆， 向下调整规范堆：从倒数第一个父节点开始到堆顶做向下调整 
			for (int i = (_con.size()-1-1)/2; i >= 0; --i)
			{		adjust_down(i);
			}
		}

		size_t empty()
		{	return _con.size() == 0;
		}

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

		void push(const T& x)
		{	_con.push_back(x);
			adjust_up(_con.size()-1);
			//adjust_down(_)
		}

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

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

	private:
		Container _con;
	};
}

==main.cpp==
#include"l4heap.h"
#includevoid testpq()
{lz ::priority_queue, greater>pq;
    //priority_queuepq;
    pq.push(3);
    pq.push(1);
    pq.push(2);
    pq.push(5);
    pq.push(0);
    pq.push(1);
    while (!pq.empty())
    {cout<< pq.top()<< " ";
        pq.pop();
    }
    
    cout<< endl<< "排序 a"<< endl;
    int a[] = {3, 2 , 1 , 4 , 56, 7 , 8, 4, 0 ,5 };
    lz::priority_queuepq2(a, a+ sizeof(a)/sizeof(int));
    while (!pq2.empty())
    {cout<< pq2.top()<<  " ";
        pq2.pop();
    }


}


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

练习题

寻找topK
优先队列只能通过把vector遍历一次全放进来才行。
这个题快排最好。
记忆一下STL规律：
队列类的如priority_queue、queue都只有pop()，而没有pop_back()，而其它的如vector、list、deque（它是双端，所以有尾删很正常）都是pop_back()，可以想象，一个vector数组，删尾巴容易删，删顶不好删，所以也不留这个接口。

• 选择题：
  下列代码的运行结果是（ ）
  int main()
  {
  priority_queue a;
  priority_queuec;
  priority_queue b;
  for (int i = 0; i< 5; i++)
  {
  a.push(i);
  c.push(i);
  }
  while (!a.empty())
  {
  cout<< a.top()<< ’ ';
  a.pop();
  }
  cout<< endl;
  while (!c.empty())
  {
  cout<< c.top()<< ’ ';
  c.pop();
  }
  cout<< endl;
  b.push(“abc”);
  b.push(“abcd”);
  b.push(“cbd”);
  while (!b.empty())
  {
  cout<< b.top()<< ’ ';
  b.pop();
  }
  cout<< endl;
  return 0;
  }
  A.4 3 2 1 0 0 1 2 3 4 cbd abcd abc
  B.0 1 2 3 4 0 1 2 3 4 cbd abcd abc
  C.4 3 2 1 0 4 3 2 1 0 abc abcd cbd
  D.0 1 2 3 4 4 3 2 1 0 cbd abcd abc
  其中，字典序：c>a，所以选ACD中一个，剩下都是大小堆判断，好说。

• 仿函数比起一般函数具有很多优点，以下描述错误的是( )
  A.在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态
  B.仿函数即使定义相同，也可能有不同的类型
  C.仿函数通常比一般函数速度快
  D.仿函数使程序代码变简单

   仿函数是一种模板函数，因为使用了模板，要做匹配、实例化等，速度比一般函数满。此外，仿函数定义相同， 也可以有不同类型，因为实例化后可以存不同类型值。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站栏目：STL之stack、queue、priority-创新互联
转载注明：http://cdxtjz.cn/article/dephsd.html