高精度算法

一、什么是高精度算法

C++中的int最大约21亿，long long最大约9.22×10¹⁸。当需要计算远超这个范围的数（比如100位的数字）时，普通数据类型存不下。高精度算法的核心思想是：用数组的每个元素存储大数的一位数字，然后模拟人工手算的过程进行运算。

通常我们用字符串读入大数，逆序存入数组（个位放在下标1，十位放在下标2……这样方便进位）。

---

二、高精度加法

原理：从个位开始逐位相加，满10进1。比如123+456，个位3+6=9，十位2+5=7，百位1+4=5，结果是579。

步骤：

1. 用字符串读入两个大数
2. 逆序存入整型数组
3. 从低位到高位逐位相加并处理进位
4. 逆序输出结果

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN];
char s1[MAXN],s2[MAXN];
int main() {
    scanf("%s %s",s1,s2);
    int l1=strlen(s1),l2=strlen(s2);
    for(int i=1;i<=l1;i++) {
        a[i]=s1[l1-i]-'0';
    }
    for(int i=1;i<=l2;i++) {
        b[i]=s2[l2-i]-'0';
    }
    int len=max(l1,l2);
    for(int i=1;i<=len;i++) {
        c[i]+=a[i]+b[i];
        if(c[i]>=10) {
            c[i]-=10;
            c[i+1]++;
        }
    }
    if(c[len+1]>0) len++;
    for(int i=len;i>=1;i--) {
        printf("%d",c[i]);
    }
    printf("\n");
    return 0;
}

---

三、高精度减法

原理：从个位开始逐位相减，如果被减数某位小于减数对应位，就向高位借1当10。

步骤：

1. 先比较两个数的大小，确保大数减小数（如果结果是负数，记录符号）
2. 逆序存入数组
3. 逐位相减，不够就借位
4. 去除前导零后输出

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN];
char s1[MAXN],s2[MAXN];
int cmp(char x[],char y[]) {
    int lx=strlen(x),ly=strlen(y);
    if(lx!=ly) return lx>ly;
    for(int i=0;i<lx;i++) {
        if(x[i]!=y[i]) return x[i]>y[i];
    }
    return 1;
}
int main() {
    scanf("%s %s",s1,s2);
    int sign=1;
    if(!cmp(s1,s2)) {
        sign=-1;
        swap(s1,s2);
    }
    int l1=strlen(s1),l2=strlen(s2);
    for(int i=1;i<=l1;i++) {
        a[i]=s1[l1-i]-'0';
    }
    for(int i=1;i<=l2;i++) {
        b[i]=s2[l2-i]-'0';
    }
    int len=l1;
    for(int i=1;i<=len;i++) {
        if(a[i]<b[i]) {
            a[i]+=10;
            a[i+1]--;
        }
        c[i]=a[i]-b[i];
    }
    while(len>1&&c[len]==0) len--;
    if(sign==-1) printf("-");
    for(int i=len;i>=1;i--) {
        printf("%d",c[i]);
    }
    printf("\n");
    return 0;
}

---

四、高精度乘法

原理：模拟竖式乘法。a的第i位乘以b的第j位，结果应累加到c的第i+j-1位。比如123×45，3×5=15放在第1位，3×4=12放在第2位，2×5=10放在第2位……最后统一进位。

步骤：

1. 逆序存入数组
2. 双重循环逐位相乘并累加
3. 统一处理进位
4. 去除前导零后输出

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN*2];
char s1[MAXN],s2[MAXN];
int main() {
    scanf("%s %s",s1,s2);
    int l1=strlen(s1),l2=strlen(s2);
    for(int i=1;i<=l1;i++) {
        a[i]=s1[l1-i]-'0';
    }
    for(int i=1;i<=l2;i++) {
        b[i]=s2[l2-i]-'0';
    }
    for(int i=1;i<=l1;i++) {
        for(int j=1;j<=l2;j++) {
            c[i+j-1]+=a[i]*b[j];
        }
    }
    int len=l1+l2;
    for(int i=1;i<=len;i++) {
        if(c[i]>=10) {
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
    }
    while(len>1&&c[len]==0) len--;
    for(int i=len;i>=1;i--) {
        printf("%d",c[i]);
    }
    printf("\n");
    return 0;
}

---

五、高精度除法（高精除以低精）

原理：从最高位开始逐位处理。每次用上一位的余数乘以10加上当前位，然后除以除数，得到当前位的商，余数留给下一位。

步骤：

1. 用字符串存储被除数（不逆序，因为从高位开始处理）
2. 从高位到低位逐位计算
3. 去除前导零后输出商和余数

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],c[MAXN];
char s[MAXN];
int main() {
    int b;
    scanf("%s %d",s,&b);
    int l=strlen(s);
    for(int i=1;i<=l;i++) {
        a[i]=s[i-1]-'0';
    }
    int r=0;
    for(int i=1;i<=l;i++) {
        int cur=r*10+a[i];
        c[i]=cur/b;
        r=cur%b;
    }
    int st=1;
    while(st<l&&c[st]==0) st++;
    for(int i=st;i<=l;i++) {
        printf("%d",c[i]);
    }
    printf("\n");
    printf("%d\n",r);
    return 0;
}

