数据结构——栈

说明：严蔚敏的《数据结构》（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进制数：\n");
    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("\n");
}

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;
}

数据结构——栈

原文：http://blog.csdn.net/dawanganban/article/details/41651881