数据结构笔记-栈

发表于 | 分类于 ，

哎呀！图片走丢了！

什么是栈？

栈本质上就是限定仅在一端进行插入或删除操作的线性表。因此栈又称为后进先出（last in first out）的线性表（简称LIFO结构）。进行操作的这一端称为栈顶，另一端称为栈底。

栈的实现

栈的实现方法有顺序实现和链式实现，链式实现与单链表的链式实现相似（毕竟栈只是特殊的单链表）。

栈的顺序实现

这里采用结构体封装，下面直接给出代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#define STACK_INIT_SIZE 100 //储存空间初始量
#define STACKINCREMENT 10 //储存空间增量
typedef struct
{
    SelemType *base;
    SelemType *top;
    int stacksize;
}stack;
bool InitStack(stack &S) //初始化空栈
{
    S.base=(SelemType*)malloc(STACK_INTI_SIZE*sizeof(SelemType));
    if(!S.base) //储存分配失败
        exit(0);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return 1;
}
bool GetTop(stack &S,SelemType &e) //若栈不空，则用e返回栈顶元素
{
    if(S.top==S.base)
        return 0;
    e=*(S.top-1);
    return 1;
}
bool Push(stack &S,SelemType e) //插入元素e作为栈顶元素
{
    if(S.top-S.base>=S.stacksize) //栈满，增加储存空间
    {
        S.base=(SelemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SelemType));
        if(!S.base) //储存分配失败
            exit(0);
        S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT;
    }
    S.top++=e;
    return 1;
}
bool Pop(stack &S,SelemType &e) //若栈不空，则弹出栈顶元素并用e返回其值
{
    if(S.top==S.base)
        return 0;
    e=*--S.top;
    return 1;
}
栈的链式实现

栈的链式实现即为只在表头插入和删除的单链表，这里不再赘述，详情见单链表篇

0%