---

六、高精度除法（高精除以高精）

原理：用减法模拟除法。对于每一位，用被除数减去除数，能减多少次，该位商就是多少。为了提升效率，采用倍增思想，每次把除数扩大10倍来试商。

步骤：

1. 判断被除数是否小于除数，若是则商0
2. 从最高位开始，每次将除数左移（即乘以10的幂次）
3. 用被除数不断减去除数，统计次数作为该位商
4. 更新被除数，继续下一位

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN],t[MAXN];
char s1[MAXN],s2[MAXN];
int cmpArr(int x[],int y[],int lx,int ly) {
    if(lx!=ly) return lx>ly;
    for(int i=lx;i>=1;i--) {
        if(x[i]!=y[i]) return x[i]>y[i];
    }
    return 1;
}
void subArr(int x[],int y[],int &len) {
    for(int i=1;i<=len;i++) {
        if(x[i]<y[i]) {
            x[i]+=10;
            x[i+1]--;
        }
        x[i]-=y[i];
    }
    while(len>1&&x[len]==0) len--;
}
int main() {
    scanf("%s %s",s1,s2);
    int l1=strlen(s1),l2=strlen(s2);
    for(int i=1;i<=l1;i++) {
        a[i]=s1[l1-i]-'0';
    }
    for(int i=1;i<=l2;i++) {
        b[i]=s2[l2-i]-'0';
    }
    if(l1<l2||(l1==l2&&!cmpArr(a,b,l1,l2))) {
        printf("0\n");
        for(int i=l1;i>=1;i--) printf("%d",a[i]);
        printf("\n");
        return 0;
    }
    int ansLen=l1-l2+1;
    for(int i=ansLen;i>=1;i--) {
        memset(t,0,sizeof(t));
        for(int j=1;j<=l2;j++) {
            t[i+j-1]=b[j];
        }
        int tLen=l2+i-1;
        while(cmpArr(a,t,l1,tLen)) {
            c[i]++;
            subArr(a,t,l1);
        }
    }
    while(ansLen>1&&c[ansLen]==0) ansLen--;
    for(int i=ansLen;i>=1;i--) printf("%d",c[i]);
    printf("\n");
    while(l1>1&&a[l1]==0) l1--;
    for(int i=l1;i>=1;i--) printf("%d",a[i]);
    printf("\n");
    return 0;
}

---

七、总结

运算	时间复杂度	关键点
加法	O(n)	逐位相加，处理进位
减法	O(n)	先比较大小，逐位借位
乘法	O(n²)	逐位相乘后统一进位
除法（低精）	O(n)	从高位逐位求商
除法（高精）	O(n²)	减法模拟，倍增试商

高精度算法是算法竞赛中的基础技能，掌握后可以处理任意大的整数运算。实际应用中，通常用加法、减法和乘法较多，除法相对较少，但原理都需要理解透彻。

---

指针单双链表

一、什么是指针链表

链表是一种线性数据结构，由一系列节点组成。每个节点包含数据域和指针域，指针域指向下一个节点（或上一个节点）。链表的优点是插入删除操作快，不需要移动元素，缺点是查找需要遍历，不能随机访问。

指针链表的特点：

• 节点动态分配内存
• 通过指针连接节点
• 插入删除时间复杂度O(1)
• 查找时间复杂度O(n)

---

二、单链表

单链表：每个节点只包含指向下一个节点的指针，只能从前往后遍历。

节点结构

