[数据结构与算法] 入栈出栈操作总结

时间:2020-12-21 10:20:47

最近要参加数据结构与算法期末考试了,在这里总结一下出栈入栈的一些常规操作。

#include  <stdlib.h>   
#include "stdio.h"   
#include<string.h>  
typedef char SElemType;       //栈数据元素的类型  
#define STACK_INIT_SIZE 10  //栈存储空间的初始分配量  
#define STACKINCREMENT 10    //栈存储空间的分配增量  
typedef struct  
{  
    SElemType *base;         //构造之前和销毁之后,base的值为NULL  
    SElemType *top;             //栈顶指针  
    int stacksize;           //当前分配的存储容量(以sizeof(SElemType)为单位)  
}Stack;  
 
char InitStack(Stack &S)  
{  
    S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); //通过malloc函数分配空间  
    if (!S.base)  
        return 0;               //如果分配失败,则返回0  
    S.top=S.base;                //栈顶指针设为栈底地址  
    S.stacksize=STACK_INIT_SIZE; //当前分配的空间  
    return 1;  
}  
 
char StackEmpty(Stack S)  
{  
    if (S.base)  
    {  
        if (S.base==S.top)       //如果栈为空栈,则返回1(true),否则返回0(false)  
        {  
            return 1;  
        }  
    }  
    return 0;  
}  
 
char Push(Stack &S,SElemType e)  
{  
    if (S.base)  
    {  
        if ((S.top-S.base)>=S.stacksize)    //栈满,追加存储空间  
        {  
            S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)* sizeof(SElemType));  
            if(S.base==NULL)  
                return 0;                  //如果重新分配空间失败,则返回0(false),表示插入不成功  
            S.top=S.base+S.stacksize;               //设置数组的新地址  
            S.stacksize+=STACKINCREMENT;    //分配空间要加上新增的空间  
        }  
        *S.top++=e; 
        return 1;  
    }  
    return 0;  
}  
//*S.top++=e     
//栈顶位置后++,本次运算S.top栈空间不变,所以是把S栈顶指针指向E,运算完成后栈空间才自增1  
//*++S.top=e  
//栈顶位置前++,本次运算S.top栈顶向前增加1,所以是把S栈新增的栈顶指向E。  
char Pop(Stack &S,SElemType &e)  
{  
    if (S.base)  
    {  
        if (S.top>S.base)    //若栈不是空的  
        {  
            e=*--S.top;  
            return 1;  
        }  
    }  
    return 0;  
}  
 
char StackTraverse(Stack &S)//依次输出从栈底到栈顶的每个元素  
{  
    int i;  
    if (S.base)  
    {  
        printf("\n依次输出从栈底到栈顶的每个元素为:\n");  
        for(i=0;i<S.top-S.base;i++)  
        {  
            printf("%c  ",S.base[i]);   //依次打印数据元素  
        }  
        printf("\n");  
        return 1;  
    }  
    return 0;  
}  
 
void main()  
{  
    Stack S;  
    char x,y;  
    InitStack(S);  
    x='c';y='k';  
    Push(S,x);StackTraverse(S);
    Push(S,'a');StackTraverse(S);
    Push(S,y);StackTraverse(S);  
    Pop(S,x);StackTraverse(S);
    Push(S,'t');StackTraverse(S);
    Push(S,x);StackTraverse(S);  
    Pop(S,x);StackTraverse(S);
    Push(S,'s');StackTraverse(S);  
    while(!StackEmpty(S)){
        Pop(S,y);StackTraverse(S);
        printf("%c",y);
    }  
    printf("%c\n",x);  
    
}  

 

参考了别人写的代码,自己又把代码敲了一遍。但是还是不熟悉。

一回生,二回熟嘛!多多练习就能掌握了。