一、栈（stack）和队列（queue）介绍和相关接口介绍

一、栈 —— 类比枪械弹匣
形象比喻
弹匣装填子弹时，后放进去的子弹排在最上方；射击取弹时，只能先打出最后装入的子弹。取放只能在同一开口操作，无法抽取中间子弹。
专业定义与特点
逻辑结构：线性数据结构
存取规则：后进先出 LIFO
操作端口：仅有栈顶一个出入口
核心操作
入栈：元素从栈顶添加
出栈：元素从栈顶删除
取栈顶：仅查看顶端元素，不删除
结构形态：一端封闭、一端开口，元素层层堆叠
常见应用
函数调用栈、表达式求值、括号匹配、浏览器后退功能
二、队列 —— 类比日常排队
形象比喻
商场、车站排队通行，最先排队的人最先办理业务，后来的人只能排在队尾，队伍中间无法插队、中途不能任意离场。
专业定义与特点
逻辑结构：线性数据结构
存取规则：先进先出 FIFO
操作端口：队尾入队、队首出队，两个独立端口
核心操作
入队：元素追加至队尾
出队：元素从队首移除
取队首：查看排头元素
结构形态：两端开放，元素单向依次移动

栈和队列数据取入相关示意图：

 

二、栈和队列各自相关接口介绍：

使用STL中的栈来实例化出对象，和vector类似，但是增加了一个模板参数，第一个代表村春数据类型，第二个代表底层容器类型，多余的参数是因为stack是容器适配器（queue也是如此，容器适配器后边讲解）

相关接口：

push(x):按照后进先出原则从栈顶放入元素

top():返回栈顶元素

pop():从栈顶删除一个元素

empty（）：返回一个布尔值，判断stack是否为空

size():返回栈中元素个数

使用STL中的queue时，也是有两个模板参数，和上面的栈相同

相关接口：

push():从队尾插入一个元素

pop(  ):从队头删除一个元素

front():返回队头的元素

back()：返回队尾的元素

empty():返回一个布尔值，判断队列是否为空

size():返回队列中元素的个数

相关使用接口代码演示：

 

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

void testStack()
{
	cout << "--------------test for stack---------------" << endl;
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	while (!st.empty())
	{
		int it = st.top();
		st.pop();
		cout << it << " ";
	}
	cout << endl;

	
}
void testQueue()
{
	cout << "-------------test for queue--------------" << endl;
    queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	while (!q.empty())
	{
	    cout <<"front:"<<q.front()<<"back:"<<q.back()<< " "<<endl;
		q.pop();
	}
	cout << endl;
	
}

int main()
{
	testStack();
	testQueue();
	
	
}

运行结果：

--------------test for stack---------------
5 4 3 2 1
-------------test for queue--------------
front:1back:5
front:2back:5
front:3back:5
front:4back:5
front:5back:5

值得注意的是stack和queue都不支持迭代器区间构造。

三、容器适配器

一、什么是 容器适配器？

容器适配器 = 改装壳

• 底层有一个通用容器（比如 vector、deque）
• 适配器限制它的行为，改成你想要的结构
• 它不是全新容器，而是封装 + 限制接口

二、专业定义

容器适配器（Container Adapter）是一种封装机制：不实现新的数据结构，而是修改已有容器的接口，提供特定行为（栈、队列、优先级队列）。

因此由于容器适配器被限制了元素的访问，故而就不会有元素遍历这一说法，所以容器适配器一般都不具有迭代器。

三、常见容器适配器

 

适配器	底层默认容器	可否换底层
stack	deque	可（vector/list）
queue	deque	可（list）
priority_queue	vector	可（deque）

 

那么stack,queue的底层改装容器deque是什么

四，deque的简单介绍

为了引入deque，我们先来看一下vector和list的优缺点：

vector:

优点：存储连续，不易造成空间碎片，空间利用率高，缓存效率高，支持随机访问

缺点：随机插入删除效率低下，扩容操作会导致空间的大量浪费

queue:

优点：随机插入删除效率高，没有扩容操作，不会导致空间大量浪费

缺点：存储不连续，易造成碎片化空间存储，空间利用率低，不支持随机访问

 

我们可以看到vector和list的优缺点是互补的，在两者基础之上，人们引入deque，是在list和vector的基础上的改良，支持头插尾插，头删尾删。

改良的具体细节：

将list中的一个个节点结构改为一组组数组结构（buff)，优化相关方法。

deque:的成员：两个封装好的迭代器start,finish分别指向起始元素位置和最后一个元素的下一个位                            置

                          一个指针数组map：存放每个buff的地址，从中间存放，两边扩容

                          记录指针数组存放元素个数的一个整形值size

迭代器的封装：

                         deque的相关方法实现主要依赖于它的迭代器；

                         迭代器的成员有：

                         两个一维指针first,last，指向当前buff的起始元素位置，最后一个元素位置的下一                             个位置

                         一个一维指针cur：指向当前访问到的元素的位置

                         一个二维指针node：指向map数组中当前buff所对应的地址的那个元素的地址

迭代器的遍历：

                       当cur!=last时就就++cur,反之就让cur、first、last、node分别更新到下一组buff的第                          一个元素位置，第一个元素位置，最后一个元素位置、map中存放当前bufff指针元                          素的地址

成员的访问：   通过取整取模运算得知相应位置的元素是什么：就像是告知你一个存放在二维数组                          的元素是整个数组从第一个元 素开始数的第几个，求它在第几行，第几列那样

头插尾插，头删尾删：通过挪动start和finish实现

 

deque存储空间结构示意图

deque 优点

• 头尾插入删除效率极高（O (1)）
• 分段存储，不易出现大内存分配失败
• 支持随机访问
• 扩容无代价、不拷贝数据

