十分钟之内实现stack和queue？容器适配器是什么？priority_queue不是队列？

stack，queue，priority的模拟实现

一、栈和队列的特性（图解）🐬

​ 学过数据结构的同学们都知道，LIFO–后进先出,FIFO–先进先出

栈

队列

​

那大家想过为什么那些大佬们设计出来这两种结构呢？我们回顾一下vector和list

二、回顾vector和list的优缺点🕊

vector的底层原理是一个动态数组

vector的优势：

1. 尾插尾删的效率很高
2. 支持大量的随机访问（下标访问法）

vector的劣势：

1. 头插头删，中间插中间删的效率低，需要挪动数据
2. 入栈时，涉及到增容也会影响程序效率

list的底层原理是不同空间的结点，通过prev和next联系起来

list的优势：

1. 支持任意位置的O(1)的插入与删除
2. 不存在增容的情况

list的劣势：

1. 不支持随机访问
2. 空间不连续，相比与空间连续的容器效率是存在差异的

大家可以看到，vector与list是一个互补的结构，而且各有优势，而stack的特性正好是利用了vector的优势，避免了vector的劣势

queue的特性利用了list的优势，避免了list的劣势。

我的理解就是，严格要求stack和queue保持FIFO，LIFO的特性，是因为要完美地利用优势，从而提高程序的效率。做出要求，就像那种达到扬长避短的效果。

三、什么是容器适配器🐱‍👤

容器适配器的概念

​ 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

​ 大家重点关注上述加粗的文字。

​ C++官方文档里面也提到，stack与queue叫做容器适配器（container adaptor）

​ 不知道大家有没有这种疑问，明明vector和list都已经实现了，为什么还有实现stack和queue呢？stack和queue明明就是vector与list的一个小分支。严重破坏了懒人的三观。我马爹也表示不同意。

思考：能否利用已有的类来实现stack和queue的功能呢（也可以叫做复用）？

答案是：可以的，这也是为什么stack和queue被叫做容器适配器的原因。

四、十分钟之内模拟实现stack和queue👻

​ 没错，你没用听错，stack和queue的实现是只需要十分钟的，大家如果稍微理解了一点容器适配器，下面就开始实操。

stack的模拟实现

template<class T,class container = vector<T>>
class stack
{
public:
    void push(const T val)//尾插
    {
        _con.push_back(val);
    }

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

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

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

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



private:
    container _con;
};

​ 大家看到模板类型的既可以是int和double和string，而且还可以是vector和list的那些类。

而且stack的私用成员是vector。说的通俗易懂一点：我们这个stack就是vector的一个包装。stack的push使用了vector的push_back

queue的模拟实现

template<class T,class container = list<T>>
class queue
{
public:
    void push(const T& val)
    {
        _con.push_back(val);
    }

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

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

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

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

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

private:
    container _con;
};

​ 我们queue是list的一个包装。

​ 利用了已有的类通过一些接口和包装即可实现了另一个新的类，懒人狂喜。

​

​ 当然了，可能有些同学会发现，博主我咋看C++官网文档的的原装类不是vector和list呢，而是deque呢？因为容器适配器是很灵活的，并不是说你非得用vector去包装stack，你还可以用list去包装stack。那具体deque是什么，由于deque其结构，咱们会在后面的文章进行更新，敬请期待！

五、priority_queue（优先级队列）–硬菜来喽🐻

​ 有些同学可能会疑惑了，优先级队列是什么，是个什么队列呢？这里要强调的是，优先级队列可不是队列哦，包括deque也不是队列，只有queue才是队列

​ 优先级队列–看名字里面可能是有优先级的，其实也就是说谁的优先级高，谁就先出来。不再满足FIFO。

可以是大的优先级高，也可以是小的优先级高。

priority_queue的用法

