📝前言說明：
本專欄主要記錄本人的基礎算法學習以及刷題記錄，使用語言為C++。
每道題我會給出LeetCode上的題號（如果有題號），題目，以及最后通過的代碼。沒有題號的題目大多來自牛客網。對于題目的講解，主要是個人見解，如有不正確，歡迎指正，一起進步！

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C++學習筆記，C語言入門基礎，python入門基礎，python刷題專欄
🎀CSDN主頁 愚潤澤

20. 有效的括號

經典的括號匹配題：利用棧。遇到左括號：入棧，遇到右括號：出棧
不過寫代碼時要注意：因為我們要讓'(' 匹配 ')'，所以遇到左括號時，直接將它對應的右括號入棧，后續可以直接字符比較判斷。

class Solution {
public:bool isValid(string s) {stack<char> st;for(auto ch : s){if(ch == '('){st.push(')'); // 需要匹配的}else if (ch == '['){st.push(']');}else if (ch == '{'){st.push('}');}else{if( st.empty() || ch != st.top()){ // 這里要先判斷棧是否為空return false;}st.pop();}}return st.empty();}
};

225. 用隊列實現棧

首先我們要了解棧的特點：先進后出，隊列的特點：先進先出
因此，這道題的難點在于：如何讓新入隊的元素處于隊頭？

這道題給了我們兩個隊列，如果將一個隊列當做主隊列（即棧），另一個隊列作為輔助隊列，我們就可以利用輔助隊列來改變新入隊的元素的位置：
前提：每次操作前，輔助隊列要為空。
思想：如果直接讓新元素進主隊列，那這個元素肯定是最后一個了，但是直接讓新元素進輔助隊列，那這個新元素就是輔助的第一個元素。所以我們先讓新元素進入輔助隊列，然后再把主隊列（棧）里的元素依次出棧放入輔助隊列，這樣在輔助隊列里新元素第一個出隊列，而其他元素的出隊列順序與原來的主隊列（棧）保持一致。這時候我們再交換輔助隊列和主隊列的身份。

class MyStack {
public:queue<int> queue1; queue<int> queue2; MyStack() {}void push(int x) {queue2.push(x); // 把新元素放到輔助隊列while(!queue1.empty()){queue2.push(queue1.front()); // 依次將棧的元素放入輔助隊列queue1.pop();}swap(queue1, queue2);}int pop() {int r = queue1.front();queue1.pop();return r;}int top() {return queue1.front();}bool empty() {return queue1.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();*/

232. 用棧實現隊列

只需要讓一個棧進，一個棧負責出就行了。當一個棧的元素全部倒入另一個棧，這時候元素的出入順序就會完全改變一次。（為了節約時間，我們只在outStack里面元素徹底為空且遇到出棧需求時，才將inStack的數據倒入`outStack）

class MyQueue {
public:stack<int> inStack, outStack;void in_to_out(){ // 倒轉while(!inStack.empty()){outStack.push(inStack.top());inStack.pop();}}MyQueue() {}void push(int x) {inStack.push(x);}int pop() {if(outStack.empty()){in_to_out();}int r = outStack.top();outStack.pop(); return r;}int peek() {if(outStack.empty()){in_to_out();}return outStack.top();}bool empty() {return inStack.empty() && outStack.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();*/

622. 設計循環隊列

下面解法以數組為例：
環形隊列的關鍵在于：1，如何通過取模來達到走環的效果；2，如何判斷隊列滿和空的情況。
對于循環：當一個數+1時可能超出最大值，則需要%來控制此數的大小任然在下標范圍內；
對于判空：起始時front指針和rear指針都指向空；對于滿，我們可以犧牲一個空間，即：當rear+1 == front的時候為滿（但注意rear + 1要確保在數組下標內）。
下面做法以front的后一位為第一個數據位為例：

class MyCircularQueue {
public:// 用數組來模擬循環隊列，讓front指向的位置為空，front下一個位置才有節點// front == rear時為空，當 rear + 1 == front 時為滿 MyCircularQueue(int k) {capacity = k;front = rear = 0;que = vector<int> (k+1); // 比容量多開一個空間，則數組下標為[0, k]（后續我們要讓rear和front的下標在這個范圍內，不然會越界）}bool enQueue(int value) {if(isFull()){return false;}rear = (rear + 1) % (capacity + 1);  que[rear] = value;return true;}bool deQueue() {if(isEmpty()){return false;}front = (front + 1) % (capacity + 1);return true;}int Front() {if(isEmpty()){return -1;}return que[(front + 1) % (capacity + 1)];}int Rear() {if(isEmpty()){return -1;}return que[rear];}bool isEmpty() {return rear == front;}bool isFull() {return ((rear + 1) % (capacity + 1)) == front;}private:int front;int rear;int capacity;vector<int> que;
};/*** Your MyCircularQueue object will be instantiated and called as such:* MyCircularQueue* obj = new MyCircularQueue(k);* bool param_1 = obj->enQueue(value);* bool param_2 = obj->deQueue();* int param_3 = obj->Front();* int param_4 = obj->Rear();* bool param_5 = obj->isEmpty();* bool param_6 = obj->isFull();*/

面試題03.05. 棧排序

這道題的題目表述不清楚，看示例可以發現，實際上是往棧里面插入元素，要保證插入后的順序從棧底到棧頂是從大到小的。
我們只需要將每次要插入的元素和棧中已經有的元素作比較，找到合適的位置插入。
如：棧頂元素為t，要插入元素為val，如果val < t，就直接入棧，否則，先讓t進入輔助棧，重復此過程，直到找到合適的位置插入，插入完后，把st2的元素倒回來。

class SortedStack {
public:SortedStack() {}void push(int val) {while( !st1.empty() && st1.top() < val){st2.push(st1.top()); // 把st1的元素暫存到st2st1.pop();}st1.push(val);// 把st2的元素倒回來while(!st2.empty()){st1.push(st2.top());st2.pop();}}void pop() {if(!st1.empty()){st1.pop();}}int peek() {if(!st1.empty()){return st1.top();}return -1;}bool isEmpty() {return st1.empty();}
private:stack<int> st1, st2;
};/*** Your SortedStack object will be instantiated and called as such:* SortedStack* obj = new SortedStack();* obj->push(val);* obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->isEmpty();*/

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！