文章目录

• 简介
• • stack
  • queue
  • priority_queue
• stack的模拟实现
• • 成员变量
  • empty
  • size
  • top
  • push
  • pop
• queue的模拟实现
• • 成员变量
  • empty
  • size
  • top
  • push
  • pop
• priority_queue的模拟实现
• • 成员变量
  • empty
  • size
  • top
  • push
  • pop
  • 仿函数
• 完整版代码
• • stack.h
  • queue.h
  • priority_queue.h
  • test.cpp

简介

stack、queue和priority_queue是STL库中比较常用的几个容器他们分为一下几部分

stack

queue

priority_queue

我们可以看出他们实现的接口都是一样的。

stack的模拟实现

stack的特点是后进先出，可以用数组或者链表实现。其实stack就是对vector，list，deque等容器进行封装。接下来我们来看看到底是如何封装的。

成员变量

stack被写成了模板，因为vector、list和deque都可以适配stack，所以stack被写出了模板，使用者传什么容器就是对什么容器进行适配，如果不传默认用deque。

_con就是创建和封装的对象，我们也不用对_con进行初始化，因为对自定义类型，默认的足够了。

empty

size

top

push

pop

这就是stack的常用的接口，我们可以看出stack本质就是对适配的容器接口进行封装形成新的接口。

queue的模拟实现

queue的特点是先进先出，可以用链表实现。其实stack就是对list，deque容器进行封装。接下来我们来看看到底是如何封装的。（queue一般不用数组实现，因为数组头删效率低）

成员变量

queue也被写成了模板，跟stack情况类似，因为list和deque都可以适配queue，所以queue被写成了模板，使用者传什么容器就是对什么容器进行适配，如果不传默认用deque。

_con就是创建和封装的对象，我们也不用对_con进行初始化，因为对自定义类型，默认的足够了。

empty

size

top

push

pop

这就是queue的常用的接口，我们可以看出和stack本质是一样的就是对适配的容器接口进行封装形成新的接口。

priority_queue的模拟实现

priority_queue（优先级队列）它逻辑结构上是heap（堆），但是在物理结构上它是数组。priority_queue是对vector容器进行封装。

成员变量

priority_queue也被写成了模板，跟stack、queue情况类似，但是只跟vector适配，而且priority_queue多了个仿函数，使用在可以显示的传，不然默认给less。

empty

size

top

push

因为堆只有大堆或者小堆，所以插入数据的时候要向上调整，保证插入数据后还是大堆或者小堆。

pop

因为堆只有大堆或者小堆，所以删除数据的时候要向下调整，保证删除数据后还是大堆或者小堆。

priority_queue跟之前的栈和队列一样都是对容器的封装，只有priority_queue在对插入、删除的时候要注意保证不能改变堆的性质

仿函数

完整版代码

stack.h

#pragma once
namespace lzf
{template>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_stack1(){stack> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}}
}

queue.h

#pragma once
namespace lzf
{template>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& top(){return _con.front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue1(){queue q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.top() << " ";q.pop();}}
}

priority_queue.h

#pragma once
namespace lzf
{templatestruct less{bool operator()(const T& x,const T& y)const{return x < y;}};templatestruct greater{bool operator()(const T& x, const T& y)const{return x > y;}};template>class priority_queue{private:void adjust_up(){Compare com;//默认建大堆size_t child = _con.size() - 1;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(){Compare com;//默认建大堆size_t parent = 0;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}public:priority_queue(){}templatepriority_queue(Inputiterator first, Inputiterator last){//用一段区间迭代器建堆while (first != last){_con.push_back(*first);adjust_up();++first;}}//template//priority_queue(Inputiterator first, Inputiterator last)//	:_con(first,last)//{//	//用一段区间迭代器建堆// for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)//	{//		adjust_down(i);//	}//}const T& top()const{return _con.front();}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}void push(const T& x){_con.push_back(x);adjust_up();}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down();}private:Container _con;};void test_prority_queue1(){priority_queue> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(6);q.push(3);q.push(9);q.push(0);while (!q.empty()){cout << q.top() << " ";q.pop();}}void test_prority_queue2(){vector v;v.push_back(5);v.push_back(9);v.push_back(2);v.push_back(6);v.push_back(7);v.push_back(3);v.push_back(0);priority_queue> q(v.begin(),v.end());while (!q.empty()){cout << q.top() << " ";q.pop();}}
}

test.cpp

#include
using namespace std;
#include
#include
#include
#include
#include"stack.h"
#include"queue.h"
#include"priority_queue.h"
void test()
{int a = 0;int* pa = &a;int*& ppa = pa;cout << *ppa;}
int main()
{//lzf::test_stack1();//lzf::test_queue1();//lzf::test_prority_queue2();test();return 0;
}```