第三章节 栈和队列

参考：1.数据结构C语言版|第2版；2.力扣；3.2025年数据结构考研复习指导。三个参考分别依次对应文章三个部分。

文章目录

• 第一部分
• • 栈
  • • 基本概念
    • 栈的实现
    • • 顺序栈的实现
      • 链栈的实现
    • 经典案例
    • • 进制转换
      • 括号匹配
      • 求解表达式的结果
  • 队列
  • • 基本概念
    • 队列的实现
    • • 顺序队列的实现
      • 链队列的实现
    • 经典案例
    • • 舞伴问题
  • 递归
  • • 基本概念
    • 经典案例
    • • 函数定义
      • 某种操作
    • 递归分析
  • 递归与栈
• 第二部分
• • 栈
  • • • 20. 有效的括号
      • 32. 最长有效括号
      • 1047. 删除字符串中的所有相邻的重复项
      • 1190. 反转每对括号间的子串
    • 单调栈
    • • 42. 接雨水
      • 84. 柱状图中的最大矩形
      • 85. 最大矩形
      • 456. 132模式
      • 496. 下一个更大元素I
      • 503. 下一个更大元素II
      • 739. 每日温度
      • 1475. 商品折扣后的最终价格
      • 2454. 下一个更大元素IV
  • 队列
  • • • 649. Dota2参议院
      • 1047. 删除字符串中的所有相邻的重复项
      • 1190. 反转每对括号间的子串
    • 单调队列
    • • 239. 滑动窗口的最大值
• 第三部分

第一部分

栈

基本概念

栈的定义：栈是限定仅在表尾进行插入和删除操作的线性表。栈顶、栈底、空栈（顾名思义）。栈的特点：后进先出。

栈的实现

顺序栈的实现

顺序栈（顾名思义）

#include
using namespace std;
struct Stack
{
    int max_size;
    int now_size;
    int * datas;
};
void Init(Stack & my_stack,int max_size)
{
    my_stack.max_size=max_size;
    my_stack.now_size=0;
    my_stack.datas=new int [max_size];
}
void Destroy(Stack & my_stack)
{
    my_stack.max_size=-1;
    my_stack.now_size=-1;
    delete [] my_stack.datas;
}
bool IsEmpty(const Stack & my_stack)
{
    return my_stack.now_size==0;
}
int GetSize(const Stack & my_stack)
{
    return my_stack.now_size;
}
int GetTop(const Stack & my_stack)
{
    if (IsEmpty(my_stack)) {cout<<"\'my_stack\' hasn\'t any data"<<endl;return INT_MIN;}
    return my_stack.datas[my_stack.now_size-1]; 
}
void Push(Stack & my_stack,int data)
{
    if (my_stack.now_size==my_stack.max_size) cout<<"\'my_stack\' has already been full."<<endl;
    my_stack.datas[my_stack.now_size]=data;my_stack.now_size+=1;
}
void Pop(Stack & my_stack)
{
    if (IsEmpty(my_stack)) cout<<"\'my_stack\' hasn\'t any data"<<endl;
    my_stack.now_size-=1;
}
int main()
{
    Stack my_stack;Init(my_stack,10);
    for (int i=0;i<6;i++)
        Push(my_stack,i);
    for (int i=0;i<5;i++)
        Pop(my_stack);
    cout<<IsEmpty(my_stack)<<";"<<GetSize(my_stack)<<";"<<GetTop(my_stack);
    Destroy(my_stack);return 0;
}

链栈的实现

链栈（顾名思义）

