栈的创建（顺序表）_栈的建立

一、栈的定义

  栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
   压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
   出栈：栈的删除操作叫做出栈。出数据也在栈顶。
  通俗一点的理解就是，栈就像是一个羽毛球筒一样，先放进去的羽毛球，最后才能拿出来，反而后放进去的可以先拿出来，也就是我们上面提到的LIFO：Last In First Out。
  
  而栈我们可以通过顺序表来构建，也可以通过链表来构建，本文讲述的是顺序表构建内容。

二、栈的构建

  构建栈的需求有三个文件，包括Stack.c（用来书写逻辑的内容）、Stack.h（用来书写逻辑的声明）、test.c（用来测试我们所书写的代码）。

1、Stact.h（用来书写逻辑的声明）

  首先，先来梳理完成代码的逻辑，以方便后面内容的完成。
  先来创建一个结构体，包含数组、栈顶、以及空间大小。并且我们将他重命名一下，方便我们后面的使用。

 1. tydepef struct Stack
 2. {
 3. 	int* a;
 4. 	int top;
 5. 	int capacity;
 6. }Stack;

1
2
3
4
5
6
7
8

  为了方便以后解决其他类型的数组问题，所以将数组类型重新定义，方便以后修改。

 1. tydepef int STDataType;
 2. tydepef struct Stack
 3. {
 4. 	int* a;
 5. 	int top;
 6. 	int capacity;
 7. }Stack;

1
2
3
4
5
6
7
8
9

后面，需要分装几个函数来完成后面的代码编写。

 1. //初始化
 2.void STInit(Stack* ps);
 3.//顺序表的销毁
 4.void STDestroy(Stack* ps);
 5.//压栈
 6.void STPush(Stack* ps, STDataType x);
 7.//出栈
 8.void STPop(Stack* ps);
 9.//取栈顶数据
 10.STDataType STTop(Stack* ps);
 11.//栈判空
 12.bool STEmpty(Stack* ps);
 13.//栈的大小
 14.int STSize(Stack* ps);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、Stack.c（用来书写逻辑的内容）

2.2.1 栈的初始化

栈的初始化代码如下：

 1. //栈的初始化
 2. void STInit(Stack* ps)
 3. {
 4. 	assert(ps);
 5. 	ps->a = NULL;
 6. 
 7. 	//top指向栈顶的下一个数据
 8. 	ps->top = 0;
 9. 
 10. 	//top指向栈顶数据
 11. //ps->top = -1;
 12.  
 13. 	ps->capacity = 0;
 14. }
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

  这里对top的初始化有两种：一种让top指向栈顶下一个数据，一种让top指向栈顶数据。后面的代码我们用让top指向栈顶下一个数据。

2.2.2栈的销毁

栈的销毁代码如下：

 1. //栈的销毁
 2. void STDestroy(Stack* ps)
 3. {
 4. 	assert(ps);
 5. 
 6. 	free(ps->a);
 7. 	ps->a = NULL;
 8. 	ps->top = ps->capacity = 0;
 9. } 

1
2
3
4
5
6
7
8
9
10

2.2.3 压栈

  对于压栈，要判断数组空间是否足够，或则数组是否为NULL；如果数组空间不够或者为NULL；要对其开辟新空间(realloc),判断空间是否足够的条件为“top = capacity”。

 1. //压栈
 2. void STPush(Stack* ps, STDataType x)
 3. {
 4. 	assert(ps);
 5. 	if(ps->top == ps->capacity)
 6. 	{
 7. 		int newcapacity = ps->capacity == 0 ? 4 : 2*ps->capacity;
 8. 		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
 9. 		if(tmp == NULL)
 10. 		{
 11. 		perror("realloc:STPush");
 12. 		exit(1); 
 13. 	} 
 14. 	ps->a = tem;
 15. 	ps->capacity = newcapacity;
 16. 	}
 17. 	ps->a[ps->top] = x;
 18. 	ps->top++;
 19. }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.2.4 出栈

  出栈，就是将栈顶数据在栈中删除。这里很简单，只需要对top进行操作就可以了，top表示栈顶的下一个数据，所以top–就可以确定新栈顶的位置了，这里不需要对原来栈顶数据进行改变，下一次压栈的时候会有新数据来覆盖掉原来要删除的数据。

 1. //出栈
 2. void STPop(Stack* ps)
 3. {
 4. 	assert(ps);
 5. 	assert(ps->top > 0);
 6. 
 7. 	ps->top--;
 8. }

1
2
3
4
5
6
7
8
9
10

2.2.5取栈顶数据

取栈顶数据代码入下：

 1. //取栈顶数据
 2. STDataType STTop(Stack* ps)
 3. {
 4. 	assert(ps);
 5. 	asserrt(ps->top > 0);
 6. 
 7. 	return ps->a[ps->pos-1];
 8. } 

