stack顺序存储结构 - HelloWorld开发者社区

《偶刚开始学习数据结构，欢迎拍砖111》

栈是只能通过访问它的一段来实现数据存储的一种线性数据结构，换句话来说就是先进后出的原则，FILO，与队列刚好相反哈，现在只说stack。

栈包括以下几种基本运算

（1）初始化

（2）判断是否为空

（3）push

（4）pop

（5）top

其他的则根据这几种基本操作进行组合，即可实现。

栈的实现同样有顺序存储与链式存储两种方式，现在说一说顺序存储

首先顺序存储简单可以理解为对数组的操作，所以他的缺点就是容量是有限的。

ok，言归正传。

《一》array_based_stack的实现

首先同样将存储的元素设定为int

下面是stack类型

#define MAX_STACK_SIZE 100     //栈的容量
typedef struct ArrayBasedStack{
    int *base; //存储空间
    int top;   //top指向最上面的一个可用元素,为空时，top = -1；

}AStack;

以及以下几个操作的定义

int initStack(AStack* s);
bool stackEmpty(AStack* s);
int* push(AStack* s, int elem);//成功则返回栈顶指针，否则返回null
int* pop(AStack* s);//返回新的栈顶指针
int top(AStack* s);

下面是实现

#include "stack_array_based.h"
#include <MALLOC.H>
#include <STDIO.H>
int initStack(AStack* s)
{
    s->base = (int *)malloc(MAX_STACK_SIZE * sizeof(int));
    if (s->base==NULL)
    {
        return -1;
    }
    s->top = -1;
    return 0;
}

bool stackEmpty(AStack* s)
{
    if (s->top == -1)
    {
        return true;
    }
    return false;
}
int* push(AStack* s, int elem)
{
    if (s->top==MAX_STACK_SIZE-1) //栈满
    {
        return NULL;
    }
    s->top++;
    s->base[s->top] = elem;
    
    return &(s->base[s->top]);
}
int* pop(AStack* s)//返回新的栈顶指针
{

    if (stackEmpty(s))
    {
        return NULL;
    }
    s->top --;
    if (top<0)
    {
        return NULL;
    }
    return &(s->base[s->top]);
}
int top(AStack* s)
{
    return (s->base[s->top]);
}

最后再来个简单的测试实例

#include "stack_array_based.h"
#include <MALLOC.H>
#include <STDIO.H>

int main()
{
    AStack* s = (AStack*)malloc(sizeof(AStack));
    if (s == NULL)
    {
        return -1;
    }
    
    initStack(s);
    printf("top:%d\n",s->top);
    //向栈中插入是个数据
    for (int i = 0; i<10; i++)
    {
        push(s,i);
    }
    //将数据打印
    while(!stackEmpty(s))
    {
        printf("%d\t",top(s));
        pop(s);
    }
}

实验结果如下 stack顺序存储结构