什么是棧？什么是隊列？

什么是先進后出？什么是先進先出？

了解基礎之后，又如何用來寫算法題？

帶著這些疑問，讓我帶領你，走進棧與隊列的世界

棧與隊列

棧：

1、棧的基本定義：

棧其實就是一種線性表，它只允許在固定的一段進行插入或者刪除元素。

你可以把它想象成一個只能從上面開口放東西和拿東西的盒子。

那個能放東西和拿東西的上面開口的地方，我們就叫它棧頂。

2、棧的核心操作：入棧、出棧、取棧頂元素

3、棧的特性：先進后出（LIFO，Last In First Out）

什么意思呢？

就拿槍的彈夾來舉例，把（棧）比作彈夾，把（元素）類比為子彈。

當你往彈夾里壓子彈的時候，最后壓進去的那顆子彈，會在最上面，

等開槍的時候，它會第一個被打出去。

而最開始壓進去的子彈，因為被后來的子彈壓在下面了，

所以是最后才被打出來的。

這就是先進后出

隊列：

1、隊列的基本定義：

隊列本質上也是一種特殊的線性表。

它就像我們在排隊一樣，只允許在隊伍尾部（隊尾）加人（元素），只有隊伍的最前排（隊首）人（元素）才能離開。

2、隊列的核心操作：入隊列、出隊列、取出隊首元素。

3、隊列的特性：先進先出（FIFO，First In First Out）

什么意思呢？

就像火車過隧道的例子，火車頭就是隊首，火車尾就是隊尾。

火車進隧道的時候，車頭先進入隧道，等出隧道的時候，也是車頭先出來，

車尾后進去所以就后出來。

這就跟隊列里的元素一樣，先進入隊列的元素會先出隊列，后進入的就后出隊列。

深度思索

上方只能讓你淺顯的了解各個函數的表層含義，它和咱們計算機還是不搭邊的。

那他們在計算機中，那些場景會用到這些呢？

棧：

最典型的就是嵌套結構管理

• 括號匹配：遇到 (){} 等符號時，會將左括號，壓入棧中，當遇到右括號時，判斷棧中括號是否匹配。
• 調用函數：程序調用函數時，會把當前位置壓棧保存，等函數執行完畢之后再按逆序返回。

棧在算法中的常見應用

• 表達式求值（中綴轉后綴表達式）
• 瀏覽器后退 / 前進功能
• 迷宮尋路算法（深度優先搜索 DFS）

隊列：

• 任務公平調度，多個程序排隊等待CPU處理，按順序執行避免混亂。
• 異步通信橋梁，微信發消息時，消息先入隊列，對方手機再按順序接收，避免同步壓力

隊列在算法中的常見應用

• 廣度優先搜索（BFS）
• 消息隊列系統（Kafka/RabbitMQ）
• 緩存淘汰策略（FIFO 算法）

棧與隊列的算法實現

棧的實現：

棧最常用的四個函數，放入、彈出、取棧頂元素、判斷是否為空

基于順序表實現棧：

const int max_size = 100;
struct MyStack{
private:int arr[max_size];int size;
public:// 初始化MyStack():size(0){};// 放入void push(int val){if(size>max_size-1){cout<<"已抵達最大容量"<<endl;}arr[size]=val;size++;}// 彈出int pop(){if(empty()){cout<<"暫無數據，彈出失敗"<<endl;return 0;}int cur = arr[size-1];size--;return cur;}int top() {if (empty()) {cout << "該棧為空棧" << endl;return 0;}int cur = arr[size-1];return cur;}bool empty(){if(size<=0) return true;else return false;}
};int main(){return 0;
}

基于鏈表實現棧：

