AKSZ-栈&队列
2024-05-02 17:33:13
发布于:广东
STL
->standard template library->标准模板库
栈(stack)
类似一个羽毛球筒,先进后出。
入栈
void push(int x){
q[++top]=x;
}
出栈
void pop(){
top--;
}
栈顶
int query(){
return stk[top];
}
大小
int size(){
return top;
}
判空
bool empty(p){
return top==0;
}
栈模板
定义:stack<int> stk;
入栈:stk.push(n);
出栈:stk.pop();
栈顶:int tmp=stk.top();
判空:stk.empty();
复杂度通通O(1)!!!
队列(queue)
类似于一根管子,先进先出。
入队
void push(int x){
q[++rear]=x;
}
出队
void pop(){
front++;
}
队首
int query(){
return q[front+1];
}
大小
int size(){
return rear-front;
}
判空
bool empty(p){
return rear==front;
}
以上代码中,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)。
这里空空如也
有帮助,赞一个