deque 缺点

• 内存不连续，不能当作原生数组使用
• 中间插入删除效率差
• 迭代器效率略低于 vector
• 结构复杂，占用少量额外空间

五、栈和队列的代码实现

栈的代码实现：stack.h

//stack.h
#pragma once
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
	template <class T, class container = deque<T>>
	class stack
	{
	private:
		container con;
	public:
		void push(const T &a)
		{
			con.push_back(a);
		}
		void pop()
		{
			con.pop_back();
		}
		const T& top()
		{
			return con.back();
		}
		bool empty()
		{
			return con.empty();
		}
		int size()
		{
			return con.size();
		}
	};
};

队列的代码实现：queue.h

//queue.h
#pragma once
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
namespace mine1
{
template<class T,class container=deque<T>>
class queue
{
private:
	container con;
public:
	void push(const T& a)
	{
		con.push_back(a);
	}
	void pop()
	{
		con.pop_front();
	}
	const T& back()
	{
		return con.back();
	}
	const T& front()
	{
		return con.front();
	}
	bool empty()
	{
		return con.empty();
	}
	int size()
	{
		return con.size();
	}
};
};

六、优先级队列（priority_queue)介绍

优先级队列这个容器适配器是基于数据结构中堆这一个数据结构实现的，是对堆的封装关于堆的相关介绍：

C语言——堆

要实现这一个容器适配器，我们要首先介绍仿函数。

仿函数

仿函数是对标c语言中的函数指针。由于函数指针的设计的可读性较低，所以c++引入仿函数，为的就是简化回调函数操作。

仿函数的本质

仿函数是伪装的很好的类，它通过示例化出对象，使用对象就可以完成类似于函数指针（或函数名）的函数调用，它本质也属于适配器的一员（STL中三大适配器：容器适配器，仿函数适配器，迭代器适配器）。仿函数的底层是通过重载opereator（）实现的。

结论：仿函数=类重载opereator ()+实例化对象调用

来看一个简单的仿函数就十知八九了：

#include<functional>
#include<iostream>
using namespace std;
class Add{
public:
	int operator()(int a,int b) 
	{
		return a+b;
	}
};
int main()
{
	Add add;
	cout<<add(2,3)<<endl;//5
}

STL中仿函数的使用：

一、先记住：使用前提

1. 必须包含头文件：#include <functional>
2. 配合 STL 算法 使用（如 sort、find_if、for_each 等）
3. 调用方式：仿函数类名()(参数)（临时对象调用）

二、STL中常见的仿函数即使用方法

1.算术仿函数

仿函数名称	功能	示例代码
plus<T>	加法：a + b	plus<int>()(3,5) → 8
minus<T>	减法：a - b	minus<int>()(10,3) →7
multiplies<T>	乘法：a * b	multiplies<int>()(2,4)→8
divides<T>	除法：a / b	divides<double>()(9,2)→4.5
modulus<T>	取模：a % b	modulus<int>()(7,3)→1
negate<T>	取反：-a	negate<int>()(5)→-5

2.关系仿函数

仿函数名称	功能	示例
equal_to<T>	等于：a == b	equal_to<int>()(3,3)→true
not_equal_to<T>	不等于：a != b	-
greater<T>	大于：a > b	✅ 排序降序核心
greater_equal<T>	大于等于：a >= b	-
less<T>	小于：a < b	✅ 默认升序排序
less_equal<T>	小于等于：a <= b	-

3.逻辑仿函数

仿函数名称	功能	示例
logical_and<T>	逻辑与：a && b	logical_and<bool>()(true,false)→false
logical_or<T>	逻辑或：`a		b`	-
logical_not<T>	逻辑非：!a	logical_not<bool>()(true)→false

 

基于仿函数对优先级队列的实现：

我们使用关系比较仿函数作为模板类priority_queue的模板参数，这样来控制建堆时这个堆是大堆还是小堆：（大堆，降序，用less<T>;小堆，升序，用greater<T>）

//priority_queue.h
#pragma once
#include<vector>
#include<functional>
#include<iostream>
#include<algorithm>
using namespace std;
namespace mine2
{
    template <class T, class Container = vector<T>, class Compare = less<T> >

    class priority_queue

    {

    public:

        priority_queue()=default;

        template <class InputIterator>

        priority_queue(InputIterator first, InputIterator last)//迭代器区间构造
        {
            for (auto it = first; it != last; it++)
            {
                c.push_back(*it);
            }
            for (int i = (c.size() - 1-1)/2; i >= 0; i--)
            {
                Adjustdown(i);
            }
        }

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

        size_t size() const
        {
            return c.size();
        }
        void Adjustup(int n)//向上调整默认大堆
        {
            int parent = (n - 1) / 2;
            int child = n;
            while (child != 0)
            {
                if (comp(c[parent], c[child]))
                {
                    swap(c[parent], c[child]);
                    child = parent;
                    parent = (parent - 1) / 2;

                }
                else
                    break;
            }
        }
        void Adjustdown(int n)
        {
            int parent = n;
            int child = 2 * parent + 1;
            while (child < c.size())
            {
                if (child + 1 < c.size() && comp(c[child ], c[child+1]))child++;
                if(comp(c[parent],c[child]))
                {
                    swap(c[parent],c[child]);
                    parent=child;
                    child=child*2+1;
                }
                else break;
            }
        }
        const T& top() const
        {
            return c[0];
        }

        void push(const T& x)
        {
            c.push_back(x);
            Adjustup(c.size() - 1);
        }
        void pop()
        {
            swap(c[0], c[size() - 1]);
            c.pop_back();
            Adjustdown(0);
        }
    private:

        Container c;

        Compare comp;

    };

};