栈,依靠线性表来实现。

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);
}