第三章节 栈和队列

参考：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. 滑动窗口的最大值
                                • 第三部分

                                  第一部分

                                  栈

                                  基本概念

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

                                  （）

                                  栈的实现

                                  顺序栈的实现

                                  顺序栈（顾名思义）

                                  #includeusing 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    if (my_stack.now_size==my_stack.max_size) cout    if (IsEmpty(my_stack)) cout    Stack my_stack;Init(my_stack,10);    for (int i=0;i    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    Node * next;InitNode(next);next-data=data;    next-next=my_stack;my_stack=next;}void Pop(Node * & my_stack){    if (IsEmpty(my_stack)) cout    Node * my_stack;InitStack(my_stack);    for (int i=0;i    stackmy_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(){    coutpublic:    bool isValid(string s) {        stack                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;    }};    int x=s[0]-'0',len=1;    while (s[len]='0' and s[len]        x*=10;x+=s[len]-'0';len+=1;    }    return make_pair(x,len);}double calculate(char * s){    int i=0;stack        if (s[i]='0' and s[i]            pair                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    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    if (IsEmpty(my_queue)) {cout    if (IsEmpty(my_queue)) {cout    if (IsEmpty(my_queue)) {cout    Queue my_queue;Init(my_queue,10);    for (int i=0;i    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    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    if (my_queue1.size()my_queue2.size())     {        queue        cout    string lb1[1]={"LCL"};    string lb2[3]={"GNZ","YHC","WMQ",};    queue    if (n==0) return 1;    return n*factorial(n-1);}    cout    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;}    if (my_vector.empty()) return;    cout    if (my_queue.empty()) return;    cout    if (my_stack.empty()) return;    cout    vector        my_vector.push_back(i);my_queue.push(i);my_stack.push(i);    }    func1(my_vector);coutpublic:    bool isValid(string s) {        stack                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;    }};public:    int longestValidParentheses(string s) {        int result=0;        stack                my_stack.pop();                if (my_stack.empty()) my_stack.push(i);                else result=max(result,i-my_stack.top());            }        return result;    }};public:    string removeDuplicates(string s) {        stack                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;    }};public:    string reverseParentheses(string s) {        stack                string s_temp;                while (1)                {                    if (z.top()=='(')                    {                        z.pop();                        for (int i=0;iresult+=z.top();z.pop();}        reverse(result.begin(),result.end());        return result;    }};public:    int trap(vector        int result=0;        stack            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;    }};public:    int largestRectangleArea(vector        vector            while (!my_stack1.empty() and heights[i]                my_vector1[my_stack1.top()]=i;my_stack1.pop();            }            my_stack1.push(i);        }        vector            while (!my_stack2.empty() and heights[i]                my_vector2[my_stack2.top()]=i;my_stack2.pop();            }            my_stack2.push(i);        }        int result=0;        for (int i=0;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_tempresult) result=result_temp;        }        return result;    }};public:    int maximalRectangle(vector        vector            int result_temp=fc(my_matrix[i]);            if (result_tempresult) result=result_temp;        }        return result;    }    int fc(const vector        vector            while (!my_stack1.empty() and heights[i]                my_vector1[my_stack1.top()]=i;my_stack1.pop();            }            my_stack1.push(i);        }        vector            while (!my_stack2.empty() and heights[i]                my_vector2[my_stack2.top()]=i;my_stack2.pop();            }            my_stack2.push(i);        }        int result=0;        for (int i=0;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_tempresult) result=result_temp;        }        return result;    }};public:    bool find132pattern(vector        stack            if (nums[i]                 k=max(k,my_stack.top());my_stack.pop();            }            my_stack.push(nums[i]);        }        return false;}};public:    vector        unordered_map            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();        }        vectorpublic:    vector        vector            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;i                    result[my_stack.top()]=nums[i];break;                }            my_stack.pop();        }        return result;    }};public:    vector        vector            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;    }};public:    vector        stack            while (!my_stack.empty() and prices[i]                prices[my_stack.top()]-=prices[i];my_stack.pop();            }            my_stack.push(i);        }        return prices;    }};public:    vector        vector            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;    }};public:    string predictPartyVictory(string senate) {        queue            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;    }};public:    string removeDuplicates(string s) {        deque                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;    }};public:    string reverseParentheses(string s) {        deque                string s_temp;                while (1)                {                    if (sddl.back()=='(')                    {                        sddl.pop_back();                        for (int i=0;iresult+=sddl.front();sddl.pop_front();}        return result;    }};public:    vector        vector            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            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;    }};