数据结构——栈

说明：严蔚敏的《数据结构》（C语言版）学习笔记，记录一下，以备后面查看。

如上图所示，刚开始base指针和top指针都指向栈低，当压栈的时候，top指针向上移动，直到栈满后，栈顶指针top指向栈外地址，此时我们需要再分配新空间。

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

const int OK = 1; //定义正确返回
const int ERROR = -1; //定义错误的返回
const int OVERFLOW = -2; //定义溢出

//定义元素类型
typedef int SElemType;
//定义返回类型
typedef int Status;

typedef struct{
    SElemType *base; //栈底指针，在构造之前和销毁后base的值为NULL
    SElemType *top; //栈顶指针
    int stacksize; //已分配的空间
}SqStack;

//初始化栈
Status InitStack(SqStack &S){
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base) exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

//获取栈顶元素
Status GetTop(SqStack S, SElemType &e){
    if(S.top == S.base) return ERROR;
    e = *(S.top - 1);
    return OK;
}

//压栈
Status Push(SqStack &S, SElemType e){
    if(S.top - S.base >= S.stacksize){
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!S.base) exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top = e;
    S.top++;
    return OK;
}

//出栈
Status Pop(SqStack &S, SElemType &e){
    if(S.top == S.base) return ERROR;
    e = *(--S.top);
    return OK;
}

//判断栈是否为空
bool StackEmpty(const SqStack &S){
    if(S.top == S.base) return true;
    else return false;
}

//十进制数转8进制数
void conversion(SqStack &S){
    InitStack(S);
    printf("请输入10进制数，返回一个8进制数：
");
    int n;
    scanf("%d", &n);
    while(n){
        Push(S, n % 8);
        n = n / 8;
    }
    SElemType e;
    printf("8进制数是：0x");
    while(!StackEmpty(S)){
        Pop(S, e);
        printf("%d", e);
    }
    printf("
");
}

int main(){
    SqStack sq;
    //InitStack(sq);
    //Push(sq, 1);
    //Push(sq, 2);
    //Push(sq, 3);
    //SElemType e3;
    //Pop(sq, e3);
    //GetTop(sq, e3);
    //printf("%d", e3);
    conversion(sq);
    
    scanf("%d");
    return 0;
}

上面的conversion函数是一个将10进制转换为8进制的例子，这个就是栈的一个应用，还有例如，括号匹配的验证、迷宫求解等。

例如Hanoi塔问题：

假设有3个分别为a,b,c的三个塔座，a上有直径从大到小的圆盘，可以借助b塔座将a上的圆盘移动到c上，移动过程中大小顺序不变。

void movePic(char a, int n, char b){
    printf("将编号为%d的圆盘从%c上移动到%c上
", n , a, b);
}

void hanuota(int n, char x, char y, char z){
    if(n == 1){
        movePic(x, 1, z);  //将编号为1的圆盘从x移到z
    }else{
        hanuota(n - 1, x, z, y); //将x上编号为1到n-1的圆盘移到y,z作辅助塔
        movePic(x, n, z);  //将编号为n的圆盘从x移到z
        hanuota(n - 1, y, x, z); //将y上编号为1到n-1的圆盘移到z,x作辅助塔
    }
}

int main(){
    hanuota(3, 'a', 'b', 'c');
}

我们可以将问题简单抽象成递归。

1、要将n个圆盘移动到c，则需要先将n-1个圆盘移动到b

2、再将a上的最底下的圆盘移动到c

3、最后将b上面的n-1个圆盘移动到c

经过这三个步骤就可以完成移动，在这三个步骤中，步骤1，从a将n-1个圆盘移动到b和问题本身是同一个问题，步骤3将n-1个圆盘从b移动到c也和问题本身是同一个问题，所以这两处我们就可以迭代调用。