栈的顺序存储实现 - C语言学习教程_C语言程序_ c语言编程

栈的顺序存储也称为顺序栈，它利用一组地址连续的存储单元，依次存放自栈底到栈顶的元素，同时附设栈顶标识top来指示栈顶元素在顺序栈中的位置。向顺序栈中插入元素时，其过程如图1所示。

图1 向顺序栈中插入元素

由图1可知，向栈中插入元素时，需先使top指针指向栈顶后面的空位，然后进行赋值。删除栈中元素时，只将top向下移动，指示到新的栈顶元素，删除过程如图2所示。

图2 顺序栈弹栈

由图2可知，弹栈是将top移动，指示到新的栈顶元素。原来的栈顶元素依然存在与存储单元中，但无法再通过栈进行访问。

在这个过程中，有一点需要注意：不管栈的示例图如何画（在图3-2中，栈是开口向上，在图3-3与图3-4中，栈是开口向右，当然读者也可以将其开口向下或者开口向左），都是为了更清晰的描述问题，其存储原理是一样的，这一点读者不可混淆。学习其原理后，下面我们来实现一个顺序栈，此顺序栈所具备的功能如下：

● 顺序栈的初始化。

● 判断栈是否为空。

● 获取栈顶元素。

● 弹栈、压栈。

● 销毁栈。

然后在测试文件main.c中完成此顺序栈的测试，具体如例1所示。

例1

seqstack.h //头文件

 1    #ifndef _SEQSTACK_H_
 2    #define _SEQSTACK_H_
 3    
 4    #define MAXSIZE 1024
 5    #define INFINITY 65535
 6    typedef struct
 7    {
 8        int data[MAXSIZE];                 //在结构中定义一个数组
 9        int top;                          //指示栈顶元素,在数组中相当于索引
 10    }SeqStack;
 11    
 12    void InitStack(SeqStack* stack);     //初始化栈
 13    int IsEmpty(SeqStack* stack);         //判断栈是否为空
 14    int SeqStack_Top(SeqStack* stack); //返回栈顶元素
 15    int SeqStack_Pop(SeqStack* stack); //弹出栈顶元素
 16    void SeqStack_Push(SeqStack* stack, int val);     //将元素val压入栈中
 17    void SeqStack_Destory(SeqStack* stack);         //销毁栈
 18    
 19    #endif

seqstack.c //函数实现文件

 20    #include "seqstack.h"
 21    
 22    void InitStack(SeqStack* stack) //初始化栈
 23    {
 24        stack->top = -1; 
 25    }
 26    
 27    int IsEmpty(SeqStack* stack)     //判断栈是否为空
 28    {
 29        if (stack->top == -1)
 30            return 1;
 31        return 0;
 32    }
 33    
 34    int SeqStack_Top(SeqStack* stack) //返回栈顶元素
 35    {
 36        if (!IsEmpty(stack))
 37            return stack->data[stack->top];
 38        return INFINITY; //只是作个简单标识，有可能栈顶元素也为-1；
 39    }
 40    
 41    int SeqStack_Pop(SeqStack* stack) //弹出栈顶元素
 42    {
 43        if (!IsEmpty(stack))
 44            return stack->data[stack->top--]; //弹出一个元素后，top要减1
 45        return INFINITY;
 46    }
 47    
 48    void SeqStack_Push(SeqStack* stack, int val) //将元素val压入栈中
 49    {
 50        if (stack->top >= MAXSIZE - 1) //栈已满
 51            return;
 52        stack->top++; //增加元素后，top要加1
 53        stack->data[stack->top] = val; //将val元素存到数组中
 54    }
 55    
 56    void SeqStack_Destory(SeqStack* stack) //销毁栈
 57    {
 58        if (!IsEmpty(stack))
 59            free(stack);
 60    }

main.c //测试文件

 61    #include <stdio.h>
 62    #include <stdlib.h>
 63    #include "seqstack.h"
 64    
 65    int main()
 66    {
 67        srand((unsigned)time(0));     //以时间为种子产生随机
 68        SeqStack stack;             //创建一个顺序栈
 69        InitStack(&stack);             //初始化栈
 70        
 71        //向栈中添加元素
 72        for (int i = 0; i < 50; i++)
 73        {
 74            SeqStack_Push(&stack, rand() % 1000); //添加的是随机产生的数
 75        }
 76    
 77        //获取栈顶元素
 78        printf("栈顶元素：%d\n", SeqStack_Top(&stack));
 79    
 80        //打印栈中元素
 81        printf("栈中的元素:");
 82        for (int i = 0; i < 50; i++)
 83        {
 84            if (i % 5 == 0)
 85                printf("\n"); //每5个元素一行
 86            printf("%d  ", SeqStack_Pop(&stack));  //依次将栈顶元素弹出    
 87        }
 88    
 89        printf("\n");
 90    
 91        system("pause");
 92        return 0;
 93    }

运行结果如图3所示。

图3 例1运行结果

在例1的实现中，用一个struct来定义栈。在此结构体中定义了一个数组data来存放元素，同时定义了top来指示栈顶元素。

代码22-25行初始化栈。栈中数据索引从0开始，当top值为-1时栈为空。

代码27-32行是判断栈是否为空，其判断条件为top值是否为-1，如果top值为-1，则栈为空；如果top值不为-1，证明栈中有元素，栈不为空。

代码34-39行是读取栈顶元素，就是读取数组data中索引为top的元素，因此该元素为lstack->data[lstack->top]。

代码41-46行是将栈顶元素弹出，栈顶元素为lstack->data[lstack->top]，将其弹出后，top指示下面的元素，所以top要减1。

代码48-54行是元素入栈，首先是让top指示到数组中要插入数据的位置，因为是顺序栈，所以top++；然后将元素存储到数组的栈顶元素lstack->data[lstack->top]中。

代码56-60行是销毁栈，就是将分配的结构空间释放掉。

学习完顺序栈，读者可再与之前学习的顺序表相比较，区分两者在执行读取、插入、删除等操作时的异同，以巩固所学知识。

顺序栈是在顺序表的基础上实现的，读者可以利用已经实现的顺序表来实现一个顺序栈，例如在创建顺序栈时，直接调用已经在顺序表中实现的SeqList_Create()函数。这种实现方式就留给读者自己来实现，读者可以参考博学谷中的相关资源，也可以参考相应的讲解视频。当然，读者也可以有自己的实现方式，我们追求的是更高效简便的算法。