数据结构 三 栈

数据结构 栈
数据结构 栈
发布日期:   2021-06-30

栈

栈，依靠线性表来实现。

ADT

  1. 构造一个空栈
  2. 销毁一个栈
  3. 清空栈
  4. 判断栈是否为空
  5. 栈中元素个数
  6. 获得栈顶元素
  7. push
  8. pop
  9. 遍历栈

栈的顺序表实现

接口说明

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
#include "../Linear-List/linearlist.c"

//stack 可以直接使用 list 作为基础构建不同的stack  其实list就是所有线性数据结构的基础。
//我觉得之前的list的实现很不优雅，所以决定再重新实现一遍
//要学会抓住事情的主要矛盾，学习栈就是要学习其后进先出的思想，现在不要管其他杂乱的东西。

typedef struct LinearStack
{
    //存储数据的区域   这里的block就相当于linearlist 中的List
    struct LinearList *block;
    Item *base;
    Item *top;
    //当前长度
    int length;
    //当前分配的存储容量
    int stacksize;
} * LinearStack;

bool InitStack(LinearStack *stack, int initsize);

bool DestroyStack(LinearStack *stack);

bool ClearStack(LinearStack *stack);

bool EmptyStack(LinearStack *stack);

bool GetTopStack(LinearStack *stack, Item *itemsave);

bool PushStack(LinearStack *stack, Item *item);

bool PopStack(LinearStack *stack);

void AutoFillStack(LinearStack *stack);

void TraverseStack(LinearStack *stack, void (*fun)(Item item));

接口实现

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include "linearstack.h"

bool InitStack(LinearStack *stack, int initsize)
{
    (*stack) = (struct LinearStack *)malloc(sizeof(struct LinearStack));
    InitLinearList(&((*stack)->block), initsize);
    (*stack)->base = (Item *)malloc(sizeof(Item));
    (*stack)->top = (Item *)malloc(sizeof(Item));
    //由于这了的base和top只是item*类型的，所以指向特定的item有点累赘，不如直接存储特定的元素值，除非改变其类型为指向一个结点的指针，这样只更更改其指向会更加由必要。
    (*stack)->length = 0;
    (*stack)->stacksize = initsize;
    printf("初始化成功\n");
    return true;
}

bool DestroyStack(LinearStack *stack)
{
    DestroyLinearList(&((*stack)->block));
    free((*stack)->base);
    free((*stack)->top);
    (*stack)->base = NULL;
    (*stack)->top = NULL;
    (*stack)->block = NULL;
    free(stack);
    *stack = NULL;
    if (*stack == NULL)
    {
        printf("销毁成功\n");
    }
    else
    {
        printf("销毁失败\n");
    }
}

bool ClearStack(LinearStack *stack)
{
    free((*stack)->base);
    free((*stack)->top);
    (*stack)->base = (Item *)malloc(sizeof(Item));
    (*stack)->top = (Item *)malloc(sizeof(Item));
    (*stack)->length = 0;
    ClearLinearList(&((*stack)->block));
    printf("清空栈成功\n");
    return true;
}

bool EmptyStack(LinearStack *stack)
{
    if ((*stack)->length == 0)
    {
        printf("栈空\n");
        return true;
    }
    else
    {
        printf("栈不空\n");
        return false;
    }
}

bool GetTopStack(LinearStack *stack, Item *itemsave)
{
    if ((*stack)->length == 0)
    {
        printf("错误，栈中没有元素\n");
        return false;
    }
    else
    {
        *itemsave = *((*stack)->top);
        return true;
    }
}

bool PushStack(LinearStack *stack, Item *item)
{
    printf("当前容量为：%d, 可用容量为：%d\n", (*stack)->stacksize, (*stack)->stacksize - (*stack)->length);
    InsertLinearList(&((*stack)->block), (*stack)->length, item);
    (*stack)->length++;
    (*stack)->stacksize = (*stack)->block->listsize;
    if ((*stack)->length == 1)
    {
        //base只是指针不需要分配内存，也没有内存，所以只能通过改变指向的方式改变base,top也一样。
        *((*stack)->base) = ((*stack)->block->items[0]);
    }
    *((*stack)->top) = ((*stack)->block->items[(*stack)->length - 1]);
    return true;
}

bool PopStack(LinearStack *stack)
{
    if ((*stack)->length == 0)
    {
        printf("已经空了，不能pop\n");
        return false;
    }
    //删除最后一个元素。
    DeleteLinearList(&((*stack)->block), (*stack)->length - 1);
    (*stack)->length--;
    //更改 top
    *((*stack)->top) = (*stack)->block->items[(*stack)->length - 1];

    return true;
}