1
2
3
4
5
6
7
8
9
10

2.2.6 判空

对栈进行判空的代码如下：

 1. //判空
 2. bool STEmpty(Stack* ps)
 3. {
 4. 	assert(ps);
 5. 	assert(ps->top > 0);
 6. 	return ps->top == 0;
 7. }

1
2
3
4
5
6
7
8
9

2.2.7 栈的大小

对于站的大小，只需要知道top的值就可以了。

 1. //栈的大小
 2. int STSize(Stack* ps)
 3. {
 4. 	assert(ps);
 5. 	assert(ps->top > 0);
 6. 	
 7. 	return ps->top;
 8. }
1
2
3
4
5
6
7
8
9

三、完整代码展示

Stack.h

 1. #include <stdio.h>
 2. #include <stdlib.h>
 3. #include <stdbool.h>
 4. #include <assert.h>
 5.  
 6. tydepef int STDataType;
 7. tydepef struct Stack
 8. {
 9. 	int* a;
 10. 	int top;
 11. 	int capacity;
 12. }Stack;
 13. 
 14. //初始化
 15.void STInit(Stack* ps);
 16.//顺序表的销毁
 17.void STDestroy(Stack* ps);
 18.//压栈
 19.void STPush(Stack* ps, STDataType x);
 20.//出栈
 21.void STPop(Stack* ps);
 22.//取栈顶数据
 23.STDataType STTop(Stack* ps);
 24.//栈判空
 25.bool STEmpty(Stack* ps);
 26.//栈的大小
 27.int STSize(Stack* ps);
 
 
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

Stack.c

 1. #include "Stack.h"
 2. //栈的初始化
 3. void STInit(Stack* ps)
 4. {
 5. 	assert(ps);
 6. 	ps->a = NULL;
 7. 
 8. 	//top指向栈顶的下一个数据
 9. 	ps->top = 0;
 10. 
 11. 	//top指向栈顶数据
 12. //ps->top = -1;
 13.  
 14. 	ps->capacity = 0;
 15. }
 16.  
 17. 
 18. //栈的销毁
 19. void STDestroy(Stack* ps)
 20. {
 21. 	assert(ps);
 22.  
 23. 	free(ps->a);
 24. 	ps->a = NULL;
 25. 	ps->top = ps->capacity = 0;
 26. } 
 27. 
 28.  
 29. //压栈
 30. void STPush(Stack* ps, STDataType x)
 31. {
 32. 	assert(ps);
 33. 	if(ps->top == ps->capacity)
 34. 	{
 35. 		int newcapacity = ps->capacity == 0 ? 4 : 2*ps->capacity;
 36. 		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
 37. 		if(tmp == NULL)
 38. 		{
 39. 		perror("realloc:STPush");
 40. 		exit(1); 
 41. 	} 
 42. 	ps->a = tem;
 43. 	ps->capacity = newcapacity;
 44. 	}
 45. 	ps->a[ps->top] = x;
 46. 	ps->top++;
 47. }
 48.  
 49.  
 50. //出栈
 51. void STPop(Stack* ps)
 52. {
 53. 	assert(ps);
 54. 	assert(ps->top > 0);
 55. 
 56. 	ps->top--;
 57. }
 58. 
 59.  
 60. //取栈顶数据
 61. STDataType STTop(Stack* ps)
 62. {
 63. 	assert(ps);
 64. 	asserrt(ps->top > 0);
 65. 
 66. 	return ps->a[ps->pos-1];
 67. } 
 68. 
 69.  
 70. //判空
 71. bool STEmpty(Stack* ps)
 72. {
 73. 	assert(ps);
 74. 	assert(ps->top > 0);
 75. 	return ps->top == 0
 76. }
 77. 
 78.  
 79. //栈的大小
 80. int STSize(Stack* ps)
 81. {
 82. 	assert(ps);
 83. 	assert(ps->top > 0);
 84. 	
 85. 	return ps->top;
 86. }
 87. 

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

test.c

 1. #include "Stact.h"

 2.int main()
 3.{
 4.		// 入栈：1 2 3 4
 5.		// 出栈：4 3 2 1  /  2 4 3 1
 6.		ST s;
 7.		STInit(&s);
 8.		STPush(&s, 1);
 9.		STPush(&s, 2);
 10.
 11.	printf("%d ", STTop(&s));
 12.	STPop(&s);
 13.
 14.	STPush(&s, 3);
 15.	STPush(&s, 4);
 16.
 17.	while (!STEmpty(&s))
 18.	{
 19.		printf("%d ", STTop(&s));
 20.		STPop(&s);
 21.	}
 22.
 23.	STDestroy(&s);
 24.}

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