void test_priority_queue()
{
	vector<int> v{ 2,5,4,7,6,5,8,9,10,5,6,3 };
	priority_queue<int> q1;
    
	for (const auto& x : v)
	{
		q1.push(x);
	}

	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl;
}

​ 由于容器设计时的灵活性和通用性，大部分容器的用法很相似，大家可以使用以下priority_queue，来了解以下priority_queue的用法以及性质。

​ C++文档里面，模板里面可以看到的信息是：

1. priority_queue–也是一个容器适配器
2. 相比stack和queue，模板里面多了一样东西

仿函数（函数对象）

​ 仿函数，顾名思义，函数的仿制品，其实它并不是函数。

下面是截取的一段运算符的图表。

大家看一看圆括号()，这个运算符的作用很多

1. 可以作为函数调用的标志
2. 也可以作为一个表达式,(1+2)*3，使得左边得表达式先计算加法。

那如果我们在一个类里面重载了一个operator()，是不是也可以使用上述得函数调用得功能了。函数对象得名字也由此产生。

代码演示：

template<class T>
struct less
{
    bool operator()(const T& l, const T& r)
    {
        return l < r;
    }
};


template<class T>
struct greater
{
    bool operator()(const T& l, const T& r)
    {
        return l > r;
    }
};

less类和greater类里面重载了operator()，那就有了下面得用法了。

void test_function_object()
{
	int a = 2, b = 3;
	double c = 2.2, d = 3.3;
	Less<int> comparei;
	cout << comparei(a, b) << endl;
	Less<double> compared;
	cout << compared(c, d) << endl;
    
    greater<int> comparei;
	cout << comparei(a, b) << endl;
	greater<double> compared;
	cout << compared(c, d) << endl;
}

​ 但是上述例子我们丝毫没有体会到仿函数得作用，明明可以设计一个函数模板，直接使用函数来实现相应的功能。仿函数显得多此一举了。仿函数被设计出来得另一个原因是，函数指针得类型很复杂，当我们向将一个函数指针作为参数上传时，发现其写法很复杂（这也时c语言得不足之处），而类就不用担心了，写法就非常简单明了

​ 具体priority_queue为什么要用仿函数，我们待会儿实现时再细说

priority_queue的实质

​ priority_queue的pop顺序要么是大的先出，要么是小的先出，也就是一个是降序，一个是升序。

而还有一个结构也可以满足这个特点堆，大堆–大的优先级高，小堆–小的优先级高

​ 也就是priority_queue和堆一样，其原理就是一颗完全二叉树，底层结构呢就是一个数组

上述的大小堆在vector的存储方式如下：

六、priority_queue的模拟实现🦄

基本架构

template<class T,class container = vector<T>>//priority_queue的底层，空间适配器是vector
	class priority_queue
	{
	public:
		//…………
	private:
		container _con;
	};

push()–插入

​ 要实现大堆，小堆的功能，

1. 尾插
2. 继续向上调正，保持大堆小堆的形态。

void AdjustUp(size_t child)
{
    while (child > 0)//到了根节点，循环结束
    {
        size_t parents = (child - 1) / 2;
        if (_con[parents] > _con[child])
        {
            swap(_con[parents], _con[child]);
            child = parents;
        }
        else//父亲比孩子小，就不变
        {
            break;
        }
    }
}

void push(const T& val)
{
    _con.push_back(val);
    size_t child = _con.size() - 1;
    AdjustUp(child);
}

pop()–删除

​ 如果我们直接删除头部的数据，由于vector不支持头删，那么调正起来会非常的麻烦。

解决方法：

1. 先将头部数据与尾部数据进行交换
2. 尾删
3. 向下调正，保持大小堆的形态

父亲找孩子的公式：

leftchild = parents*2+1

rightchild = parents*2+2