void AutoFillStack(LinearStack *stack)
{
    for (int i = 1; i <= 10; i++)
    {
        Item item;
        item.value = i;
        PushStack(stack, &item);
    }
}

void TraverseStack(LinearStack *stack, void (*fun)(Item item))
{
    Item item;
    while (!EmptyStack(stack))
    {
        GetTopStack(stack, &item);
        PopStack(stack);
        fun(item);
    }
}

接口使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "linearstack.c"

void fun2(Item item)
{
    printf("item: %d\n", item.value);
}
int main()
{
    LinearStack stack;
    InitStack(&stack, 5);
    AutoFillStack(&stack);
    TraverseStack(&stack, (*fun2));
    ClearStack(&stack);
    DestroyStack(&stack);
}

栈的链表实现

接口说明

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
#include "../Link-List/linklist.c"

typedef struct LinkStack
{
    //存储数据的区域   这里的block就相当于LinkList 中的List
    LinkList block;
    Item *base;
    Item *top;
    //当前长度
    int length;
} * LinkStack;

bool InitStack(LinkStack *stack);

bool DestroyStack(LinkStack *stack);

bool ClearStack(LinkStack *stack);

bool EmptyStack(LinkStack *stack);

bool GetTopStack(LinkStack *stack, Item *itemsave);

bool PushStack(LinkStack *stack, Item *item);

bool PopStack(LinkStack *stack);

void AutoFillStack(LinkStack *stack);

void TraverseStack(LinkStack *stack, void (*fun)(Item item));

接口实现

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include "linkstack.h"

bool InitStack(LinkStack *stack)
{
    (*stack) = (LinkStack)malloc(sizeof(struct LinkStack));
    InitLinkList(&((*stack)->block));
    (*stack)->length = 0;
    (*stack)->base = (Item *)malloc(sizeof(Item));
    (*stack)->top = (Item *)malloc(sizeof(Item));
    printf("初始化LinkStack成功\n");
    return true;
}

bool DestroyStack(LinkStack *stack)
{
    DestroyLinkList(&((*stack)->block));
    free((*stack));
    (*stack) = NULL;
    printf("销毁LinkStack成功\n");
    return true;
}

bool ClearStack(LinkStack *stack)
{
    ClearLinkList(&((*stack)->block));
    (*stack)->length = 0;
    (*stack)->base = NULL;
    (*stack)->top = NULL;
    printf("清空LinkStack成功\n");
    return true;
}

bool EmptyStack(LinkStack *stack)
{
    if ((*stack)->length == 0)
    {
        printf("LinkStack空\n");
        return true;
    }
    else
    {
        printf("LinkStack不空\n");
        return false;
    }
}

bool GetTopStack(LinkStack *stack, Item *itemsave)
{
    if ((*stack)->length == 0)
    {
        printf("错误，栈中没有元素\n");
        return false;
    }
    else
    {
        *itemsave = *((*stack)->top);
        return true;
    }
}

bool PushStack(LinkStack *stack, Item *item)
{
    InsertLinkList(&((*stack)->block), (*stack)->length, item);
    (*stack)->length++;
    if ((*stack)->length == 1)
    {
        GetItemLinkList(&((*stack)->block), 0, (*stack)->base);
    }
    GetItemLinkList(&((*stack)->block), (*stack)->length - 1, (*stack)->top);
    return true;
}

bool PopStack(LinkStack *stack)
{
    if ((*stack)->length == 0)
    {
        printf("已经空了，不能pop\n");
        return false;
    }
    //删除top
    DeleteLinkList(&((*stack)->block), (*stack)->length - 1);
    (*stack)->length--;
    //更改top
    GetItemLinkList(&((*stack)->block), (*stack)->length - 1, (*stack)->top);
    return true;
}

void AutoFillStack(LinkStack *stack)
{
    for (int i = 0; i <= AUTOFILLSIZE; i++)
    {
        Item item;
        item.value = i;
        PushStack(stack, &item);
    }
}

void TraverseStack(LinkStack *stack, void (*fun)(Item item))
{
    printf("TraverseStack\n");
    Item item;
    while (!EmptyStack(stack))
    {
        GetTopStack(stack, &item);
        fun(item);
        PopStack(stack);
    }
}

接口使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "linkstack.c"

void fun(Item item)
{
    printf("item: %d\n", item.value);
}
int main()
{
    LinkStack stack;
    InitStack(&stack);
    AutoFillStack(&stack);
    TraverseStack(&stack, (*fun));
    ClearStack(&stack);
    DestroyStack(&stack);
}
文章作者: 崔文耀
文章链接: http://myblog.cuimouren.cn
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 崔文耀 !
数据结构 栈
  目录