学习笔记栈（一.栈的顺序存储结构）

红太狼 2022-08-09 16:42 253阅读 0赞

快考试了 来整理。  
栈中的数据元素用一个预设的足够长度的一维数组来实现

datatype data[MAXSIZE];

用一个int 类型的数据来作为栈顶的指针 指明栈顶的位置  
因为是数组吗实际就是用他来表示栈顶的下标

int top;

顺序栈的类型描述如下

typedef struct
    {
        int data[MAXSIZE];
        int top;
    }SeqStack;

这里要说的是因为我的data类型就是int 所有我就直接用了int来定义data\[\],  
定义一个指向顺序栈的指针

SeqStack *s;

0的下标端设为栈底 所以控制空栈的时候让

s->top = -1;

如果有入栈元素那就让栈顶指针加一

s->top++;

下来看一下下顺序栈的基本操作  
1.置空栈：建立一个栈空间 然后初始化栈顶指针

SeqStack *Init_SeqStack()
    {
        SeqStack *s;
        s = (SeqStack *)malloc(sizeof(SeqStack));//申请空间
        s->top = -1;//栈顶指针指向-1
        return s;
    }

2.判空栈：判断他的栈顶指针是不是等于-1

int Empty_SeqStack(SeqStack *s)//判空栈
    {
        if(s->top==-1)
        {
            return 1;//是空栈返回-1
        }
        else
            return 0;//不是空栈返回0
    }

3.判满栈：要看他的栈顶指针是不是已经到了数组的最后一个 因为数组下标是从0开始的 所以最后一个下标就是MAXSIZE-1

int Full_SeqStack(SeqStack *s)//判断栈是否满了
     {
        if(s->top==MAXSIZE-1)
        {
            return 1;//满返回1
        }
        else
            return 0;不满返回0
     }

4.入栈：先判断是不是满栈了 然后把指针指到要入的位置 然后赋上数据

int Push_SeqStack(SeqStack *s, int x)//入栈操作
    {
        if(Full_SeqStack(s))//判断是否满栈 如果满栈则不能入栈 返回0
        {
            return 0;
        }
        else
        {
            s->top++;//指针+1
            s->data[s->top]=x;//赋值
            return 1;
        }
    }

5.出栈 ：先判断栈是否为空 然后用一个数据指针带回 s->top–；只能从栈顶出栈

int Pop_SeqStack( SeqStack *s,int *x)//出栈
    {
        if(Empty_SeqStack(s))//判断是否为空
        {
            return 0;
        }
        else
        {
            *x = s->data[s->top];//带回
            s->top--;栈顶下移一个
            return 1;
        }
    }

6.得到栈顶元素：判空 然后返回栈顶元素就好了

int Top_SeqStack(SeqStack *s)
    {
        if(Empty_SeqStack(s))//判空栈
        {
            return 0;
        }
        else
        {
            return(s->data[s->top]);//返回栈顶元素但并没有丢失
        }
    
    }

要注意出栈和得到栈顶元素的区别 出栈改变了栈顶而得到栈顶元素并没有改变栈顶  
基础大概就是这么多