struct Node{
public:int val;Node* next;Node():val(0),next(nullptr){}Node(int val):val(val),next(nullptr){}
};struct MyStack{
private:// 鏈表頭指針Node* head; // 不同的色彩，我也想見一見
public:~MyStack(){while(head){Node* temp = head;head = head->next;delete temp;}}MyStack():head(nullptr){}// 入棧void push(int val){Node* cur = new Node(val);cur->next = head;head = cur;}// 出棧int pop(){if(empty()){cout<<"空棧"<<endl;return 0;}Node* temp = head;int cur = temp->val;head = head->next;delete temp;return cur;}// 取元素int top(){if(empty()){cout<<"空棧"<<endl;return 0;}return head->val;}// 判斷是否為空bool empty(){return head == nullptr;}};

隊列的實現：

基于順序表實現隊列

// 基于數組，實現的循環隊列
const int CAPACITY = 100;
struct MyQueue{
private:int data[CAPACITY];int head;int tail;int count;
public:MyQueue():head(0),tail(0),count(0){}// 入隊列void push(int val){if(count>=CAPACITY){cout<<"隊列已滿"<<endl;return;}data[tail] = val;tail = (tail+1)%CAPACITY;count+=1;}// 出隊列int pop(){if(empty()){cout<<"空隊列"<<endl;return 0;}int cur = data[head];head=(head+1)%CAPACITY;count--;return cur;}// 取隊首元素int top(){if(empty()){cout<<"空隊列"<<endl;return 0;}int cur = data[head];return cur;}// 判斷是否為空bool empty(){return !count;}
};

基于鏈表實現隊列

#include <iostream>// 基于鏈表來實現隊列
class MyQueue{
private:// 定義鏈表節點的結構體struct Node {int val;  // 節點存儲的值Node* next;  // 指向下一個節點的指針// 節點的構造函數，用于初始化節點的值Node(int val) : val(val), next(nullptr) {}};Node* newHead;  // 鏈表的頭節點指針Node* newTail;  // 鏈表的尾節點指針public:// 隊列的構造函數，初始化頭節點和尾節點指針為 nullptr，表示隊列為空MyQueue() : newHead(nullptr), newTail(nullptr) {}// 析構函數，用于釋放鏈表中所有節點的內存，防止內存泄漏~MyQueue() {while (newHead) {Node* temp = newHead;newHead = newHead->next;delete temp;}}// 1. 入隊列，就是尾插，為了和 Java 庫中的隊列保持一致，用 bool 返回值bool offer(int val) {// 創建一個新的節點，存儲要插入的值Node* newNode = new Node(val);// 特殊情況處理：如果鏈表為空if (newHead == nullptr) {// 新節點既是頭節點也是尾節點newHead = newNode;newTail = newNode;} else {// 一般情況處理：將新節點插入到鏈表尾部newTail->next = newNode;// 更新尾節點指針指向新的尾節點newTail = newTail->next;}return true;}// 2. 出隊列，就是頭刪，注意頭刪也是要返回那個要刪除的值int poll() {// 特殊情況處理：鏈表為空，沒得刪if (newHead == nullptr) {std::cout << "隊列為空，無法出隊" << std::endl;return -1;  // 這里用 -1 表示出隊失敗，可根據實際情況修改}// 保存要出隊的值int ret = newHead->val;Node* temp = newHead;// 鏈表只有一個元素的情況if (newHead->next == nullptr) {// 出隊后鏈表為空，頭節點和尾節點都置為 nullptrnewHead = nullptr;newTail = nullptr;} else {// 一般情況處理：更新頭節點指針指向下一個節點newHead = newHead->next;}// 釋放被刪除節點的內存delete temp;return ret;}// 3. 取隊列首元素int top() {// 特殊情況處理：鏈表為空，沒得取if (newHead == nullptr) {std::cout << "隊列為空，無法獲取隊首元素" << std::endl;return -1;  // 這里用 -1 表示獲取失敗，可根據實際情況修改}// 一般情況處理：返回頭節點的值return newHead->val;}
};

競賽中如何運用

其實這才是很多人關心的問題！畢竟學了，就是為了用！

但是怎么用呢？

總不能每次用到棧和隊列時，都手敲實現吧？那太抽象了點！

所以，我們這里就引入了STL庫中的<stack>與<queue>兩個函數庫

先簡單的說一下，拓展一下認知：

棧與隊列 是 以底層容器完成其所有的工作，對外提供統一的接口，底層容器是可插拔的（也就是說我們可以控制使用哪種容器來實現棧與隊列的功能）。

所以STL中棧往往不被歸類為容器，而被歸類為container adapter（容器適配器）。

那么問題來了，STL 中棧是用什么容器實現的？

從下圖中可以看出，棧的內部結構，棧的底層實現可以是vector，deque，list 都是可以的， 主要就是數組和鏈表的底層實現。

<stack> /st?k/

• 棧頂插入(push)
• 棧頂彈出(pop)
• 棧頂獲取元素(top)
• 判斷是否為空(empty)

#include <iostream>
#include <stack>
using namespace std;int main(){stack<int> s1;s1.push(1);s1.push(2);s1.pop();cout<<s1.top();while(!s1.empty()){cout<<s1.top();s1.pop();}cout<<endl;// ==== 作為容器適配器 ====stack<int,deque<int>> s2;s2.push(1);s2.push(2);s2.pop();cout<<s2.top();while(!s2.empty()){cout<<s2.top();s2.pop();}return 0;
}

<queue> /kju?/

• 插入(push)
• 刪除(pop)
• 獲取隊首(front)
• 獲取隊尾(back)
• 判斷非空(empty)

#include <queue>
#include <iostream>
using namespace std;
int main(){queue<int> q1;q1.push(1);q1.push(2);q1.push(3);// 首cout<<q1.front()<<endl;// 尾cout<<q1.back()<<endl;// 循環取出while(!q1.empty()){cout<<q1.front()<<endl;q1.pop();}return 0;
}

大綱

基礎

一、用棧實現隊列-（解析）-基礎

二、用隊列實現棧-（解析）-基礎

三、有效的括號-（解析）-棧的基礎應用

四、刪除字符串中的所有相鄰重復項-（解析）-棧的基礎應用

五、?逆波蘭表達式求值-（解析）-棧的基礎應用

?六、滑動窗口最大值-（解析）-單調棧的基本應用

七、前 K 個高頻元素-（解析）-

藍橋真題

一、買二贈一-（解析）-將隊列做為輔助空間

( ?? ω ?? )?點擊這里，繼續學習其他模塊吧！

題目

基礎練習

一、用棧實現隊列

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現?MyQueue?類：

• void push(int x)?將元素 x 推到隊列的末尾
• int pop()?從隊列的開頭移除并返回元素
• int peek()?返回隊列開頭的元素
• boolean empty()?如果隊列為空，返回?true?；否則，返回?false

說明：

• 你?只能?使用標準的棧操作 —— 也就是只有?push to top,?peek/pop from top,?size, 和?is empty?操作是合法的。
• 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

示例 1：

輸入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 1, 1, false]解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多調用?100?次?push、pop、peek?和?empty
• 假設所有操作都是有效的 （例如，一個空的隊列不會調用?pop?或者?peek?操作）