#include
using namespace std;
struct Node
{
    int data;
    Node * next;
};
void InitNode(Node * & node)
{
    node=new Node;node->next=nullptr;
}
void InitStack(Node * & my_stack)
{
    my_stack=nullptr;
}
void DestoryNode(Node * & node)
{
    delete node;
}
void DestoryStack(Node * & my_stack)
{
    while (my_stack!=nullptr)
    {
        Node * temp=my_stack;my_stack=my_stack->next;DestoryNode(temp);
    }
}
bool IsEmpty(Node * & my_stack)
{
    return my_stack==nullptr;
}
int GetSize(Node * & my_stack)
{
    int result=0;Node * temp=my_stack;
    while (temp!=nullptr) {temp=temp->next;result+=1;}
    return result;
}
int GetTop(Node * & my_stack)
{
    if (IsEmpty(my_stack)) {cout<<"\'my_stack\' hasn\'t any data"<data;
}
void Push(Node * & my_stack,int data)
{
    Node * next;InitNode(next);next->data=data;
    next->next=my_stack;my_stack=next;
}
void Pop(Node * & my_stack)
{
    if (IsEmpty(my_stack)) cout<<"\'my_stack\' hasn\'t any data"<next;DestoryNode(temp);
}
int main()
{
    Node * my_stack;InitStack(my_stack);
    for (int i=0;i<6;i++)
        Push(my_stack,i);
    for (int i=0;i<5;i++)
        Pop(my_stack);
    cout<<IsEmpty(my_stack)<<";"<<GetSize(my_stack)<<";"<<GetTop(my_stack);
    DestoryStack(my_stack);return 0;
}

经典案例

进制转换

题面描述：将十进制数转换为八进制数

代码如下：

#include
#include
using namespace std;
int transform(int n)
{
    stack my_stack;
    while (n) {my_stack.push(n%8);n/=8;}
    int x=0;
    while (!my_stack.empty()) {x*=10;x+=my_stack.top();my_stack.pop();}
    return x;
}
int main()
{
    cout<<transform(55);
    return 0;
}

括号匹配

题面描述：力扣20题

代码如下：

class Solution {
public:
    bool isValid(string s) {
        stack my_stack;
        for (int i=0;i<s.size();i++)
            if (s[i]=='(' or s[i]=='{' or s[i]=='[')
                my_stack.push(s[i]);
            else
            {
                if (my_stack.empty() or\
                   (s[i]==')' and my_stack.top()!='(') or\
                   (s[i]==']' and my_stack.top()!='[') or\
                   (s[i]=='}' and my_stack.top()!='{'))
                    return false;
                my_stack.pop();
            }
        if (!my_stack.empty()) return false;
        return true;
    }
};

求解表达式的结果

题面描述：懂的都懂（是太长了，不想码字）

代码如下：

#include
#include
#include
using namespace std;
pair read_number(char * s)
{
    int x=s[0]-'0',len=1;
    while (s[len]>='0' and s[len]<='9')
    {
        x*=10;x+=s[len]-'0';len+=1;
    }
    return make_pair(x,len);
}
double calculate(char * s)
{
    int i=0;stack my_stack1;stack my_stack2;
    while (s[i]!='\0')
    {
        if (s[i]>='0' and s[i]<='9')
        {
            pair temp=read_number(s+i);
            if (!my_stack2.empty() and (my_stack2.top()=='*' or my_stack2.top()=='/'))
            {
                double x=my_stack1.top();my_stack1.pop();char y=my_stack2.top();my_stack2.pop();
                if (y=='*') my_stack1.push(x*temp.first);
                else my_stack1.push(x/temp.first);
            }
            else my_stack1.push(temp.first);
            i+=temp.second;
            continue;
        }
        else if (s[i]!=')') my_stack2.push(s[i]);
        else
        {
            while (my_stack2.top()!='(')
            {
                double x=my_stack1.top();my_stack1.pop();
                double y=my_stack1.top();my_stack1.pop();
                char z=my_stack2.top();my_stack2.pop();
                if (z=='+') my_stack1.push(y+x);
                else my_stack1.push(y-x);
            }
            my_stack2.pop();
            if (!my_stack2.empty() and (my_stack2.top()=='*' or my_stack2.top()=='/'))
            {
                double x=my_stack1.top();my_stack1.pop();
                double y=my_stack1.top();my_stack1.pop();
                char z=my_stack2.top();my_stack2.pop();
                if (z=='*') my_stack1.push(y*x);
                else my_stack1.push(y/x);
            }
        }
        i+=1;
    }
    while (!my_stack2.empty())
    {
        double x=my_stack1.top();my_stack1.pop();
        double y=my_stack1.top();my_stack1.pop();
        char z=my_stack2.top();my_stack2.pop();
        if (z=='+') my_stack1.push(y+x);
        else my_stack1.push(y-x);
    }
    double temp=my_stack1.top();my_stack1.pop();return temp;
}
int main()
{
    //首先式子必须合法，然后数字必须为整。
    char s1[]="1+2+3+4+5+6+7+8+9";
    char s2[]="1*2*3*4*5*6*7*8*9";
    char s3[]="(1+2)+(3+4)+(5+6)+(7+8)";
    char s4[]="(1*2)*(3*4)*(5*6)*(7*8)";
    char s5[]="(1+2)*(3+4)*(4+6)*(7+8)";
    char s6[]="(1*2)+(3*4)+(4*6)+(7*8)";
    char s7[]="((1*2)+(3*4))*((5*6)+(7*8))";
    char s8[]="1+5*((10*20+1)+(1+30*400))*((400*30+1)+(1+20*10))*5+1";
    cout<<fixed<<setprecision(2);
    cout<<calculate(s1)<<endl\
        <<calculate(s2)<<endl\
        <<calculate(s3)<<endl\
        <<calculate(s4)<<endl\
        <<calculate(s5)<<endl\
        <<calculate(s6)<<endl\
        <<calculate(s7)<<endl\
        <<calculate(s8)<<endl;
    return 0;
}

队列

基本概念

队列的定义：队列是限定仅在表头进行删除和表尾进行插入操作的线性表。队头、队尾、空队列（顾名思义）。队列的特点：先进先出。

队列的实现

顺序队列的实现

顺序队列（顾名思义）

#include
using namespace std;
struct Queue
{
    int max_size;
    int * data;
    int begin;
    int end;
};
void Init(Queue & my_queue,int max_size)
{
    my_queue.max_size=max_size;
    my_queue.data=new int [max_size];
    my_queue.begin=0;
    my_queue.end=0;
}
void Destroy(Queue & my_queue)
{
    my_queue.max_size=-1;
    delete [] my_queue.data;
    my_queue.begin=-1;
    my_queue.end=-1;
}
int GetSize(const Queue & my_queue)
{
    return (my_queue.end-my_queue.begin+my_queue.max_size)%my_queue.max_size;
}
bool IsFull(const Queue & my_queue)
{
    return GetSize(my_queue)==my_queue.max_size-1;
}
bool IsEmpty(const Queue & my_queue)
{
    return GetSize(my_queue)==0;
}
void Push(Queue & my_queue,int data)
{
    if (IsFull(my_queue)) {cout<<"\'my_queue\' has been full."<<endl;return;}
    my_queue.data[my_queue.end%my_queue.max_size]=data;my_queue.end=(my_queue.end+1)%my_queue.max_size;
}
void Pop(Queue & my_queue)
{
    if (IsEmpty(my_queue)) {cout<<"\'my_queue\' hasn\'t any data."<<endl;return;}
    my_queue.begin=(my_queue.begin+1)%my_queue.max_size;
}
int GetFront(const Queue & my_queue)
{
    if (IsEmpty(my_queue)) {cout<<"\'my_queue\' hasn\'t any data."<<endl;INT_MIN;}
    return my_queue.data[my_queue.begin];
}
int GetBack(const Queue & my_queue)
{
    if (IsEmpty(my_queue)) {cout<<"\'my_queue\' hasn\'t any data."<<endl;INT_MIN;}
    return my_queue.data[(my_queue.end+my_queue.max_size-1)%my_queue.max_size];
}
int main()
{
    Queue my_queue;Init(my_queue,10);
    for (int i=0;i<6;i++)
        Push(my_queue,i);
    for (int i=0;i<5;i++)
        Pop(my_queue);
    cout<<GetSize(my_queue)<<endl<<GetFront(my_queue)<<endl<<GetBack(my_queue);
    Destroy(my_queue);return 0;
}

顺序队列实现的本质是采用循环队列！顺序队列实现的本质是采用循环队列！重要的事情说两遍！重要的事情说两遍！

链队列的实现

链队列（顾名思义）

#include
using namespace std;
struct Node
{
    int data;
    Node * next;
};
void InitNode(Node * & node)
{
    node=new Node;node->next=nullptr;
}
void DestroyNode(Node * & node)
{
    delete node;
}
struct Queue
{
    Node * begin;
    Node * end;
};
void InitQueue(Queue & my_queue)
{
    my_queue.begin=nullptr;my_queue.end=nullptr;
}
void DestroyQueue(Queue & my_queue)
{
    while (my_queue.begin!=nullptr)
    {
        Node * temp=my_queue.begin;my_queue.begin=my_queue.begin->next;DestroyNode(temp);
    }
}
void Push(Queue & my_queue,int data)
{
    Node * node=new Node;InitNode(node);node->data=data;
    if (my_queue.end==nullptr) {my_queue.begin=node;my_queue.end=node;}
    else {my_queue.end->next=node;my_queue.end=my_queue.end->next;}
}
void Pop(Queue & my_queue)
{
    if (my_queue.begin==nullptr) {cout<<"\'my_queue\' hasn\'t any data."<next;DestroyNode(temp);
}
int GetFront(Queue & my_queue)
{
    return my_queue.begin->data;
}
int GetBack(Queue & my_queue)
{
    return my_queue.end->data;
}
int GetSize(Queue & my_queue)
{
    int result=0;Node * temp=my_queue.begin;
    while (temp!=nullptr) {temp=temp->next;result+=1;}
    return result;
}
bool IsEmpty(Queue & my_queue)
{
    return my_queue.end==nullptr;
}
int main()
{
    Queue my_queue;InitQueue(my_queue);
    for (int i=0;i<6;i++)
        Push(my_queue,i);
    for (int i=0;i<5;i++)
        Pop(my_queue);
    cout<<GetSize(my_queue)<<endl<<GetFront(my_queue)<<endl<<GetBack(my_queue);
    DestroyQueue(my_queue);return 0;
}

经典案例

舞伴问题

题面描述：懂的都懂（是太长了，不想码字）

代码如下：

#include
#include
#include
using namespace std;
void func(queue & my_queue1,queue & my_queue2)
{
    if (my_queue1.size()>my_queue2.size()) 
    {
        queue temp;temp=my_queue2;my_queue2=my_queue1;my_queue1=temp;
    }
    while (!my_queue2.empty())
    {
        cout<<my_queue2.front()<<";"<<my_queue1.front()<<endl;
        my_queue2.pop();my_queue1.push(my_queue1.front());my_queue1.pop();
    }
}
int main()
{
    string lb1[1]={"LCL"};
    string lb2[3]={"GNZ","YHC","WMQ",};
    queue my_queue1;for (int i=0;i<1;i++) my_queue1.push(lb1[i]);
    queue my_queue2;for (int i=0;i<3;i++) my_queue2.push(lb2[i]);
    func(my_queue1,my_queue2);
    return 0;
}

递归

基本概念

递归的定义：一个问题直接或者间接出现问题本身。问题包括：函数定义，某种操作等等。

经典案例

函数定义

阶乘定义

int factorial(int n)
{
    if (n==0) return 1;
    return n*factorial(n-1);
}

某种操作

懂的都懂

#include
using namespace std;
void move(char A,int n,char C)
{
    cout<<n<<";"<
    if (n==1) move(A,1,C);
    else
    {
        Hanoi(n-1,A,C,B);move(A,n,C);Hanoi(n-1,B,A,C);
    }
}
int main()
{
    Hanoi(4,'A','B','C');
    return 0;
}

递归遍历数据结构

#include
#include
#include
#include
using namespace std;
void func1(vector & my_vector)
{
    if (my_vector.empty()) return;
    cout<<my_vector[my_vector.size()-1]<<" ";my_vector.pop_back();
    func1(my_vector);
}
void func2(queue & my_queue)
{
    if (my_queue.empty()) return;
    cout<<my_queue.front()<<" ";my_queue.pop();
    func2(my_queue);
}
void func3(stack & my_stack)
{
    if (my_stack.empty()) return;
    cout<<my_stack.top()<<" ";my_stack.pop();
    func3(my_stack);
}
int main()
{
    vector my_vector;queue my_queue;stack my_stack;
    for (int i=0;i<10;i++)
    {
        my_vector.push_back(i);my_queue.push(i);my_stack.push(i);
    }
    func1(my_vector);cout<<endl;
    func2(my_queue);cout<<endl;
    func3(my_stack);cout<<endl;
}

递归分析

该咋分析，就咋分析。并不特别，迎难而上。

递归与栈

例子后面章节很多，这里我们暂时跳过。

第二部分

栈

20. 有效的括号

class Solution {
public:
    bool isValid(string s) {
        stack my_stack;
        for (int i=0;i<s.size();i++)
            if (s[i]=='(' or s[i]=='{' or s[i]=='[')
                my_stack.push(s[i]);
            else
            {
                if (my_stack.empty() or\
                   (s[i]==')' and my_stack.top()!='(') or\
                   (s[i]==']' and my_stack.top()!='[') or\
                   (s[i]=='}' and my_stack.top()!='{'))
                    return false;
                my_stack.pop();
            }
        if (!my_stack.empty()) return false;
        return true;
    }
};

32. 最长有效括号

class Solution {
public:
    int longestValidParentheses(string s) {
        int result=0;
        stack my_stack;my_stack.push(-1);
        for (int i=0;i<s.length();i++)
            if (s[i] == '(') my_stack.push(i);
            else
            {
                my_stack.pop();
                if (my_stack.empty()) my_stack.push(i);
                else result=max(result,i-my_stack.top());
            }
        return result;
    }
};

1047. 删除字符串中的所有相邻的重复项

class Solution {
public:
    string removeDuplicates(string s) {
        stack z;
        for (int i=0;i<s.size();i++)
            if (z.empty()) z.push(s[i]);
            else
            {
                if (s[i]==z.top()) z.pop();
                else z.push(s[i]);
            }
        string result;
        while (!z.empty()) {result+=z.top();z.pop();}
        reverse(result.begin(),result.end());
        return result;
    }
};

1190. 反转每对括号间的子串

class Solution {
public:
    string reverseParentheses(string s) {
        stack z;
        for (int i=0;i<s.size();i++)
            if (s[i]!=')') z.push(s[i]);
            else
            {
                string s_temp;
                while (1)
                {
                    if (z.top()=='(')
                    {
                        z.pop();
                        for (int i=0;i<s_temp.size();i++)
                            z.push(s_temp[i]);
                        break;
                    }
                    s_temp+=z.top();z.pop();
                }
            }
        string result;
        while (!z.empty()) {result+=z.top();z.pop();}
        reverse(result.begin(),result.end());
        return result;
    }
};

单调栈

42. 接雨水

class Solution {
public:
    int trap(vector& height) {
        int result=0;
        stack my_stack;int top;
        for (int i=0;i<height.size();i++)
        {
            while (!my_stack.empty() and height[i]>=height[my_stack.top()])
            {
                top=my_stack.top();my_stack.pop();
                if (!my_stack.empty())
                    result+=(min(height[my_stack.top()],height[i])-height[top])*(i-my_stack.top()-1);
            }
            my_stack.push(i);
        }
        return result;
    }
};

84. 柱状图中的最大矩形

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        vector my_vector1(heights.size(),-1);
        stack my_stack1;
        for (int i=0;i<heights.size();i++)
        {
            while (!my_stack1.empty() and heights[i]<heights[my_stack1.top()])
            {
                my_vector1[my_stack1.top()]=i;my_stack1.pop();
            }
            my_stack1.push(i);
        }
        vector my_vector2(heights.size(),-1);
        stack my_stack2;
        for (int i=heights.size()-1;i>=0;i--)
        {
            while (!my_stack2.empty() and heights[i]<heights[my_stack2.top()])
            {
                my_vector2[my_stack2.top()]=i;my_stack2.pop();
            }
            my_stack2.push(i);
        }
        int result=0;
        for (int i=0;i<heights.size();i++)
        {
            int r,l;
            if (my_vector1[i]==-1) r=heights.size()-1-i;
            else r=my_vector1[i]-1-i;
            if (my_vector2[i]==-1) l=i;
            else l=i-1-my_vector2[i];
            int result_temp=heights[i]*(r+l+1);
            if (result_temp>result) result=result_temp;
        }
        return result;
    }
};