void AdjustDown(size_t parents)
{
    size_t child = parents * 2 + 1;//左孩子
    while (child < _con.size())
    {//千万注意：有可能是不存在右孩子的--所以会存在越位
        if (child + 1 < _con.size() && _con[child] > _con[child + 1])//找到最小孩子
        {
            ++child;
        }

        if (_con[parents] > _con[child])
        {
            swap(_con[parents], _con[child]);
            parents = child;
            child = parents * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

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

empty(),size(),top()

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

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

T top()//堆顶元素
{
    return _con[0];
}

迭代器区间构造

priority_queue()//无参构造函数
{}

//由于模板和typedef的结合，想正常使用container这个类要加上typename
priority_queue(typename container::iterator begin,typename container::iterator end)//迭代器区间构造函数
{
    typename container::iterator it = begin;
    while (it != end)
    {
        push(*it);
        ++it;
    }
}

还存在一个问题，我们这个实现的是一个小堆，在实现里面我们使用的是>，而小堆还没有实现，这个时候仿函数就排上用场了

完整代码

namespace kcc
{
	//开始实现仿函数
	template<class T>
	struct less//注意less是降序
	{
		bool operator()(const T& l, const T& r)
		{
			return l < r;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)
		{
			return l > r;
		}
	};
	
	//less--大堆
	//greater--小堆
	template<class T,class container = vector<T>,class compare = less<T>>//第三个模板
	class priority_queue
	{
	public:
		//compare是一个类，但是是对象使用operator()
		compare com;

		priority_queue()//无参构造函数
		{}
		//由于模板和typedef的结合，想正常使用container这个类要加上typename
		priority_queue(typename container::iterator begin,typename container::iterator end)//迭代器区间构造函数
		{
			typename container::iterator it = begin;
			while (it != end)
			{
				push(*it);
				++it;
			}
		}

		void AdjustUp(size_t child)
		{
			while (child > 0)//到了根节点，循环结束
			{
				size_t parents = (child - 1) / 2;
				if (com(_con[parents] , _con[child]))
				{
					swap(_con[parents], _con[child]);
					child = parents;
				}
				else//父亲比孩子小，就不变
				{
					break;
				}
			}
		}

		void AdjustDown(size_t parents)
		{
			size_t child = parents * 2 + 1;//左孩子
			while (child < _con.size())
			{//千万注意：有可能是不存在右孩子的--所以会存在越位
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))//找到最小孩子
				{
					++child;
				}

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



		void push(const T& val)
		{
			_con.push_back(val);
			size_t child = _con.size() - 1;
			AdjustUp(child);
		}

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

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

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

		T top()//堆顶元素
		{
			return _con[0];
		}


	private:
		container _con;
	};
}

​ 第三个模板我们传入了一个类，然后在里面定义了一个类对象就可以使用仿函数了，>,<的功能就可以通过传入的类的不同来实现了，上述给了缺省值，默认是大堆，想要实现小堆可以在传参的时候自己传入即可。

温馨提示：

1. 这里很容被弄晕，大堆我们传入的类是less
2. 小堆传入的是greater

这里可能会有很多人吐槽为什么要这么设计，确实我也想吐槽，不过库里面就是这样设计的。

要硬圆的话，大家就这样记吧，

大堆是降序（大的优先级高）使用less

小堆是升序（小的优先级高）：使用greater

七、课后练习的OJ题目连接–还请同学们一定要去做OJ题🤖

1. 155. 最小栈 - 力扣（LeetCode）
2. 栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
3. 150. 逆波兰表达式求值 - 力扣（LeetCode）
4. 232. 用栈实现队列 - 力扣（LeetCode）
5. 225. 用队列实现栈 - 力扣（LeetCode）
6. 215. 数组中的第K个最大元素 - 力扣（LeetCode）

八、总结🐡

​ 这篇文章主要还是已容器适配器的基础来模拟实现stack和queue，大家也可以看到容器适配器并不全是由一个类调用几个接口

就可以实现，有些容器适配器还是需要很多调整的的就像priority_queue。

还希望这篇文章可以帮到大家！