STL
->standard template library->标准模板库
栈(STACK)
类似一个羽毛球筒,先进后出。
入栈
出栈
栈顶
大小
判空
栈模板
定义:stack<int> stk;
入栈:stk.push(n);
出栈:stk.pop();
栈顶:int tmp=stk.top();
判空:stk.empty();
复杂度通通O(1)!!!
队列(QUEUE)
类似于一根管子,先进先出。
入队
出队
队首
大小
判空
以上代码中,rear是队尾,front是队首前一个元素
队列模板
定义:queue<int> q;
入队:q.push(x);
出队:q.pop();
队首:int t=q.front();
大小:q.size();
判空:q.empty();
初始化/清空:while(q.empty())q.pop();
其中,只有初始化复杂度是O(n),其余均为O(1)。
优先队列(PRIORITY QUEUE)
定义:priority_queue<int> q(大根堆)
priority_queue<int,vector<int>,greater<int> > q(小根堆)
其余和队列基本相同,但是q.pop();是删掉最大元素,没有front(),只有q.top(),代表最大的元素。
q.top()的复杂度是O(log n)。