85. 最大矩形

class Solution {
public:
    int maximalRectangle(vector<vector>& matrix) {
        vector<vector> my_matrix(matrix.size(),vector (matrix[0].size()));
        for (int i=0;i<matrix[0].size();i++)
            my_matrix[0][i]=(matrix[0][i]-'0');
        for (int i=1;i<matrix.size();i++)
            for (int j=0;j<matrix[0].size();j++)
                my_matrix[i][j]=matrix[i][j]=='0'?0:my_matrix[i-1][j]+(matrix[i][j]-'0');
        int result=0;
        for (int i=0;i<my_matrix.size();i++)
        {
            int result_temp=fc(my_matrix[i]);
            if (result_temp>result) result=result_temp;
        }
        return result;
    }
    int fc(const vector & heights)
    {
        vector my_vector1(heights.size(),-1);
        stack my_stack1;
        for (int i=0;i<heights.size();i++)
        {
            while (!my_stack1.empty() and heights[i]<heights[my_stack1.top()])
            {
                my_vector1[my_stack1.top()]=i;my_stack1.pop();
            }
            my_stack1.push(i);
        }
        vector my_vector2(heights.size(),-1);
        stack my_stack2;
        for (int i=heights.size()-1;i>=0;i--)
        {
            while (!my_stack2.empty() and heights[i]<heights[my_stack2.top()])
            {
                my_vector2[my_stack2.top()]=i;my_stack2.pop();
            }
            my_stack2.push(i);
        }
        int result=0;
        for (int i=0;i<heights.size();i++)
        {
            int r,l;
            if (my_vector1[i]==-1) r=heights.size()-1-i;
            else r=my_vector1[i]-1-i;
            if (my_vector2[i]==-1) l=i;
            else l=i-1-my_vector2[i];
            int result_temp=heights[i]*(r+l+1);
            if (result_temp>result) result=result_temp;
        }
        return result;
    }
};

