今日学习 一、栈和队列

常规
1

C++标准模版库STL

在C语言中,很多东西都需要自己实现,例如用数组模拟栈和队列等等有些复杂的操作实现起来会非常麻烦。
因此,C++提供了标准模板库(Standard Template Library,STL),其中封装了很多非常实用的容器,不需要费力去实现他们的细节而直接调用函数来实现很多功能,十分方便。例如,string其实就是STL中的一个容器。

栈和队列

栈
栈(stack)又称堆栈,是只能在某一端插入和删除的特殊线性表。具有先进后出(FILO,first in last out)的特性。

stack的定义

stack<typename\> name;

stack常用函数

push(x)：将x入栈,时间复杂度为O(1)
pop()：弹出栈顶元素,时间复杂度为O(1)
top()：获得栈顶元素,时间复杂度为O(1)
empty()：判空,true为空,false为非空,时间复杂度为O(1)
size()：返回栈内元素个数,时间复杂度为O(1)

队列
队列(queue)是线性表的一种,具有先进先出(FIO,first in first out)的特性。使用队列存取数据元素时,数据元素只能从表的一端进入队列,另一端出队列。

queue的定义

queue<typename\> name;

queue常用函数

push(x)：将x入队
pop()：弹出队首元素
front()：获得队首元素
back()：获得队尾元素
empty()：判空,true为空,false为非空
size()：返回队列内元素个数

优先队列
优先队列容器与队列一样,只能从队尾插入元素,从队首删除元素。但是它有一个特性,就是队列中优先级最大的元素总是位于队首。
通俗来讲:通过优先队列可以实现快速获取极值<最大、最小>

优先队列的定义

priority_queue<int, vector<int>, greater<int> > q1;
//这里需要一个空格,避免识别成>>位移运算符

priority_queue<int, vector<int>, less<int> >q1 等价于
priority_queue<int> q1

优先队列元素为结构体类型时的运算符重载
元素的比较规则默认按元素值由大到小排序,可以重载”<“操作符来重新定义比较规则。

结构体优先队列:

struct node {
    int x, y;
    friend bool operator < (node a, node b) {
        return a.x > b.x;    //结构体中,x小的优先级高
    }
};
priority_queue<node>q;    //定义方法
//通过自定义operator<操作符来比较元素中的优先级。

优先队列常用函数

push(x)：将x入队
pop()：弹出队首元素
front()：获得队列中优先级最高的元素
empty()：判空,true为空,false为非空
size()：返回队列内元素个数