总结
本章将首先介绍堆栈的原理，然后演示C/C++/Java三种语言的堆栈实现示例。注意：本文所说的栈是数据结构中的栈，而不是内存模型中的栈。内容包括：
1。堆栈简介
2. C 栈的实现
3。堆栈的 C++ 实现
4。栈的Java实现
转载请注明出处：http://www.sychzs.cn/skywang12345/p/3562239.html
更多内容：数据结构与算法系列目录
堆栈介绍
Stack是一种线性存储结构。它具有以下特点：
(01) 栈中的数据按照“LIFO，后进先出”的方式进出栈。 。
(02)向堆栈添加/删除数据时，只能从堆栈顶部进行操作。
堆栈通常包括三个操作：push、peek、pop。
push -- 将一个元素添加到堆栈中。
peek -- 返回堆栈的顶部元素。
pop——返回并删除栈顶元素的操作。
1。堆栈图
堆栈中的数据为 30 --> 20 --> 10
2。弹出
出栈前：栈顶元素为30，此时栈内元素为30 --> 20 --> 10
出栈后 ：30出栈后，栈顶元素变成20，此时栈中元素为20 --> 10
3。推
入栈前：栈顶元素为20，此时栈内元素为20 --> 10
入栈后：入栈后40入栈，栈顶元素变成40。此时栈中元素为40 --> 20 --> 10
下面介绍栈的实现，分别介绍C/C++/Java的三种实现。
堆栈的C实现
一共介绍了4种C语言实现。
1。 C语言实现1：栈由数组实现，只能存储int数据。
2。 C语言实现二：单向链表实现的栈，只能存储int型数据。
3。 C语言实现三：双向链表实现的栈，只能存储int型数据。
4。 C语言实现四：双向链表实现的栈可以存储任意类型的数据。
1。 C语言实现一：数组实现的栈，只能存储int数据
实现代码(array_stack.c)
1 #include
2 #include
3
4 /**
5 * C语言：数组实现的栈只能存储int数据。
6 * 7 * @author skywang
8 * @日期 2013/11/07
9 */
10
11 // 保存数据的数组
12 静态 int *arr=NULL;
13 // 堆栈的实际大小
14 静态 int 计数；
15
16 // 创建一个“堆栈”，默认大小为12
17 int create_array_stack(int sz)
18 {
19 arr = (int *)malloc(sz*sizeof() int));
20 如果（！arr）
21 {
22 printf("arr malloc 错误！");
23 返回 -1；
24 }
25
26 返回 0；
27 }
28
29 // 摧毁“堆栈”
30 int destroy_array_stack()
31{ 32 if（编曲）
33 {
34 免费（已抵达）；
35 arr = NULL;
36 }
37
38 返回 0；
39}
40
41 // 将 val 添加到堆栈中
42 void推（intval）
43{
44 arr[count++] = val;
45}
46
47 // 返回“栈顶元素的值”
48 int peek()
49{
50 返回 arr[count-1];
51}
52
53 // 返回“顶部元素值”并删除“顶部元素”
54 int pop()
55 {
56 int ret = arr[count-1];
57计数--；
58 返回 ret;
59 }
60
61 // 返回“堆栈”的大小 62 int 尺寸()
63 {
64 返回计数；
65 }
66
67 // 返回“栈”是否为空
68 int is_empty()
69{
70 返回 size()==0;
71}
72
73 // 打印“堆栈”
74 void print_array_stack()
75{
76 if (is_empty())
77 {
78 printf("堆栈为空\n");
79 返回 ;
80 }
81
82 printf("堆栈大小()=%d\n", size());
83
84 int i=尺寸()-1;
85 同时 (i>=0)
86 {
87 printf("%d\n", arr[i]);
88我--； 89 }
90}
91
92
93 void main()
94{
95 int tmp=0;
96
97 // 创建一个“堆栈”
98 create_array_stack(12);
99
100 // 按顺序将 10、20、30 推入堆栈
101推(10);
102推(20);
103推(30);
104
105 //print_array_stack(); // 打印堆栈
106
107 // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
108 tmp = pop();
109 printf("tmp=%d\n", tmp);
110 //print_array_stack(); // 打印堆栈
111
112 // 只将“栈顶”赋值给 tmp，不删除该元素。
113 tmp = peek();
114 printf("tmp=%d\n", tmp);
115 //print_array_stack(); //打印堆栈
116
117推(40);
118 print_array_stack(); // 打印堆栈
119120 // 销毁堆栈
121 destroy_array_stack();
122 }
查看代码运行结果：
tmp=30
tmp=20
堆栈大小()=3
40
20
10
结果解释： 本例中的栈是通过“数组”实现的！
由于代码中已经给出了详细的注释，这里不再对该函数进行解释。只简单介绍一下主函数main的逻辑。
(01) 在主函数main中，首先将“10,20,30”依次压入堆栈。此时栈上的数据为： 30 --> 20 --> 10
(02) 然后通过pop()返回栈顶元素； pop()操作不会改变堆栈中的数据。此时栈数据依然是： 30 --> 20 --> 10
(03) 然后通过peek()返回并删除栈顶元素。 peek操作后，栈上的数据为： 20 --> 10
(04) 然后通过push(40)将40压入栈中。经过push(40)操作后，堆栈数据为：40 --> 20 --> 10
2。 C语言实现二：单向链表实现的栈，且只能存储int数据
实现代码(slink_stack.c)
1 #include
2 #include
3
4 /**
5 * C语言：单向链表实现的栈只能存储int型数据。
6 * 7 * @author skywang
8 * @日期 2013/11/07
9 */
10
11 // 单向链表的“节点”
12 结构 节点 {
13 int 值；
14 struct 节点* 接下来；
15}；
16
17 // 单向链表的“表头”
18 静态 结构节点 *phead=NULL;
19
20 // 创建节点，val为节点值
21 静态 结构节点* create_node(int) 值）
22 {
23 结构体节点 *pnode=NULL;
24 pnode = (struct节点*)malloc(sizeof() 结构节点））；
25 if（！p 节点）
26 返回 NULL；
27 pnode->val = val;
28 pnode->下一个= NULL;
29 30 返回 p 节点；
31}
32
33 // 销毁单向链表
34 静态 int destroy_single_link()
35 {
36 结构体节点 *pnode=NULL;
37
38 同时（phead！= NULL）{
39 pnode = phead；
40 phead = phead->下一个；
41 空闲（p 节点）；
42 }
43 返回0；
44}
45
46 // 将val插入链表头位置
47 静态 结构节点*推送（int） 值）
48{
49 结构体节点 *pnode = NULL;
50
51 pnode = create_node(val);
52 pnode->下一个= phead；
53 phead = pnode；
54 55 返回头；
56 }
57
58 //删除链表头
59 静态 int pop()
60 {
61 if（！头）
62 {
63 printf("删除失败！链接为空！");
64 返回 -1；
65 }
66
67 int ret；
68 结构体节点*p节点；
69 ret = phead->val;
70 pnode = phead；
71 phead = phead->下一个；
72 空闲（p 节点）；
73
74 返回 ret;
75}
76
77 // 返回链表头节点的值
78 静态 int peek()
79{
80 if（！头）
81 { 82 printf("查看失败！链接为空！");
83 返回 -1；
84 }
85
86 返回phead->val；
87}
88
89 // 返回链表中的节点数
90 静态 int 尺寸()
91{
92 int 计数=0；
93 struct节点 *pnode=phead;
94
95 同时（p节点！= NULL）{
96 pnode = pnode->下一个；
97 计数++；
98 }
99 返回计数；
100}
101
102 //链表是否为空
103 静态 int is_empty()
104{
105返回phead==NULL;
106}
107
108 // 打印“堆栈”
109 静态 void print_single_link()110{
111 if (is_empty())
112 {
113 printf("堆栈为空\n");
114返回0；
115 }
116
117 printf("堆栈大小()=%d\n", size());
118
119 struct节点 *pnode=NULL;
120
121 同时（phead！= NULL）{
122 printf("%d\n",phead->val);
123 pnode = phead；
124 phead = phead->下一个；
125 自由（pnode）；
126 }
127}
128
129 void main()
130{
131 int tmp=0;
132
133 //将10,20,30依次推入栈中
134推(10);
135推(20);
136推(30);
137
138 //print_single_link(); // 打印栈
139
140 //将“栈顶元素”属性赋予tmp，并删除“栈顶元素”
141 tmp = pop();
142 printf("tmp=%d\n", tmp);143 //print_single_link(); // 打印堆栈
144
145 // 只将“栈顶”赋值给tmp，不删除该元素。
146 tmp = peek();
147 printf("tmp=%d\n", tmp);
148 //print_single_link(); //打印堆栈
149
150推(40);
151 print_single_link(); // 打印堆栈
152
153 // 销毁堆栈
154 destroy_single_link();
155}
查看代码代码说明： “运行结果”和“主函数main的逻辑”与“C语言实现一”相同。 不同的是，本例中的栈是通过单向链表实现的。
3。 C语言实现三：双向链表实现的栈，且只能存储int数据
实现代码
双向链表头文件(double_link.h)
1 #ifndef _DOUBLE_LINK_H
2 #define _DOUBLE_LINK_H
3
4 // 创建一个新的“双链表”。如果成功，返回表头；否则返回NULL 5 外部 int create_dlink();
6 // 取消“双链表”。如果成功，返回0；否则返回-1
7 外部 int destroy_dlink();
8
9 //“双向链表是否为空？”如果为空则返回1；否则，返回 0。
10 extern int dlink_is_empty();
11 // 返回“双向链表的大小”
12 extern int dlink_size();
13
14 // 获取“双向链表中索引位置元素的值”。成功则返回节点值；否则，返回-1。
15 extern int dlink_get(int索引);
16 // 获取“双向链表第一个元素的值”。成功则返回节点值；否则，返回-1。
17 extern int dlink_get_first();
18 // 获取“双向链表最后一个元素的值”。成功则返回节点值；否则，返回-1。
19 extern int dlink_get_last();
20
21 // 将“值”插入索引位置。如果成功，返回0；否则，返回-1。
22 extern int dlink_insert(int索引, int值）；23 // 将“值”插入标题位置。如果成功，返回0；否则，返回-1。
24 extern int dlink_insert_first(int值) ）；
25 // 在末尾插入“值”。如果成功，返回0；否则，返回-1。
26 extern int dlink_append_last(int值) ）；
27
28 // 删除“双向链表中索引位置的节点”。如果成功，返回0；否则返回-1
ereXtern INT DLINK_DELETE（int索引）；
30 // 删除第一个节点。如果成功，返回0；否则返回-1
31 extern int dlink_delete_first();
32 // 删除组后的节点。如果成功，返回0；否则返回-1
33 extern int dlink_delete_last();
34
35 // 打印“双链表”
36 extern void print_dlink();
37
38#endif
查看代码双向链表的实现文件double_link.c)
1 #include 2 #include
3
4 /**
5 * c语言实现的双向链表
6 *
7 * @author skywang
8 * @日期 2013/11/07
9 */
10 // 双向链表节点
11 typedef struct tag_node
12 {
13 struct tag_node *上一个；
14 struct tag_node *下一个；
15 int值；
16 }节点；
17
18 // 标题。请注意，标头不存储元素值！ ！ ！
19 静态节点 *phead=NULL;
20 // 节点数。
21 静态 int 计数=0；
22
23 // 创建一个新的“节点”。成功则返回节点指针；否则，返回 NULL。
24 静态节点* create_node(int值)
25 {
26节点 *pnode=NULL; 27 pnode = (节点*)malloc(sizeof(节点));
28 if（！p 节点）
29 {
30 printf("创建节点错误！\n");
31 返回 NULL；
32 }
33 // 默认情况下，pnode的前一个节点和后一个节点都指向自身
34 pnode->上一个 = pnode->下一个 = pnode;
35 // 该节点的值为 value
36 pnode->值 = 值；
37
38 返回 p 节点；
39}
40
41 // 创建一个新的“双链表”。如果成功，返回0；否则，返回-1。
42 int create_dlink()
43{
44 // 创建标题
45 phead = create_node(-1);
46 if（！头）
47 返回 -1；
48
49 // 将“节点数”设置为 0 50 计数 = 0；
51
52 返回 0；
53}
54
55 //“双向链表是否为空”
56 int dlink_is_empty()
57 {
58 返回 计数 == 0；
59}
60
61 // 返回“双向链表的大小”
62 int dlink_size() {
63 返回计数；
64 }
65
66 // 获取“双向链表中索引位置的节点”
67 静态节点* get_node(int索引)
68 {
69 if（索引<0 || 索引>=计数）
70 {
71 printf("%s 失败！索引超出范围！\n", __func__);
72 返回 NULL；
73 }
74
75 // 向前搜索 76 if（索引 <=（计数/2））
77 {
78 int i=0；
79节点 *pnode=phead->下一个；
80 同时（（i++）<索引）
81 pnode = pnode->下一个；
82
83 // printf("%s %d i=%d, pnode->value=%d\n",
84 // __func__, __LINE__, i, pnode->value);
85 返回p节点；
86 }
87
88 // 反向查找
89 int j=0；
90 int rindex = 计数 - 索引 - 1；
91节点 *rnode=phead->prev;
92 同时 ((j++) < rindex)
93 rnode = rnode->上一个；
94
95 // printf("%s %d j=%d, rnode->value=%d\n", 96 // __func__, __LINE__, j, rnode->value);
97 返回 r节点；
98}
99
100 // 获取“第一个节点”
101 静态节点* get_first_node()
102{
103 返回 get_node(0);
104}
105
106 // 获取“最后一个节点”
107 静态节点* get_last_node()
108{
109 return get_node(count-1);
110}
111
112 // 获取“双向链表中索引位置元素的值”。成功则返回节点值；否则，返回-1。
113 int dlink_get(int索引)
114{
115节点 *pindex=get_node(index);
116 if（！pindex）
117 {
118 printf("%s 失败！\n", __func__);
119返回-1；
120}
121
122 返回 pindex->值；
123
124}
125
126 // 获取“双向链表第一个元素的值”127 int dlink_get_first()
128{
129 返回 dlink_get(0);
130}
131
132 // 获取“双向链表最后一个元素的值”
133 int dlink_get_last()
134{
135 返回 dlink_get(count-1);
136}
137
138 // 将“值”插入索引位置。如果成功，返回0；否则，返回-1。
LIintin dlink_insert（int索引，int值）
140{
141 // 插入标题
142 if（索引==0）
143 返回 dlink_insert_first(value);
144
145 // 获取要插入位置对应的节点
146节点 *pindex=get_node(index);
147 if（！pindex）
148返回-1；
149
150 // 创建“节点”
151节点 *pnode=create_node(value);
152 if（！p 节点）
153返回-1；
154
155 pnode->prev = pindex->prev;
156 pnode->下一个 = pindex;157 pindex->上一个->下一个 = pnode;
158 pindex->上一个 = pnode；
159 // 节点数+1
160计数++；
161
162返回0；
163}
164
165 // 将“值”插入标题位置
166 int dlink_insert_first(int值)
167{
168节点 *pnode=create_node(value);
169 if（！p 节点）
170 返回 -1；
171
172 pnode->prev = phead;
173 pnode->next = phead->next；
174 phead->下一个->上一个 = pnode;
175 phead->下一个= pnode;
176计数++；
177返回0；
178}
179
180 // 在末尾位置插入“值”
181 int dlink_append_last(int值)
182{
183节点 *pnode=create_node(value);
184 if（！p 节点）
185 返回 -1；
186
187 pnode->下一个 = phead;188 pnode->prev = phead->prev;
189 phead->上一个->下一个 = pnode;
190 phead->prev = pnode；
191计数++；
192返回0；
193}
194
195 // 删除“双向链表中索引位置的节点”。如果成功，返回0；否则，返回-1。
196 int dlink_delete(int索引)
197{
198节点 *pindex=get_node(index);
199 if（！pindex）
200 {
201 printf("%s 失败！索引超出范围！\n", __func__);
202 返回 -1；
203 }
204
205 pindex->下一个->上一个 = pindex->上一个；
206 pindex->上一个->下一个 = pindex->下一个；
207 免费（pindex）；
208计数--；
209
210返回0；
211}
212
213 // 删除第一个节点
214 int dlink_delete_first()
215 {
216 return dlink_delete(0);
217 }
218
219 // 删除组后一个节点
220 int dlink_delete_last()
221 {
222 return dlink_delete(count-1);
223 }
224
225 // 撤销“双向链表”。成功，返回0；否则，返回-1。
226 int destroy_dlink()
227 {
228 if (!phead)
229 {
230 printf("%s failed! dlink is null!\n", __func__);
231 return -1;
232 }
233
234 node *pnode=phead->next;
235 node *ptmp=NULL;
236 while(pnode != phead)
237 {
238 ptmp = pnode;
239 pnode = pnode->next;
240 free(ptmp);
241 }
242
243 free(phead);
244 phead = NULL;
245 count = 0;
246
247 return 0;
248 }
249
250 // 打印“双向链表”
251 void print_dlink()
252 {
253 if (count==0 || (!phead))
254 {
255 printf("stack is Empty\n");
256 return ;
257 }
258
259 printf("stack size()=%d\n", count);
260 node *pnode=phead->next;
261 while(pnode != phead)
262 {
263 printf("%d\n", pnode->value);
264 pnode = pnode->next;
265 }
266 }
View Code双向链表的测试程序(dlink_stack.c)
1 #include
2 #include "double_link.h"
3
4 /**
5 * C 语言: 双向链表实现栈，只能存储int数据。
6 *
7 * @author skywang
8 * @date 2013/11/07
9 */
10 // 创建栈
11 int create_dlink_stack()
12 {
13 return create_dlink();
14 }
15
16 // 销毁栈
17 int destroy_dlink_stack()
18 {
19 return destroy_dlink();
20 }
21
22 // 将val添加到栈中
23 int push(int val)
24 {
25 return dlink_insert_first(val);
26 }
27
28 // 返回“栈顶元素值”
29 int peek()
30 {
31 return dlink_get_first();
32 }
33
34 // 返回“栈顶元素值”，并删除“栈顶元素”
35 int pop()
36 {
37 int ret = peek();
38 dlink_delete_first();
39 return ret;
40 }
41
42 // 返回“栈”的大小
43 int size()
44 {
45 return dlink_size();
46 }
47
48 // 返回“栈”是否为空
49 int is_empty()
50 {
51 return dlink_is_empty();
52 }
53
54 // 打印“栈”
55 void print_dlink_stack()
56 {
57 return print_dlink();
58 }
59
60 void main()
61 {
62 int tmp=0;
63
64 // 创建“栈”
65 create_dlink_stack();
66
67 // 将10, 20, 30 依次推入栈中
68 push(10);
69 push(20);
70 push(30);
71
72 //print_dlink_stack(); // 打印栈
73
74 // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
75 tmp = pop();
76 printf("tmp=%d\n", tmp);
77 //print_dlink_stack(); // 打印栈
78
79 // 只将“栈顶”赋值给tmp，不删除该元素.
80 tmp = peek();
81 printf("tmp=%d\n", tmp);
82 //print_dlink_stack(); // 打印栈
83
84 push(40);
85 print_dlink_stack(); // 打印栈
86
87 // 销毁栈
88 destroy_dlink_stack();
89 }
View Code代码说明："运行结果" 以及 "主函数main的逻辑"都和前两个示例的一样。不同的是，该示例中的栈是通过双向链表实现的。
4. C语言实现四：双向链表实现的栈，能存储任意类型的数据
实现代码
双向链表的头文件(double_link.h)
1 #ifndef _DOUBLE_LINK_H
2 #define _DOUBLE_LINK_H
3
4 // 新建“双向链表”。成功，返回表头；否则，返回NULL
5 extern int create_dlink();
6 // 撤销“双向链表”。成功，返回0；否则，返回-1
7 extern int destroy_dlink();
8
9 // “双向链表是否为空”。为空的话返回1；否则，返回0。
10 extern int dlink_is_empty();
11 // 返回“双向链表的大小”
12 extern int dlink_size();
13
14 // 获取“双向链表中第index位置的元素”。成功，返回节点指针；否则，返回NULL。
15 extern void* dlink_get(int index);
16 // 获取“双向链表中第1个元素”。成功，返回节点指针；否则，返回NULL。
17 extern void* dlink_get_first();
18 // 获取“双向链表中最后1个元素”。成功，返回节点指针；否则，返回NULL。
19 extern void* dlink_get_last();
20
21 // 将“value”插入到index位置。成功，返回0；否则，返回-1。
22 extern int dlink_insert(int index, void *pval);
23 // 将“value”插入到表头位置。成功，返回0；否则，返回-1。
24 extern int dlink_insert_first(void *pval);
25 // 将“value”插入到末尾位置。成功，返回0；否则，返回-1。
26 extern int dlink_append_last(void *pval);
27
28 // 删除“双向链表中index位置的节点”。成功，返回0；否则，返回-1
29 extern int dlink_delete(int index);
30 // 删除第一个节点。成功，返回0；否则，返回-1
31 extern int dlink_delete_first();
32 // 删除组后一个节点。成功，返回0；否则，返回-1
33 extern int dlink_delete_last();
34
35 #endif
View Code双向链表的实现文件(double_link.c)
1 #include
2 #include
3
4
5 /**
6 * C 语言实现的双向链表，能存储任意数据。
7 *
8 * @author skywang
9 * @date 2013/11/07
10 */
11 // 双向链表节点
12 typedef struct tag_node
13 {
14 struct tag_node *prev;
15 struct tag_node *next;
16 void* p;
17 }node;
18
19 // 表头。注意，表头不存放元素值！！！
20 static node *phead=NULL;
21 // 节点个数。
22 static int count=0;
23
24 // 新建“节点”。成功，返回节点指针；否则，返回NULL。
25 static node* create_node(void *pval)
26 {
27 node *pnode=NULL;
28 pnode = (node *)malloc(sizeof(node));
29 if (!pnode)
30 {
31 printf("create node error!\n");
32 return NULL;
33 }
34 // 默认的，pnode的前一节点和后一节点都指向它自身
35 pnode->prev = pnode->next = pnode;
36 // 节点的值为pval
37 pnode->p = pval;
38
39 return pnode;
40 }
41
42 // 新建“双向链表”。成功，返回0；否则，返回-1。
43 int create_dlink()
44 {
45 // 创建表头
46 phead = create_node(NULL);
47 if (!phead)
48 return -1;
49
50 // 设置“节点个数”为0
51 count = 0;
52
53 return 0;
54 }
55
56 // “双向链表是否为空”
57 int dlink_is_empty()
58 {
59 return count == 0;
60 }
61
62 // 返回“双向链表的大小”
63 int dlink_size() {
64 return count;
65 }
66
67 // 获取“双向链表中第index位置的节点”
68 static node* get_node(int index)
69 {
70 if (index<0 || index>=count)
71 {
72 printf("%s failed! index out of bound!\n", __func__);
73 return NULL;
74 }
75
76 // 正向查找
77 if (index <= (count/2))
78 {
79 int i=0;
80 node *pnode=phead->next;
81 while ((i++) < index)
82 pnode = pnode->next;
83
84 return pnode;
85 }
86
87 // 反向查找
88 int j=0;
89 int rindex = count - index - 1;
90 node *rnode=phead->prev;
91 while ((j++) < rindex)
92 rnode = rnode->prev;
93
94 return rnode;
95 }
96
97 // 获取“第一个节点”
98 static node* get_first_node()
99 {
100 return get_node(0);
101 }
102
103 // 获取“最后一个节点”
104 static node* get_last_node()
105 {
106 return get_node(count-1);
107 }
108
109 // 获取“双向链表中第index位置的元素”。成功，返回节点值；否则，返回-1。
110 void* dlink_get(int index)
111 {
112 node *pindex=get_node(index);
113 if (!pindex)
114 {
115 printf("%s failed!\n", __func__);
116 return NULL;
117 }
118
119 return pindex->p;
120
121 }
122
123 // 获取“双向链表中第1个元素的值”
124 void* dlink_get_first()
125 {
126 return dlink_get(0);
127 }
128
129 // 获取“双向链表中最后1个元素的值”
130 void* dlink_get_last()
131 {
132 return dlink_get(count-1);
133 }
134
135 // 将“pval”插入到index位置。成功，返回0；否则，返回-1。
136 int dlink_insert(int index, void* pval)
137 {
138 // 插入表头
139 if (index==0)
140 return dlink_insert_first(pval);
141
142 // 获取要插入的位置对应的节点
143 node *pindex=get_node(index);
144 if (!pindex)
145 return -1;
146
147 // 创建“节点”
148 node *pnode=create_node(pval);
149 if (!pnode)
150 return -1;
151
152 pnode->prev = pindex->prev;
153 pnode->next = pindex;
154 pindex->prev->next = pnode;
155 pindex->prev = pnode;
156 // 节点个数+1
157 count++;
158
159 return 0;
160 }
161
162 // 将“pval”插入到表头位置
163 int dlink_insert_first(void *pval)
164 {
165 node *pnode=create_node(pval);
166 if (!pnode)
167 return -1;
168
169 pnode->prev = phead;
170 pnode->next = phead->next;
171 phead->next->prev = pnode;
172 phead->next = pnode;
173 count++;
174 return 0;
175 }
176
177 // 将“pval”插入到末尾位置
178 int dlink_append_last(void *pval)
179 {
180 node *pnode=create_node(pval);
181 if (!pnode)
182 return -1;
183
184 pnode->next = phead;
185 pnode->prev = phead->prev;
186 phead->prev->next = pnode;
187 phead->prev = pnode;
188 count++;
189 return 0;
190 }
191
192 // 删除“双向链表中index位置的节点”。成功，返回0；否则，返回-1。
193 int dlink_delete(int index)
194 {
195 node *pindex=get_node(index);
196 if (!pindex)
197 {
198 printf("%s failed! the index in out of bound!\n", __func__);
199 return -1;
200 }
201
202 pindex->next->prev = pindex->prev;
203 pindex->prev->next = pindex->next;
204 free(pindex);
205 count--;
206
207 return 0;
208 }
209
210 // 删除第一个节点
211 int dlink_delete_first()
212 {
213 return dlink_delete(0);
214 }
215
216 // 删除组后一个节点
217 int dlink_delete_last()
218 {
219 return dlink_delete(count-1);
220 }
221
222 // 撤销“双向链表”。成功，返回0；否则，返回-1。
223 int destroy_dlink()
224 {
225 if (!phead)
226 {
227 printf("%s failed! dlink is null!\n", __func__);
228 return -1;
229 }
230
231 node *pnode=phead->next;
232 node *ptmp=NULL;
233 while(pnode != phead)
234 {
235 ptmp = pnode;
236 pnode = pnode->next;
237 free(ptmp);
238 }
239
240 free(phead);
241 phead = NULL;
242 count = 0;
243
244 return 0;
245 }
View Code双向链表的测试程序(dlink_stack.c)
1 #include
2 #include "double_link.h"
3
4 /**
5 * C 语言: 双向链表实现栈，能存储任意数据。
6 *
7 * @author skywang
8 * @date 2013/11/07
9 */
10 // 创建栈
11 int create_dlink_stack()
12 {
13 return create_dlink();
14 }
15
16 // 销毁栈
17 int destroy_dlink_stack()
18 {
19 return destroy_dlink();
20 }
21
22 // 将val添加到栈中
23 int push(void *p)
24 {
25 return dlink_insert_first(p);
26 }
27
28 // 返回“栈顶元素值”
29 void* peek()
30 {
31 return dlink_get_first();
32 }
33
34 // 返回“栈顶元素值”，并删除“栈顶元素”
35 void* pop()
36 {
37 void *p = peek();
38 dlink_delete_first();
39 return p;
40 }
41
42 // 返回“栈”的大小
43 int size()
44 {
45 return dlink_size();
46 }
47
48 // 返回“栈”是否为空
49 int is_empty()
50 {
51 return dlink_is_empty();
52 }
53
54
55 typedef struct tag_stu
56 {
57 int id;
58 char name[20];
59 }stu;
60
61 static stu arr_stu[] =
62 {
63 {10, "sky"},
64 {20, "jody"},
65 {30, "vic"},
66 {40, "dan"},
67 };
68 #define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )
69
70 static void print_stu(stu *p)
71 {
72 if (!p)
73 return ;
74
75 printf("id=%d, name=%s\n", p->id, p->name);
76 }
77
78 void main()
79 {
80 stu *pval=NULL;
81
82 // 创建“栈”
83 create_dlink_stack();
84
85 // 将10, 20, 30 依次推入栈中
86 int i=0;
87 for (i=0; i1; i++)
88 {
89 push(&arr_stu[i]);
90 }
91
92 // 将“栈顶元素”赋值给pval，并删除“栈顶元素”
93 pval = (stu*)pop();
94 //print_stu(pval) ;
95
96 // 只将“栈顶”赋值给pval，不删除该元素.
97 pval = peek();
98 //print_stu(pval) ;
99
100 push(&arr_stu[ARR_STU_SIZE-1]);
101
102
103 // 打印栈中的所有元素
104 while (!is_empty())
105 {
106 pval = pop();
107 print_stu(pval) ;
108 }
109
110 // 销毁栈
111 destroy_dlink_stack();
112 }
View Code运行结果：
id=40, name=dan
id=20, name=jody
id=10, name=sky
结果说明：该示例中的栈是通过双向链表实现的，并且能存储任意类型的数据。示例中是以结构体类型的数据进行演示的，由于代码中已经给出了详细的注释，这里就不再介绍了。
栈的C++实现
C++的STL中本身就包含了stack类，基本上该stack类就能满足我们的需求，所以很少需要我们自己来实现。本部分介绍2种C++实现。
1. C++实现一：数组实现的栈，能存储任意类型的数据。
2. C++实现二：C++的 STL 中自带的"栈"(stack)的示例。
1. C++实现一：数组实现的栈，能存储任意类型的数据
实现代码
栈的实现文件(ArrayStack.h)
1 #ifndef ARRAY_STACK_HXX
2 #define ARRAY_STACK_HXX
3
4 #include
5 #include "ArrayStack.h"
6 using namespace std;
7
8 template<class T> class ArrayStack{
9 public:
10 ArrayStack();
11 ~ArrayStack();
12
13 void push(T t);
14 T peek();
15 T pop();
16 int size();
17 int isEmpty();
18 private:
19 T *arr;
20 int count;
21 };
22
23 // 创建“栈”，默认大小是12
24 template<class T>
25 ArrayStack::ArrayStack()
26 {
27 arr = new T[12];
28 if (!arr)
29 {
30 cout<<"arr malloc error!"<<endl;
31 }
32 }
33
34 // 销毁“栈”
35 template<class T>
36 ArrayStack::~ArrayStack()
37 {
38 if (arr)
39 {
40 delete[] arr;
41 arr = NULL;
42 }
43 }
44
45 // 将val添加到栈中
46 template<class T>
47 void ArrayStack::push(T t)
48 {
49 //arr[count++] = val;
50 arr[count++] = t;
51 }
52
53 // 返回“栈顶元素值”
54 template<class T>
55 T ArrayStack::peek()
56 {
57 return arr[count-1];
58 }
59
60 // 返回“栈顶元素值”，并删除“栈顶元素”
61 template<class T>
62 T ArrayStack::pop()
63 {
64 int ret = arr[count-1];
65 count--;
66 return ret;
67 }
68
69 // 返回“栈”的大小
70 template<class T>
71 int ArrayStack::size()
72 {
73 return count;
74 }
75
76 // 返回“栈”是否为空
77 template<class T>
78 int ArrayStack::isEmpty()
79 {
80 return size()==0;
81 }
82
83 #endif
View Code栈的测试程序(Main.cpp)
1 #include
2 #include "ArrayStack.h"
3 using namespace std;
4
5 int main()
6 {
7 int tmp=0;
8 ArrayStack<int> *astack = new ArrayStack<int>();
9
10 cout<<"main"<<endl;
11
12 // 将10, 20, 30 依次推入栈中
13 astack->push(10);
14 astack->push(20);
15 astack->push(30);
16
17 // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
18 tmp = astack->pop();
19 cout<<"tmp="<endl;
20
21 // 只将“栈顶”赋值给tmp，不删除该元素.
22 tmp = astack->peek();
23
24 astack->push(40);
25
26 while (!astack->isEmpty())
27 {
28 tmp = astack->pop();
29 cout<endl;
30 }
31
32 return 0;
33 }
View Code运行结果：
结果说明：关于"栈的声明和实现都在头文件中"的原因，是因为栈的实现利用了C++模板，而"C++编译器不能支持对模板的分离式编译"。这在"数据结构和算法01之 线性表"中已经介绍过了。 程序的实现和逻辑都非常简单。需要说明的是，采用C++模板实现的；但是，默认数组的大小只有12，而且该实现不支持动态扩展。
2. C++实现二：C++的 STL 中自带的"栈"(stack)的示例
实现代码(StlStack.cpp)
1 #include
2 #include
3 using namespace std;
4
5 /**
6 * C++ 语言: STL 自带的“栈”(stack)的示例。
7 *
8 * @author skywang
9 * @date 2013/11/07
10 */
11 int main ()
12 {
13 int tmp=0;
14 stack<int> istack;
15
16 // 将10, 20, 30 依次推入栈中
17 istack.push(10);
18 istack.push(20);
19 istack.push(30);
20
21 // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
22 istack.pop();
23
24 // 只将“栈顶”赋值给tmp，不删除该元素.
25 tmp = www.sychzs.cn();
26
27 istack.push(40);
28
29 while (!istack.empty())
30 {
31 tmp = www.sychzs.cn();
32 istack.pop();
33 cout<endl;
34 }
35
36 return 0;
37 }
View Code运行结果：
栈的Java实现
和C++一样，JDK包中也提供了"栈"的实现，它就是集合框架中的Stack类。关于Stack类的原理，在"Java 集合系列07之 Stack详细介绍(源码解析)和使用示例"中，已经详细介绍过了。本部分给出2种Java实现
Java实现一：数组实现的栈，能存储任意类型的数据。
Java实现二：Java的 Collection集合 中自带的"栈"(stack)的示例。
1. Java实现一：数组实现的栈，能存储任意类型的数据
实现代码(www.sychzs.cn)
1 /**
2 * Java : 数组实现的栈，能存储任意类型的数据
3 *
4 * @author skywang
5 * @date 2013/11/07
6 */
7 import java.lang.reflect.Array;
8
9 public class GeneralArrayStack {
10
11 private static final int DEFAULT_SIZE = 12;
12 private T[] mArray;
13 private int count;
14
15 public GeneralArrayStack(Class type) {
16 this(type, DEFAULT_SIZE);
17 }
18
19 public GeneralArrayStack(Class type, int size) {
20 // 不能直接使用mArray = new T[DEFAULT_SIZE];
21 mArray = (T[]) Array.newInstance(type, size);
22 count = 0;
23 }
24
25 // 将val添加到栈中
26 public void push(T val) {
27 mArray[count++] = val;
28 }
29
30 // 返回“栈顶元素值”
31 public T peek() {
32 return mArray[count-1];
33 }
34
35 // 返回“栈顶元素值”，并删除“栈顶元素”
36 public T pop() {
37 T ret = mArray[count-1];
38 count--;
39 return ret;
40 }
41
42 // 返回“栈”的大小
43 public int size() {
44 return count;
45 }
46
47 // 返回“栈”是否为空
48 public boolean isEmpty() {
49 return size()==0;
50 }
51
52 // 打印“栈”
53 public void PrintArrayStack() {
54 if (isEmpty()) {
55 System.out.printf("stack is Empty\n");
56 }
57
58 System.out.printf("stack size()=%d\n", size());
59
60 int i=size()-1;
61 while (i>=0) {
62 System.out.println(mArray[i]);
63 i--;
64 }
65 }
66
67 public static void main(String[] args) {
68 String tmp;
69 GeneralArrayStack astack = new GeneralArrayStack(String.class);
70
71 // 将10, 20, 30 依次推入栈中
72 astack.push("10");
73 astack.push("20");
74 astack.push("30");
75
76 // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
77 tmp = astack.pop();
78 System.out.println("tmp="+tmp);
79
80 // 只将“栈顶”赋值给tmp，不删除该元素.
81 tmp = astack.peek();
82 System.out.println("tmp="+tmp);
83
84 astack.push("40");
85 astack.PrintArrayStack(); // 打印栈
86 }
87 }
View Code运行结果：
1 tmp=30
2 tmp=20
3 stack size()=3
4 40
5 20
6 10
View Code结果说明：GeneralArrayStack是通过数组实现的栈，而且GeneralArrayStack中使用到了泛型。
2. Java实现二：Java的 Collection集合 中自带的"栈"(stack)的示例
实现代码(www.sychzs.cn)
1 import java.util.Stack;
2
3 /**
4 * Java : java集合包中的Stack的演示程序
5 *
6 * @author skywang
7 * @date 2013/11/07
8 */
9 public class StackTest {
10
11 public static void main(String[] args) {
12 int tmp=0;
13 Stack astack = new Stack();
14
15 // 将10, 20, 30 依次推入栈中
16 astack.push(10);
17 astack.push(20);
18 astack.push(30);
19
20 // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
21 tmp = astack.pop();
22 //System.out.printf("tmp=%d\n", tmp);
23
24 // 只将“栈顶”赋值给tmp，不删除该元素.
25 tmp = (int)astack.peek();
26 //System.out.printf("tmp=%d\n", tmp);
27
28 astack.push(40);
29 while(!astack.empty()) {
30 tmp = (int)astack.pop();
31 System.out.printf("tmp=%d\n", tmp);
32 }
33 }
34 }
View Code运行结果：
