stack顺序存储结构

《偶刚开始学习数据结构,欢迎拍砖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);
    }
}

实验结果如下

《二》栈的链式实现

请参照linklist,自行实现。

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

评论

暂无评论