数据结构：顺序栈的基本操作

素颜马尾好姑娘i 2022-05-27 10:06 196阅读 0赞

采用顺序存储结构的栈称为顺序栈。顺序栈利用一组连续的存储单元存放栈中的元素，存放顺序依次从栈底到栈顶。由于栈中元素之间的存放地址的连续性，在C语言中，同样采用数组实现栈的顺序存储。另外，增加一个栈顶指针top，用于指向顺序栈的栈顶元素。

--------------------

通常top=0或者top=-1表示栈为空。两者的区别简单概括如下：

*  top=0表示栈为空时，top指向栈底，所以每次在压栈时，先将数据元素压入栈，再对指针进行++操作，使指针后移；top=-1表示栈为空，压栈时恰恰相反，先对栈顶指针进行++操作，然后再将数据压入栈中，
 *  在求栈的长度，(即:栈中元素个数时)只需要返回或打印栈顶指针的值； 而由于top=-1表示栈底时，每次对栈中元素操作时先对栈顶指针进行操作，所以在求栈的长度，即栈中元素个数时，需要返回top+1的值;
 *  栈空条件为top == 0 或 top == -1，时栈满条件均为 top = MAXSIZE -1;

--------------------

#### 顺序栈的基本操作 ####

/*源代码*/
    
    #include <stdio.h>
    #include <Windows.h>
    
    #define MAXSIZE 100
    typedef int DataType;
    
    typedef struct
    {
        DataType stack[MAXSIZE];
        int top;  
    }SeqStack;
    
    /*初始化栈,把栈初始化为空，把栈顶指针置为-1*/
    void InitStack(SeqStack * s)
    {
        s->top = -1;
    }
    
    /*判空操作，当栈顶指针为top 为-1，栈为空*/
    int StackEmpty(SeqStack s)
    {
        if (s.top == -1)
        {
            return 1;
        }
        return 0;
    }
    
    /*入栈操作，栈顶指针top++，然后将data值压入栈中*/
    int StackPush(SeqStack* s, DataType data)
    {
        if (s->top == MAXSIZE)
        {
            printf("栈已满，不能入栈！\n");
            return 0;
        }
        else
        {
            s->top++;
            s->stack[s->top] = data;
            return 1;
        }
    }
    
    /*取栈顶元素，将栈顶元素输出*/
    int StackGetTop(SeqStack s)
    {
        if (s.top==-1)
        {
            printf("栈为空！\n");
            return 0;
        }
        else
        {
            printf("%d\n", s.stack[s.top]);
            s.top--;
        }
    }
    /*输入要入栈的元素以 -1 作为结束标志*/
    
    void StackInput(SeqStack* s)
    {
        int data;
        scanf_s("%d", &data);
        while (data != -1)
        {
            StackPush(s, data);
            scanf_s("%d", &data);
        }
    }
    
    /*打印栈中元素*/
    void Display(SeqStack s)
    {
        int i;
    
        for (i = s.top; i >= 0; i--)
        {
            printf("%-3d", s.stack[i]);
        }
        printf("\n");
    }
    /*出栈操作，将栈顶指针top-- */
    void StackPop(SeqStack* s)
    {
        if (s->top==-1)
        {
            printf("栈为空！\n");
        }
        else
        {
            s->top--;
        }
    }
    
    /*返回栈的长度,栈的长度就是栈中元素的个数*/
    int StackLength(SeqStack s)
    {
         s.top + 1;
         printf("%d\n", s.top + 1);
         return 0;
    }
    
    /*清空栈，清空栈与初始化栈的操作一样，只需将栈顶指针置-1即可*/
    void StackClear(SeqStack* s)
    {
        s->top = -1;
    }
    int main()
    {
        SeqStack s;
        InitStack(&s);
    
        printf("输入入栈元素：\n");
        StackInput(&s);
        printf("栈中元素为：\n");
        Display(s);
        printf("栈顶元素为：\n");
        StackGetTop(s);
        printf("栈中元素个数为:\n");
        StackLength(s);
        printf("退一次栈!\n");
        StackPop(&s);
        printf("栈中元素为：\n");
        Display(s);
        StackClear(&s);
    
        system("pause");
        return 0;
    }