456. 132模式

class Solution {
public:
    bool find132pattern(vector& nums) {
        stack my_stack;
        int k=INT_MIN;
        for (int i=nums.size()-1;i>=0;i--)
        {
            if (nums[i]my_stack.top())
            { 
                k=max(k,my_stack.top());my_stack.pop();
            }
            my_stack.push(nums[i]);
        }
        return false;
	}
};

496. 下一个更大元素I

class Solution {
public:
    vector nextGreaterElement(vector& nums1, vector& nums2) {
        unordered_map zd;
        stack mystack;
        for (int i=0;i<nums2.size();i++)
        {
            while (!mystack.empty() and nums2[i]>mystack.top())
            {
                zd[mystack.top()]=nums2[i];mystack.pop();
            }
            mystack.push(nums2[i]);
        }
        while (!mystack.empty())
        {
            zd[mystack.top()]=-1;mystack.pop();
        }
        vector result;
        for (int i=0;i<nums1.size();i++)
            result.push_back(zd[nums1[i]]);
        return result;
    }
};

503. 下一个更大元素II

class Solution {
public:
    vector nextGreaterElements(vector& nums) {
        vector result(nums.size(),-1);
        stack my_stack;
        for (int i=0;i<nums.size();i++)
        {
            while (!my_stack.empty() and nums[i]>nums[my_stack.top()])
            {
                result[my_stack.top()]=nums[i];my_stack.pop();
            }
            my_stack.push(i);
        }
        while (!my_stack.empty())
        {
            for (int i=0;inums[my_stack.top()])
                {
                    result[my_stack.top()]=nums[i];break;
                }
            my_stack.pop();
        }
        return result;
    }
};

