数据结构栈（c++实现）-白红宇

数据结构栈（c++实现）

阅读量：2430 次

发布时间：2019-05-10

本文共 1874 字，大约阅读时间需要 6 分钟。

栈：限定在表尾进行插入或者删除的线性表。表尾端称之为栈顶，表头端称之为栈底，不含元素的表称之为空栈

栈的修改原则是后进先出的进行的，故栈又称为后进先出的线性表（LIFO结构）

栈的存储方式有两种：顺序栈与链栈

顺序栈的表示和实现

顺序栈就是栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底至栈顶的数据元素。同时设top栈顶表示栈顶元素在顺序栈中的位置top=0表示空栈

以下是顺序栈c++实现

#include
   
    #include
    
     #include
     
      #define stack_init_size 10#define stack_increatment 2#define OVERFLOW - 3#define ok 1#define error -1using namespace std;typedef struct SqStack{    int *base;//栈底指针，在栈构造之前和之后销毁，base值为NULL    int *top;//栈顶指针    int stacksize;} * Stack;int InitStack(SqStack &S){    S.base = (int *)malloc(stack_init_size * sizeof(int));    if(!S.base)        exit(OVERFLOW);    S.top = S.base;    S.stacksize = stack_init_size;    return ok;}void DestroyStack(SqStack &S){    free(S.base);    S.base = NULL;    S.top = NULL;    S.stacksize = 0;}void ClearStack(SqStack &S){    S.top = S.base;}int StackEmpty(SqStack S){    if(S.top==S.base)        return ok;    else        return error;}int StackLength(SqStack S){    return (S.top - S.base);}int GetTop(SqStack S,int &e){    if(S.top==S.base)        return error;    e = *(S.top - 1);    return ok;}int Push(SqStack &S,int e){    if(S.top-S.base>=S.stacksize)    {        S.base = (int *)realloc(S.base, (S.stacksize + stack_increatment) * sizeof(int));        if(!S.base)            exit(OVERFLOW);        S.top = S.base + S.stacksize;        S.stacksize += stack_increatment;    }    *S.top++ = e;    return ok;}int Pop(SqStack &S,int &e){    if(S.top==S.base)        return error;    e = *--S.top;    return ok;}void StackTreaverse(SqStack S){    while(S.top>S.base)    {        cout << *S.base++ << "  ";    }    cout << endl;}int main(){    int j;    SqStack S;    int e;    InitStack(S);    for (j = 1; j <= 10;j++)    {        Push(S, j);    }    cout << "the elem in stack are:";    StackTreaverse(S);    Pop(S,e);    cout << "pop the elem in stack top is:"<

效果如下：