蓝桥杯基础知识点9 stack、queue、priority_queue

2026/9/18 8:19:52 拓冰建站浏览量

01 stack的定义和结构

stack是一种后进先出（LIFO）的数据结构，头文件<stcak>。

template <class T, class Container = deque<T>>
class stack;

T：存储在stack中的元素类型。

Container：底层容器类型，默认deque（双端队列容器），也可用vector（序列容器，非连续容器，用于表示）、list（序列容器，连续容器，实现的功能和数据结构中的双向链表极为相似）等。

02 stack的常用函数

函数描述时间复杂度

push(x) 在栈顶插入元素x O(1)

pop() 弹出栈顶元素 O(1)

top() 返回栈顶元素 O(1)

empty() 检查栈是否为空 O(1)

size() 返回栈中元素的个数 O(1)

附：如果将一个数组的元素依次放入栈，再依次取出，则可翻转数组。

#include<iostream>
#include<stack>using namespace std;int main(){stack<int> myStack;// 向栈中插入元素myStack.push(1);myStack.push(2);myStack.push(3);myStack.push(4);// 获取栈顶元素    4cout << "栈顶元素：" << myStack.top() << endl;// 弹出栈顶元素myStack.pop();// 再次获取栈顶元素    3cout << "弹出一个元素后的栈顶元素：" << myStack.top() << endl;// 检查栈是否为空    否if(myStack.empty()){cout << "栈为空" << endl;}else{cout << "栈不为空" << endl;}// 获取栈的大小    3cout << "栈的大小：" << myStack.size() << endl;return 0;
}

01 queue队列

queue是一种先进先出（FIFO）的数据结构。

除Ciontainer外，其定义、结构和常用函数均与 stack 类似。

Container：底层容器类型，默认deque（双端队列容器），也可使用list（功能类似双向链表）。

template <class T, class Container = deque<T>>
class queue;

02 priority_queue优先队列（使用频率较高）

priority_queue与普通队列不同，priority_queue中的元素按照一定的优先级排序，默认元素按从大到小排序，最大元素位于队列前面。

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type>>
class priority_queue;

T：存储在priority_queue中元素的类型。

Container：底层容器类型，默认vector（可变大小的数组），也可使用deque（双端队列容器）。

Compare：比较函数对象的类型，默认less。

常用函数的push（x）和 pop（）的时间复杂度与 stack 和 queue 不同，均为 O（logN）。

struct Compare{//          重载        仿函数bool operator()(int a, int b){// 自定义比较函数，逆序排序return a > b;}
};int main(){std::priority_queue<int, std::vector<int>, Compare> pq;auto compare = [](int a, int b){//自定义比较函数，逆序排序return a > b;};std::priority_queue<int, std::vector<int>, decltype(compare)> pq(compatre);}

若优先队列中元素类型比较简单，可直接用greater<T>修饰比较方法。

priority_queue<int，vector<int>， greater<int>>pq；

std::greater函数定义在<functional>头文件中。

在 C++ 中，尖括号 < > 用于指定模板参数，在模板类或模板函数中声明。

reference:

C++ 尖括号 < > 用于指定模板参数 - 知乎 (zhihu.com)

可拓展学习：

【C、C++基础】什么时候用 “.” 什么时候用“-＞”（3个实例搞懂）_什么时候用->什么时候用.-CSDN博客

建站实战干货

蓝桥杯基础知识点9 stack、queue、priority_queue