struct Node {
    int data;
    Node* next;
};

基本操作

1. 创建链表

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head,* tail;
int n;
int main() {
    scanf("%d",&n);
    head=NULL;
    tail=NULL;
    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=NULL;
        if(head==NULL) {
            head=p;
            tail=p;
        } else {
            tail->next=p;
            tail=p;
        }
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

2. 在头部插入

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

3. 在指定位置插入

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,pos,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    scanf("%d %d",&pos,&x);
    if(pos==1) {
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    } else {
        Node* cur=head;
        for(int i=1;i<pos-1;i++) {
            if(cur==NULL) return 0;
            cur=cur->next;
        }
        if(cur==NULL) return 0;
        Node* p=new Node();
        p->data=x;
        p->next=cur->next;
        cur->next=p;
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

4. 删除指定元素

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x,del;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    scanf("%d",&del);
    while(head!=NULL&&head->data==del) {
        Node* tmp=head;
        head=head->next;
        delete tmp;
    }
    if(head==NULL) return 0;
    Node* cur=head;
    while(cur->next!=NULL) {
        if(cur->next->data==del) {
            Node* tmp=cur->next;
            cur->next=tmp->next;
            delete tmp;
        } else {
            cur=cur->next;
        }
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

5. 查找元素

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x,target,pos=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    scanf("%d",&target);
    Node* cur=head;
    while(cur!=NULL) {
        pos++;
        if(cur->data==target) {
            printf("%d\n",pos);
            return 0;
        }
        cur=cur->next;
    }
    printf("-1\n");
    return 0;
}

6. 反转链表

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    Node* pre=NULL;
    Node* cur=head;
    Node* nxt=NULL;
    while(cur!=NULL) {
        nxt=cur->next;
        cur->next=pre;
        pre=cur;
        cur=nxt;
    }
    head=pre;
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

---

三、双链表

双链表：每个节点包含指向前一个节点和后一个节点的指针，可以从前往后遍历，也可以从后往前遍历。

节点结构

struct Node {
    int data;
    Node* prev;
    Node* next;
};

基本操作

1. 创建双链表

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head,* tail;
int main() {
    head=NULL;
    tail=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=NULL;
        if(head==NULL) {
            head=p;
            tail=p;
        } else {
            tail->next=p;
            p->prev=tail;
            tail=p;
        }
    }
    printf("从头到尾：");
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    printf("从尾到头：");
    for(Node* p=tail;p!=NULL;p=p->prev) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

2. 在头部插入

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=head;
        if(head!=NULL) {
            head->prev=p;
        }
        head=p;
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

3. 在指定位置插入

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,pos,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=head;
        if(head!=NULL) {
            head->prev=p;
        }
        head=p;
    }
    scanf("%d %d",&pos,&x);
    if(pos==1) {
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=head;
        if(head!=NULL) {
            head->prev=p;
        }
        head=p;
    } else {
        Node* cur=head;
        for(int i=1;i<pos-1;i++) {
            if(cur==NULL) return 0;
            cur=cur->next;
        }
        if(cur==NULL) return 0;
        Node* p=new Node();
        p->data=x;
        p->prev=cur;
        p->next=cur->next;
        if(cur->next!=NULL) {
            cur->next->prev=p;
        }
        cur->next=p;
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

4. 删除指定元素

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x,del;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=head;
        if(head!=NULL) {
            head->prev=p;
        }
        head=p;
    }
    scanf("%d",&del);
    while(head!=NULL&&head->data==del) {
        Node* tmp=head;
        head=head->next;
        if(head!=NULL) {
            head->prev=NULL;
        }
        delete tmp;
    }
    if(head==NULL) return 0;
    Node* cur=head;
    while(cur!=NULL) {
        if(cur->data==del) {
            Node* tmp=cur;
            if(cur->prev!=NULL) {
                cur->prev->next=cur->next;
            }
            if(cur->next!=NULL) {
                cur->next->prev=cur->prev;
            }
            cur=cur->next;
            delete tmp;
        } else {
            cur=cur->next;
        }
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

5. 双向遍历

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head,* tail;
int main() {
    head=NULL;
    tail=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=NULL;
        if(head==NULL) {
            head=p;
            tail=p;
        } else {
            tail->next=p;
            p->prev=tail;
            tail=p;
        }
    }
    printf("正向遍历：");
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    printf("反向遍历：");
    for(Node* p=tail;p!=NULL;p=p->prev) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

---

四、单链表 vs 双链表对比

特性	单链表	双链表
存储空间	每个节点1个指针	每个节点2个指针
遍历方向	只能向前	可以向前向后
插入操作	O(1)（已知前驱）	O(1)（已知前驱或后继）
删除操作	需要知道前驱节点	直接删除（已知自身）
反向遍历	不支持	支持
应用场景	简单的线性结构	需要双向访问的场景

注意事项：

1. 指针链表每次插入都要new新节点，删除时要delete释放内存
2. 操作时要防止空指针访问（检查NULL）
3. 双链表比单链表多维护一个prev指针，操作时要注意同时维护前后关系
4. 链表适合频繁插入删除的场景，不适合频繁查找的场景

---

栈

一、什么是栈

栈是一种先进后出（Last In First Out，LIFO）的线性数据结构。就像一摞盘子，后放上去的盘子先被拿走，先放上去的盘子后被拿走。

核心操作：

• 入栈（push）：在栈顶添加元素
• 出栈（pop）：移除栈顶元素
• 取栈顶（top）：查看栈顶元素但不移除
• 判空（empty）：判断栈是否为空
• 获取大小（size）：获取栈中元素个数

---

二、栈的两种实现方式

1. 数组实现栈（静态栈）

原理：用数组存储元素，用一个变量top指向栈顶位置。top初始为0表示空栈，入栈时先top++再赋值，出栈时top--。

优点：简单高效，访问速度快
缺点：大小固定，不能动态扩展

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],top;
int main() {
    top=0;
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            if(top<MAXN-5) {
                stk[++top]=x;
                printf("入栈成功：%d\n",x);
            } else {
                printf("栈已满\n");
            }
        } else if(op==2) {
            if(top>0) {
                printf("出栈元素：%d\n",stk[top--]);
            } else {
                printf("栈为空\n");
            }
        } else if(op==3) {
            if(top>0) {
                printf("栈顶元素：%d\n",stk[top]);
            } else {
                printf("栈为空\n");
            }
        } else if(op==4) {
            printf("栈中元素个数：%d\n",top);
        } else if(op==5) {
            printf("栈是否为空：%s\n",top==0?"是":"否");
        }
    }
    return 0;
}

