[C++初阶]栈和队列_优先级队列的模拟实现 deque类 的理解

为了更好的理解优先级队列priority_queue，这里会同时进行栈和队列的提及

简要概念（栈和队列）

• 栈：后进先出的结构，通常使用数组栈的形式
• 队列：先进先出的结构，通常使用链表式的队列

• 优先级队列：优先级队列是基于堆实现的一种数据结构。在 C++ STL 中，我们将实现的priority_queue 类就是通过堆来实现的。
• 这里不再对堆进行详细介绍，具体在这：堆详解

栈和队列的模拟实现与使用

stack（栈）

模拟实现

进行stack的实现前先介绍一下deque<T>：

deque的理解和操作

概念（简单看看）

概念简单看看就行

1. deque 是 C++ STL 中的一种双端队列（double-ended queue），它允许在队列两端高效地添加、删除元素，同时支持随机访问。
2. 与vector的不同：deque 具有良好的内存分配策略，可以避免 vector 扩容时带来的大量元素复制操作。此外，deque 也具有更好的迭代器安全性，因为它不能像 vector 那样通过引起扩容而使得旧迭代器失效。
3. deque 内部使用了一个中央控制器，管理了一系列固定大小的连续空间块，每个块内部存储多个元素。当 deque 需要增加或删除元素时，中央控制器会根据需要进行块的扩容或收缩。

操作（重要）

这里介绍deque与stack && queue的不同处，介绍为什么要用deque实现栈和队列

1. 插入和删除方式不同：栈只能在栈顶进行插入和删除元素，而队列只能在队尾插入，在队头删除；而 deque 可以在队列的两端都插入和删除元素。
2. 访问方式不同：栈只能访问栈顶元素，队列只能访问队头元素；而 deque 可以随机访问任意位置的元素。
3. 功能上不同：栈的主要功能是实现“后进先出”（LIFO），队列的主要功能是实现“先进先出”（FIFO），而 deque 不仅可以实现这两种功能，还能够满足双向遍历、支持随机插入和删除等操作。

---

继续对stack进行模拟实现：

这里需要注意的：

1. 对于模板template： T 表示栈中元素的类型，Container 表示底层容器的类型，默认为 deque<T>
2. 成员变量： _con为Container类型，如果调用者不给Container类型，_con默认为deque，剩下的增删查改调用_con的操作函数即可

namespace aiyimu 
{//Container 表示用于存储队列元素的底层容器类型，默认值为 deque<T>template<class T, class Container = deque<T>>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();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}

queue

同理stack，这里不作过多赘述，使用_con的操作函数实现即可

namespace aiyimu
{template<class T, class Container = deque<T>>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();}const T& back() const{return _con.back();}const T& front() const{return _con.front();}bool empty()  const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}

priority_queue（优先级队列）

框架

• Container：在上文stack有解，同理
• Compare：用于选择该堆为大堆还是小堆，默认为std::less则为小堆
• std::less： 是一个函数对象，用于比较两个参数的大小关系。重载了小于运算符，用于比较两个类型为 T 的对象的大小。当 a < b 时，std::less()(a, b) 返回 true，否则返回 false。
• 构造函数，操作函数

template<class T, class Container = vector<T>, class Compare = std::less<T>>class priority_queue{public:// 默认构造priority_queue(){}// 利用迭代器构造函数template <class InputIterator>priority_queue(InputIterator first, InputIterator last){}// O(logN)// 向上调整void adjust_up(size_t child){}//向下调整void adjust_down(size_t parent){}// 其余操作函数void push(const T& x){}void pop(){}const T& top(){}bool empty() const{}size_t size() const{}private:Container _con;};

具体实现

push()

1. 插入操作即为堆的插入操作，所以执行_con.push_back()后进行向上调整（从尾部_con.size()-1进行调整）

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

adjust_up()（向上调整）

1. 向上调整即堆heap的操作，具体思路在上文给到的堆详解中
2. 主要对if语句中的内容进行解释：

（小堆）向上调整过程中，当父节点的值小于子节点时，交换父子节点

• 原始方法直接进行<判断：if (_con[parent] < _con[child])
• 但这种写法此时就锁定小堆了， 为了使调用者可以根据需要进行大堆小堆的更改
• 所以这里创建一个Compare对象com，将比较改写为：if(com(_con[parent], _con[child]))
• 该写法当调用者不做更改时默认为小堆（std::less），当调用者给出std::greater（比较大于），此时的priority_queue就变为大堆

void adjust_up(size_t child)
{Compare com;	// size_t parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if(com(_con[parent], _con[child]))// 默认为less，调用者可以自行指定{std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

pop()

• 交换堆顶和堆底的元素，删除堆顶元素，向下调整

void pop()
{// 交换堆顶和堆底的元素，删除堆顶元素，向下调整std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}

adjust_down()（向下调整）

• 向下调整需要注意的仍为com(_con[child], _con[child + 1])写法的意义
• 具体内容在adjust_up中已经提到

void adjust_down(size_t parent)
{Compare com;size_t child = parent * 2 + 1;	//先假设右孩子大while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if(com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

top()

• 返回堆顶元素，即_con[0]

const T& top()
{return _con[0];
}

empty()

• bool类型：判断堆是否为空

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

size()

• 返回堆大小（堆元素个数）

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

priority_queue 的 验证 / 使用

插入元素 && 打印priority_queue

// 头文件void test_priority_queue1()
{aiyimu::priority_queue<int> pq;//priority_queue<int> pq;// 插入元素pq.push(3);pq.push(2);pq.push(5);pq.push(9);pq.push(4);pq.push(6);pq.push(1);// 打印pq的所有元素while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}

输出结果：

降序 / 升序

int arr[] = { 3,5,6,8,19,7,1,0,9,1,20,4,12 };// 不传入Compare类型，默认less类型：小于，即降序aiyimu::priority_queue<int> heap_less(arr, arr + sizeof(arr) / sizeof(arr[0]));// 传入Compare类型，为greater类型：大于，即升序aiyimu::priority_queue<int, vector<int>, greater<int>> heap_greater(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!heap_less.empty()){cout << heap_less.top() << " ";heap_less.pop();}cout << endl;while (!heap_greater.empty()){cout << heap_greater.top() << " ";heap_greater.pop();}cout << endl;

输出结果：

由此可以看出，当使用std::less时堆为降序，std::greater时堆为升序