class MyQueue {
private:stack<int> s1;stack<int> s2;
public:// 推入void push(int val){s1.push(val);}// 交換函數void Swap(stack<int>& s1, stack<int>& s2){while(!s1.empty()){s2.push(s1.top());s1.pop();}}// 移除int pop(){Swap(s1,s2);int cur = s2.top();s2.pop();Swap(s2,s1);return cur;}// 返回開頭元素int peek(){Swap(s1,s2);int cur = s2.top();Swap(s2,s1);return cur;}// 判斷非空bool empty(){return s1.empty();}};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

二、用隊列實現棧

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop?和?empty）。

實現?MyStack?類：

• void push(int x)?將元素 x 壓入棧頂。
• int pop()?移除并返回棧頂元素。
• int top()?返回棧頂元素。
• boolean empty()?如果棧是空的，返回?true?；否則，返回?false?。

注意：

• 你只能使用隊列的標準操作 —— 也就是?push to back、peek/pop from front、size?和?is empty?這些操作。
• 你所使用的語言也許不支持隊列。?你可以使用 list （列表）或者 deque（雙端隊列）來模擬一個隊列?, 只要是標準的隊列操作即可。

示例：

輸入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 2, 2, false]解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

• 1 <= x <= 9
• 最多調用100?次?push、pop、top?和?empty
• 每次調用?pop?和?top?都保證棧不為空