2. STL栈（标准模板库）

C++的STL提供了现成的栈容器，方便使用。

#include <bits/stdc++.h>
using namespace std;
stack<int> st;
int main() {
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            st.push(x);
            printf("入栈成功：%d\n",x);
        } else if(op==2) {
            if(!st.empty()) {
                printf("出栈元素：%d\n",st.top());
                st.pop();
            } else {
                printf("栈为空\n");
            }
        } else if(op==3) {
            if(!st.empty()) {
                printf("栈顶元素：%d\n",st.top());
            } else {
                printf("栈为空\n");
            }
        } else if(op==4) {
            printf("栈中元素个数：%d\n",st.size());
        } else if(op==5) {
            printf("栈是否为空：%s\n",st.empty()?"是":"否");
        }
    }
    return 0;
}

---

三、栈的经典应用

1. 括号匹配

原理：遍历字符串，遇到左括号入栈，遇到右括号则检查栈顶是否是对应的左括号。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
char stk[MAXN],s[MAXN];
int top;
int main() {
    scanf("%s",s+1);
    int len=strlen(s+1);
    top=0;
    int flag=1;
    for(int i=1;i<=len;i++) {
        if(s[i]=='('||s[i]=='['||s[i]=='{') {
            stk[++top]=s[i];
        } else if(s[i]==')') {
            if(top>0&&stk[top]=='(') {
                top--;
            } else {
                flag=0;
                break;
            }
        } else if(s[i]==']') {
            if(top>0&&stk[top]=='[') {
                top--;
            } else {
                flag=0;
                break;
            }
        } else if(s[i]=='}') {
            if(top>0&&stk[top]=='{') {
                top--;
            } else {
                flag=0;
                break;
            }
        }
    }
    if(flag&&top==0) {
        printf("括号匹配正确\n");
    } else {
        printf("括号匹配错误\n");
    }
    return 0;
}

2. 表达式求值（中缀转后缀）