739. 每日温度

class Solution {
public:
    vector dailyTemperatures(vector& temperatures) {
        vector my_vector(temperatures.size());
        stack my_stack;
        for (int i=0;i<temperatures.size();i++)
        {
            while (!my_stack.empty() and temperatures[i]>temperatures[my_stack.top()])
            {
                my_vector[my_stack.top()]=i-my_stack.top();my_stack.pop();
            }
            my_stack.push(i);
        }
        return my_vector;
    }
};

1475. 商品折扣后的最终价格

class Solution {
public:
    vector finalPrices(vector& prices) {
        stack my_stack;
        for (int i=0;i<prices.size();i++)
        {
            while (!my_stack.empty() and prices[i]<=prices[my_stack.top()])
            {
                prices[my_stack.top()]-=prices[i];my_stack.pop();
            }
            my_stack.push(i);
        }
        return prices;
    }
};

2454. 下一个更大元素IV

class Solution {
public:
    vector secondGreaterElement(vector& nums) {
        vector result(nums.size(),-1),my_stack1,my_stack2;
        for (int i=0;i<nums.size();i++)
        {
            while (!my_stack2.empty() and nums[i]>nums[my_stack2[my_stack2.size()-1]])
            {
                result[my_stack2[my_stack2.size()-1]]=nums[i];my_stack2.pop_back();
            }
            if (!my_stack1.empty())
            {
                int j=my_stack1.size()-1;
                while (j>=0 and  nums[i]>nums[my_stack1[j]]) j-=1;
                j+=1;
                my_stack2.insert(my_stack2.end(),my_stack1.begin()+j,my_stack1.end());
                my_stack1.erase(my_stack1.begin()+j,my_stack1.end());
            }
            my_stack1.push_back(i);
        }
        return result;
    }
};

