C++-stack和queue

一、stack的介绍、使用和模拟实现

1.1 stack的介绍

1.stack是一种容器适配器(container adaptor)，专门设计用于后进先出(LIFO)的环境，即元素只能从一端进行插入和删除。

2.stack是以容器适配器的方式进行实现的，是使用特定的容器类作为底层容器进行封装实现的类，容器适配器会提供特殊的成员函数来实现stack访问元素的功能。任何标准容器只要拥有以下接口便可作为stack的底层容器。

empty push_back pop_back size back

vector、list、deque都可以作为stack的底层容器。

3.

模板参数介绍：

T：元素类型模板 Container：底层容器模板

1.2 stack的使用

1.stack的核心接口有：

stack()、push、pop、top、empty、size

void test_stack() { //构造 stack<int> st; //插入 st.push(1); st.push(2); st.push(3); st.push(2); //获取数据个数 cout << st.size() << endl; //4 //弹出栈顶元素 st.pop(); st.pop(); //获取栈顶元素 cout << st.top() << endl; //2 st.pop(); st.pop(); //判空 cout << st.empty(); //1 }

1.3 stack做为容器适配器的模拟实现

1.模拟实现分为以下几个部分：

#stack.h #include<vector> namespace xxx { template<class T,class Container = vector<T>> class stack { public: void push(const T& val) { _con.push_back(val); } void pop() { _con.pop_back(); } const T& top() { return _con.back(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: //成员变量是底层容器实例化的对象 Container _con; }; }

2.模拟实现的stack的使用

#include<iostream> #include<deque> using namespace std; #include"stack.h" void test_stack() { //使用默认的底层容器 xxx::stack<int> st1; //使用库里面的标准容器作为底层容器 xxx::stack<int, deque<int>> st2; st1.push(1); st1.push(2); st2.push(1); st2.push(2); st1.pop(); st2.pop(); cout << st1.size() << endl; //1 cout << st1.empty() << endl; //0 cout << st1.top() << endl; //1 cout << st2.size() << endl; //1 cout << st2.empty() << endl; //0 cout << st2.top() << endl; //1 }

二、queue的介绍、使用和模拟实现

2.1 queue的介绍

1.queue也是一种容器适配器(container adaptor)，专门设计拥有先进先出(FIFO)的环境，即元素从一端插入队列从队列的另一端进行提取。

2.队列作为容器适配器实现的类，即将特定的容器类进行封装作为其底层容器实现的类，容器适配器会提供特殊的成员函数类实现queue访问元素的功能。任何标准容器只要提供以下接口便可作为queue的底层容器。

empty size front back pop_front push_back

deque、list都可以作为queue的底层容器。

3.

模板参数介绍：

T:元素类型模板 Container:底层容器模板

2.2 queue的使用

1.queue的核心接口有：

queue()、push、pop、front、back、empty、size

void test_queue() { //使用构造函数创建一个队列 queue<int> q; //在队尾插入元素 q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); //删除队头的元素 q.pop(); q.pop(); //获取队头和队尾的元素 cout << q.front() << endl; //3 cout << q.back() << endl; //5 //获取队列内有效元素个数 cout << q.size() << endl; //3 //判断队列是否为空 cout << q.empty() << endl; //0 }

2.3 队列作为容器适配器的模拟实现

队列的模拟实现部分和栈的模拟实现部分差不多。

#queue.h #include<list> namespace xxx { template<class T,class Container = list<T>> class queue { public: void push(const T& val) { _con.push_back(val); } void pop() { _con.pop_front(val); } const T& front() { return _con.front(); } const T& back() { return _con.back(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; }; }

模拟实现的队列使用也和栈差不多：

#include<iostream> #include<deque> using namespace std; #include"queue.h" void test_queue() { xxx::queue<int> q1; xxx::queue<int, deque<int>> q2; //... }

三、priority_queue的介绍、使用和模拟实现

3.1 priority_queue的介绍

1.优先级队列(priority_queue)也是一个容器适配器(container adaptor)，默认的底层实现是一个大堆，从堆底插入元素，在进行向上调整后需要依旧保持堆的特性，删除元素时会删除堆顶的元素，删除步骤是将堆顶和堆底的元素进行交换，然后删除堆底的元素，对堆顶的元素进行向下调整，需要依旧保持堆的特性。

2.优先级队列是被实现为容器适配器的类，同样也是使用特定的容器进行封装作为其底层容器的类，优先级队列相较于其他的容器适配器而言，需要底层容器拥有随机访问迭代器的功能。在这个前提下能提供以下接口的标准容器就可以作为优先级队列的底层容器。

empty size front push_back pop_back

标准容器vector、deque可以作为优先级队列(priority_queue)的底层容器。

3.模板参数介绍：

template<class T,class Container = vector<T>,class Compare = less<typename Container::value_type>> T:元素模板 Container:底层容器模板 Compare:仿函数模板

3.2 priority_queue的使用(包括仿函数的设置控制大小堆)

1.priority_queue的核心接口：

priority_queue()、priority_queue(first,last)、push、pop、top、size、empty

void priority_queue_test() { //使用默认构造 priority_queue<int> pq1; //使用迭代器区间构造 vector<int> v = { 10,5,6,7,4,3,1,2 }; priority_queue<int> pq2(v.begin(), v.end()); //插入一个8 pq2.push(8); //删除顶部元素 pq2.pop(); //获取顶部元素 cout << pq2.top() << endl; //8 //获取有效数据个数 cout << pq2.size() << endl; //8 //判空 cout << pq2.empty() << endl; //0 }

2.优先级队列的模板参数列表里面有一个仿函数模板，这个仿函数模板是用于改变优先级队列的底层是选择大堆控制还是小堆控制。库里面默认优先级队列的底层是大堆。

大堆小堆的切换方式：使用less仿函数时为大堆，使用greater仿函数时为小堆。

//设置底层为大堆 priority_queue<int> pq1; priority_queue<int, vector<int>, less<int>> pq2; //设置底层为小堆 priority_queue<int, vector<int>, greater<int>> pq3;

3.3 priority_queue的模拟实现

优先级队列的模拟实现和stack、queue的模拟实现多了一个仿函数成员变量。

还有一点迭代器区间初始化优先级列队时需要一个额外的迭代器模板参数。

#include<vector> namespace xxx { //template<class T, class Container = vector<T>> //添加仿函数模板 template<class T, class Container = vector<T>,class Compare=Less<T>> class priority_queue { public: template<class InputIterator> priority_queue(InputIterator first, InputIterator last) :_con(first,last) { //向下调整建堆 for (int end = ((_con.size() - 1) - 1) / 2; end >= 0; end--) { adjust_down(end); } } void swap(T& x, T& y) { T tmp = x; x = y; y = tmp; } void adjust_up(int child) { int parent = (child - 1) / 2; while (child > 0) { //if (_con[child] > _con[parent]) if(_com(_con[parent],_con[child])) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { int child = parent * 2 + 1; while (child < size()) { //if ((child + 1) < size() && _con[child + 1] > _con[child]) if ((child + 1) < size() && _com(_con[child],_con[child+1])) { child += 1; } //if (_con[child] > _con[parent]) if (_com(_con[parent],_con[child])) { swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void push(const T& x) { _con.push_back(x); adjust_up(size()-1); } void pop() { swap(_con[0], _con[size() - 1]); _con.pop_back(); adjust_down(0); } T& top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; //仿函数成员变量 Compare _com; }; }

模拟实现的priority_queue的使用：

#include<iostream> using namespace std; #include"priority_queue.h" //拥有控制模拟实现的优先级队列的仿函数 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; } }; void priority_queue_test() { vector<int> v= { 10,5,6,7,4,3,1,2 }; xxx::priority_queue<int> pq(v.begin(), v.end()); while (!pq.empty()) { cout << pq.top() << " "; //10 7 6 5 4 3 2 1 pq.pop(); } cout << endl; xxx::priority_queue<int,vector<int>,Greater<int>> pq1(v.begin(), v.end()); while (!pq1.empty()) { cout << pq1.top() << " "; //1 2 3 4 5 6 7 10 pq1.pop(); } cout << endl; }

四、容器适配器(Container Adaptor)

4.1 适配器的概念

适配器是一种设计模式，这种模式是将一个类的接口转换成用户希望的另一种接口，例如220V的电压通过设计成不同类型的插座可以满足不同类型的插头的需求。

容器适配器的意思就是：可以通过模板参数控制底层容器。

4.2 STL标准库里面的stack、queue、priority_queue的默认底层容器

stack和queue的默认底层容器使用的是deque，priority_queue的默认底层容器使用的是vector。

4.3 deque的简单介绍

1.双端队列(deque)：是一种双开口的连续空间的数据结构，双开口是指可以在头尾和尾部插入和删除数据，且时间复杂度为O(1)，与vector相比，可以在头部进行插入删除数据，与list相比，可以通过operator[]更快的访问数据。

2.deque并不是一段真正的连续的空间，而是由一段段连续的小空间构成的，实际上deque类似于一个动态的二维数组。

3.双端队列底层是一段假象的连续空间，实际上是分段连续的，为了维护其整体的连续性以及随机访问的功能，deque的迭代器设计也比较复杂。

4.deque的优点与缺陷

4.1 deque的头部和尾部的插入删除数据很方便，且扩容代价也比较低。

4.2 如果需要deque在中间进行插入或删除数据，有两种方案：

1.对单个buff数组进行扩容，但会导致每个buff内部的数据个数不同 2.每个buff的数据个数保持不变，对整体的数据进行挪动，然后再插入数据

中间的插入数组主要会影响operator[]的效率。

operator[]的实现：

//假设查找operator[i]位置上的数据 1.i-=第一个buff的数据个数，因为第一个buff在经过头插后数据可能不满。 2.x=i/(每个buff内数据个数)，x是i处于第几个buff的位置。 3.y=i%10，y是i在第x+1个buf上的具体位置。

因此deque在中间的插入和删除效率是很低的。

4.3 deque不适合遍历，在拥有大量数据的情况下，buff的迭代器需要去频繁检测是否移动到了某段buff的边界，会导致效率很低。

4.4 STL标准库里面选择deque作为stack和queue的底层容器的原因

1.stack和queue不需要遍历，只需要在一端或两端进行插入删除数据。

2.stack的元素增长时，deque比vector的扩容效率高，且deque不需要挪动数据；queue的元素增长时deque不仅效率高而且在内存使用率方面要比list更好。