原理：利用栈的优先级比较，将中缀表达式转换为后缀表达式再求值。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
char stk[MAXN],s[MAXN];
int top;
int getPri(char c) {
    if(c=='*'||c=='/') return 2;
    if(c=='+'||c=='-') return 1;
    return 0;
}
int main() {
    scanf("%s",s+1);
    int len=strlen(s+1);
    top=0;
    for(int i=1;i<=len;i++) {
        if(s[i]>='0'&&s[i]<='9') {
            printf("%c",s[i]);
        } else if(s[i]=='(') {
            stk[++top]=s[i];
        } else if(s[i]==')') {
            while(top>0&&stk[top]!='(') {
                printf("%c",stk[top--]);
            }
            if(top>0) top--;
        } else {
            while(top>0&&getPri(stk[top])>=getPri(s[i])) {
                printf("%c",stk[top--]);
            }
            stk[++top]=s[i];
        }
    }
    while(top>0) {
        printf("%c",stk[top--]);
    }
    printf("\n");
    return 0;
}

3. 单调栈（求下一个更大元素）

原理：维护一个单调递减的栈，当前元素比栈顶大时，栈顶的下一个更大元素就是当前元素。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],ans[MAXN],stk[MAXN];
int top;
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    top=0;
    for(int i=n;i>=1;i--) {
        while(top>0&&a[stk[top]]<=a[i]) {
            top--;
        }
        if(top>0) {
            ans[i]=a[stk[top]];
        } else {
            ans[i]=-1;
        }
        stk[++top]=i;
    }
    for(int i=1;i<=n;i++) {
        printf("%d ",ans[i]);
    }
    printf("\n");
    return 0;
}

4. 模拟递归（DFS）

栈可以用来模拟递归调用，避免递归深度过大的问题。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
struct Node {
    int x,y,step;
};
Node stk[MAXN];
int top;
int main() {
    int n,start;
    scanf("%d %d",&n,&start);
    top=0;
    stk[++top]={start,0,1};
    while(top>0) {
        Node cur=stk[top--];
        printf("%d ",cur.x);
        if(cur.x*2<=n) {
            stk[++top]={cur.x*2,cur.y+1,cur.step+1};
        }
        if(cur.x+1<=n) {
            stk[++top]={cur.x+1,cur.y+1,cur.step+1};
        }
    }
    printf("\n");
    return 0;
}

---

四、栈的常见题型

1. 最小栈

设计一个栈，支持push、pop、top和getMin操作，getMin能在O(1)时间返回最小值。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],minStk[MAXN];
int top,minTop;
int main() {
    top=0;
    minTop=0;
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            stk[++top]=x;
            if(minTop==0||x<=minStk[minTop]) {
                minStk[++minTop]=x;
            }
        } else if(op==2) {
            if(top>0) {
                if(stk[top]==minStk[minTop]) {
                    minTop--;
                }
                printf("出栈：%d\n",stk[top--]);
            }
        } else if(op==3) {
            if(top>0) {
                printf("栈顶：%d\n",stk[top]);
            }
        } else if(op==4) {
            if(minTop>0) {
                printf("最小值：%d\n",minStk[minTop]);
            }
        }
    }
    return 0;
}

2. 栈排序

使用辅助栈对栈进行排序。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],tmpStk[MAXN];
int top,tmpTop;
int main() {
    top=0;
    tmpTop=0;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        while(top>0&&stk[top]>x) {
            tmpStk[++tmpTop]=stk[top--];
        }
        stk[++top]=x;
        while(tmpTop>0) {
            stk[++top]=tmpStk[tmpTop--];
        }
    }
    while(top>0) {
        printf("%d ",stk[top--]);
    }
    printf("\n");
    return 0;
}

---

五、栈的总结

特性	数组实现	STL实现
时间复杂度	O(1)	O(1)
空间限制	固定大小	动态扩展
操作直观	需要手动管理	封装完善
适用场景	已知最大大小	大小不确定

栈的核心思想：

1. 先进后出是根本特性
2. 递归本质上就是栈的应用
3. 适用于需要回溯的场景
4. 常用于深度优先搜索（DFS）
5. 表达式求值、括号匹配等是经典应用

注意事项：

1. 使用数组实现时注意栈溢出（top超过MAXN）
2. 出栈前检查栈是否为空
3. 递归深度过大时考虑用栈模拟
4. 栈擅长处理具有嵌套结构的数据