队列

649. Dota2参议院

class Solution {
public:
    string predictPartyVictory(string senate) {
        queue dl1,dl2;for (int i=0;i<senate.size();i++) dl2.push(senate[i]);
        while (1)
        {
            if (dl1.empty()) {dl1.push(dl2.front());dl2.pop();}
            else
            {
                if (dl2.front()==dl1.front()) {dl1.push(dl2.front());dl2.pop();}
                else {dl2.pop();dl2.push(dl1.front());dl1.pop();}
            }
            if (dl2.empty()) break;
        }
        string result=dl1.front()=='D'?"Dire":"Radiant";
        return result;
    }
};

1047. 删除字符串中的所有相邻的重复项

class Solution {
public:
    string removeDuplicates(string s) {
        deque sddl;
        for (int i=0;i<s.size();i++)
            if (sddl.empty()) sddl.push_back(s[i]);
            else
            {
                if (s[i]==sddl.back()) sddl.pop_back();
                else sddl.push_back(s[i]);
            }
        string result;
        while (!sddl.empty()) {result+=sddl.front();sddl.pop_front();}
        return result;
    }
};

1190. 反转每对括号间的子串

class Solution {
public:
    string reverseParentheses(string s) {
        deque sddl;
        for (int i=0;i<s.size();i++)
            if (s[i]!=')') sddl.push_back(s[i]);
            else
            {
                string s_temp;
                while (1)
                {
                    if (sddl.back()=='(')
                    {
                        sddl.pop_back();
                        for (int i=0;i<s_temp.size();i++)
                            sddl.push_back(s_temp[i]);
                        break;
                    }
                    s_temp+=sddl.back();sddl.pop_back();
                }
            }
        string result;
        while (!sddl.empty()) {result+=sddl.front();sddl.pop_front();}
        return result;
    }
};

单调队列

239. 滑动窗口的最大值

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        vector result;
        deque sddl;
        for (int i=0;i<k;i++)
        {
            while (!sddl.empty() and nums[i]>sddl.back())
                sddl.pop_back();
            sddl.push_back(nums[i]);
        }
        result.push_back(sddl.front());
        for (int i=k;i<nums.size();i++)
        {
            while (!sddl.empty() and nums[i]>sddl.back())
                sddl.pop_back();
            sddl.push_back(nums[i]);
            if (nums[i-k]==sddl.front())
                sddl.pop_front();
            result.push_back(sddl.front());
        }
        return result;
    }
};

第三部分

3.1.4有些题特别傻逼例如9题；有些题做起来特别难受例如23题（你又不能说它不对，就是考了一个非常偏的知识点)；有些题考了一些根本没用的知识点例如24题（共享栈这东西还是注意一下吧）。其他题目都还好。3.2.5我就不说了，傻逼题太多了。还以一些错题例如11题：知道队首指针，队尾指针你告诉我怎么不能计算队列的长度，老子一个遍历就算出来了，神TM智障。有些傻逼题有一定道理我能接受，有些真的接受不了。