class MyStack {
private:queue<int> q1;queue<int> q2;
public:// 壓入元素void push(int val){q1.push(val);}// 交換元素void Swap(queue<int>& q1, queue<int>& q2){while(q1.size()>1){q2.push(q1.front());q1.pop();}}// 移除元素int pop(){ // 移除元素Swap(q1,q2);int val = q1.front();q1.pop();Swap(q2,q1);if(q2.size()!=0){q1.push(q2.front());q2.pop();}return val;}// 取出元素int top(){Swap(q1,q2);int val = q1.front();q2.push(val);q1.pop();Swap(q2,q1);if(q2.size()!=0){q1.push(q2.front());q2.pop();}return val;}// 判斷非空bool empty(){return q1.empty();}};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

三、有效的括號

給定一個只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右括號都有一個對應的相同類型的左括號。

示例 1：

輸入：s = "()"

輸出：true

示例 2：

輸入：s = "()[]{}"

輸出：true

示例 3：

輸入：s = "(]"

輸出：false

示例 4：

輸入：s = "([])"

輸出：true

提示：

• 1 <= s.length <= 104
• s?僅由括號?'()[]{}'?組成

class Solution {// 解決符號問題，就是stack的專場// 考慮的不夠周全/*3種特殊情況右括號的情況：1、右括號的左邊不是對應括號2、出現右括號，但是stack為空意外情況：1、字符串遍歷完，仍然還有符號*/
public:bool isValid(string s) {stack<int> myStack;for(char c : s){if(c=='('||c=='['||c=='{') myStack.push(c);else{if(myStack.size()==0) return false;else {char ch = myStack.top();if(ch=='('&&c==')') myStack.pop();else if(ch=='['&&c==']')  myStack.pop();else if(ch=='{'&&c=='}')  myStack.pop();else return false;}}}if(myStack.size()!=0) return false;return true;}
};

四、刪除字符串中的所有相鄰重復項

給出由小寫字母組成的字符串?s，重復項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。

在?s?上反復執行重復項刪除操作，直到無法繼續刪除。

在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。

示例：

輸入："abbaca"
輸出："ca"
解釋：
例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時唯一可以執行刪除操作的重復項。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執行重復項刪除操作，所以最后的字符串為 "ca"。

提示：

1. 1 <= s.length <= 105
2. s?僅由小寫英文字母組成。

class Solution {// 相鄰匹配問題，stack的專場stack<char> myStack; 
public:string removeDuplicates(string s) {for(char c : s){if(!myStack.empty() && myStack.top()==c) myStack.pop();else myStack.push(c);}string str="";while(!myStack.empty()){str+=myStack.top();myStack.pop();}reverse(str.begin(),str.end());return str;}
};

五、逆波蘭表達式求值

給你一個字符串數組?tokens?，表示一個根據?逆波蘭表示法?表示的算術表達式。

請你計算該表達式。返回一個表示表達式值的整數。

注意：

• 有效的算符為?'+'、'-'、'*'?和?'/'?。
• 每個操作數（運算對象）都可以是一個整數或者另一個表達式。
• 兩個整數之間的除法總是?向零截斷?。
• 表達式中不含除零運算。
• 輸入是一個根據逆波蘭表示法表示的算術表達式。
• 答案及所有中間計算結果可以用?32 位?整數表示。

示例?1：

輸入：tokens = ["2","1","+","3","*"]
輸出：9
解釋：該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9

示例?2：

輸入：tokens = ["4","13","5","/","+"]
輸出：6
解釋：該算式轉化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6

示例?3：

輸入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
輸出：22
解釋：該算式轉化為常見的中綴算術表達式為：((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

• 1 <= tokens.length <= 104
• tokens[i]?是一個算符（"+"、"-"、"*"?或?"/"），或是在范圍?[-200, 200]?內的一個整數

逆波蘭表達式：

逆波蘭表達式是一種后綴表達式，所謂后綴就是指算符寫在后面。

• 平常使用的算式則是一種中綴表達式，如?( 1 + 2 ) * ( 3 + 4 )?。
• 該算式的逆波蘭表達式寫法為?( ( 1 2 + ) ( 3 4 + ) * )?。

逆波蘭表達式主要有以下兩個優點：

• 去掉括號后表達式無歧義，上式即便寫成?1 2 + 3 4 + * 也可以依據次序計算出正確結果。
• 適合用棧操作運算：遇到數字則入棧；遇到算符則取出棧頂兩個數字進行計算，并將結果壓入棧中

class Solution {// 棧是符號表達式的專場stack<long long> s;
public:int evalRPN(vector<string>& tokens) {for(string str : tokens){if(str=="+"||str=="-"||str=="*"||str=="/"){int num2 = s.top(); s.pop();int num1 = s.top(); s.pop();if(str=="+") s.push(num1+num2);else if(str=="-") s.push(num1-num2);else if(str=="*") s.push(num1*num2);else s.push(num1/num2);}else s.push(stoll(str));}return s.top();}
};

六、滑動窗口最大值

給你一個整數數組?nums，有一個大小為?k?的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的?k?個數字。滑動窗口每次只向右移動一位。

返回?滑動窗口中的最大值?。

示例 1：

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

輸入：nums = [1], k = 1
輸出：[1]

提示：

• 1 <= nums.length <= 105
• -104?<= nums[i] <= 104
• 1 <= k <= nums.length

class Solution {
private:struct myQueue{ // 手搓，單調隊列 vprivate:deque<int> myDeque;public:void push(int val){ // 放while(!myDeque.empty()&&myDeque.back()<val) myDeque.pop_back();myDeque.push_back(val);}void pop(int val){ // 彈出if(!myDeque.empty() && val==myDeque.front()) myDeque.pop_front();}int front(){ // 輸出if(!myDeque.empty()) return myDeque.front();return 0;}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> vec;myQueue mq;for(int i=0; i<k; ++i) mq.push(nums[i]); // 存入vec.push_back(mq.front()); for(int i=k; i<nums.size(); ++i){mq.pop(nums[i-k]);mq.push(nums[i]);int val = mq.front();vec.push_back(mq.front());}return vec;}
};

七、前 K 個高頻元素

給你一個整數數組?nums?和一個整數?k?，請你返回其中出現頻率前?k?高的元素。你可以按?任意順序?返回答案。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

提示：

• 1 <= nums.length <= 105
• k?的取值范圍是?[1, 數組中不相同的元素的個數]
• 題目數據保證答案唯一，換句話說，數組中前?k?個高頻元素的集合是唯一的

進階：你所設計算法的時間復雜度?必須?優于?O(n log n)?，其中?n?是數組大小。

噠噠噠，后續補充

藍橋真題

一、買二贈一

問題描述

某商場有?NN?件商品，其中第?ii?件的價格是?AiAi?。現在該商場正在進行 “買二贈一” 的優惠活動，具體規則是：每購買?22?件商品，假設其中較便宜的價格是?PP（如果兩件商品價格一樣，則?PP?等于其中一件商品的價格），就可以從剩余商品中任選一件價格不超過?P22P??的商品，免費獲得這一件商品。可以通過反復購買?22?件商品來獲得多件免費商品，但是每件商品只能被購買或免費獲得一次。

小明想知道如果要拿下所有商品（包含購買和免費獲得），至少要花費多少錢？

輸入格式

第一行包含一個整數?NN。

第二行包含?NN?個整數，代表?A1,A2,A3,…,ANA1?,A2?,A3?,…,AN?。

輸出格式

輸出一個整數，代表答案。

樣例輸入

7
1 4 2 8 5 7 1

樣例輸出

25

樣例說明

小明可以先購買價格?44?和?88?的商品，免費獲得一件價格為?11?的商品；再后買價格為?55?和?77?的商品，免費獲得價格為?22?的商品；最后單獨購買剩下的一件價格為?11?的商品。總計花費?4+8+5+7+1=254+8+5+7+1=25。不存在花費更低的方案。

評測用例規模與約定

對于?3030% 的數據，1≤N≤201≤N≤20。

對于?100100% 的數據，1≤N≤5×1051≤N≤5×105，1≤Ai≤1091≤Ai?≤109。

Java版：

import java.util.*;
// 重點在于Queue這種輔助空間，不易想到
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 讀取輸入的元素個數int n = scanner.nextInt();// 創建一個長整型數組來存儲輸入的元素long[] vec = new long[n];for (int i = 0; i < n; i++) {// 讀取每個元素并存儲到數組中vec[i] = scanner.nextLong();}// 對數組進行降序排序Arrays.sort(vec);reverseArray(vec);// 創建一個隊列來存儲處理后的元素Queue<Long> que = new LinkedList<>();int k = 0;long sum = 0;// 遍歷排序后的數組for (int i = 0; i < n; i++) {// 如果隊列不為空且隊列頭部元素大于等于當前數組元素if (!que.isEmpty() && que.peek() >= vec[i]) {// 移除隊列頭部元素que.poll();continue;}// 如果 k 小于 2if (k < 2) {k++;// 累加當前數組元素到總和中sum += vec[i];}// 如果 k 大于等于 2if (k >= 2) {// 將當前數組元素除以 2 后加入隊列que.add(vec[i] / 2);k = 0;}}// 輸出總和System.out.println(sum);scanner.close();}// 反轉數組元素順序以實現降序排序public static void reverseArray(long[] arr) {int left = 0;int right = arr.length - 1;while (left < right) {long temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}
}

C++版：

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define ll long long
using namespace std;
// 重點在于，queue這種輔助空間，不會輕易被想到
bool cmp(ll a, ll b){return a>b;
}
int main()
{// 理智，一點int n;cin>>n;vector<ll> vec(n);for(int i=0; i<n; ++i) cin>>vec[i];sort(vec.begin(),vec.end(),cmp); // 排序queue<ll> que;int k=0;ll sum=0;for(int i=0; i<n; ++i){if(!que.empty()&&que.front()>=vec[i]){que.pop();continue;}if(k<2){k++;sum+=vec[i];}if(k>=2){que.push(vec[i]/2);k=0;}}cout<<sum<<endl;return 0;
}

知識點

1、析構函數的作用

• 自動調用：其作用是，在對象生命周期結束時自動釋放資源，防止資源泄露。
• 怎么調用：類名(){...}前加上~，代表析構。
• 默認實現：未被顯示定義，編輯器會自動生成一個空析構函數。

2、C++標準庫<deque> /dek/

deque /dek/ 是標準模版庫(STL)的一部分，他提供了雙端隊列（double-ended queue）的實現。

是一種允許，在兩端進行插入和刪除操作的線性數據結構。

并且<deque>的隨機訪問時間復雜度為O(1)。

不過deque?是由多個連續的存儲塊組成的，這些存儲塊在內存中不一定是連續的。只是隨機訪問的話，還是vector(頭插O(n),尾插O(1))比較合適。

#include <iostream>
#include <deque>
using namespace std;
int main(){deque<int> myDeque;// 插入myDeque.push_back(3);myDeque.push_back(4);myDeque.push_front(2);myDeque.push_front(1);// 訪問元素for(int i=0; i<myDeque.size(); ++i){cout<<myDeque[i]<<endl;}// 刪除元素myDeque.pop_back();myDeque.pop_front();// 訪問頭部與尾部元素cout<<myDeque.front()<<endl;cout<<myDeque.back()<<endl;return 0;
}

---

借鑒博客：

1、數據結構：棧和隊列(Stack & Queue)【詳解】

2、棧和隊列（詳細版，一看就懂。包含棧和隊列的定義、意義、區別，實現）

3、棧與隊列理論基礎

4、C++ 標準庫?<stack>

5、C++ 容器類 <queue>

---

( ?? ω ?? )?點擊這里，繼續學習其他模塊吧！