藍橋杯基礎知識點9 stack、queue、priority_queue

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博客