栈的图文解析 和 对应3种语言的实现(C/C++/Java)

Posted on | Edited on | In | Views:

概要

本章会先对栈的原理进行介绍，然后分别通过C/C++/Java三种语言来演示栈的实现示例。注意：本文所说的栈是数据结构中的栈，而不是内存模型中栈。内容包括：

  1. 栈的介绍
  2. 栈的C实现
  3. 栈的C++实现
  4. 栈的Java实现

栈的介绍

栈（stack），是一种线性存储结构，它有以下几个特点：

(01) 栈中数据是按照”后进先出（LIFO, Last In First Out）”方式进出栈的。

(02) 向栈中添加/删除数据时，只能从栈顶进行操作。

栈通常包括的三种操作：push、peek、pop。

1
2
3
push -- 向栈中添加元素。
peek -- 返回栈顶元素。
pop  -- 返回并删除栈顶元素的操作。
  1. 栈的示意图

栈中的数据依次是 30 –> 20 –> 10

  1. 出栈

出栈前：栈顶元素是30。此时，栈中的元素依次是 30 –> 20 –> 10

出栈后：30出栈之后，栈顶元素变成20。此时，栈中的元素依次是 20 –> 10

  1. 入栈

入栈前：栈顶元素是20。此时，栈中的元素依次是 20 –> 10

入栈后：40入栈之后，栈顶元素变成40。此时，栈中的元素依次是 40 –> 20 –> 10

实现

下面介绍栈的实现，分别介绍C/C++/Java三种实现。

栈的C实现

共介绍4种C语言实现。

  1. C语言实现一：数组实现的栈，并且只能存储int数据。
  2. C语言实现二：单向链表实现的栈，并且只能存储int数据。
  3. C语言实现三：双向链表实现的栈，并且只能存储int数据。
  4. C语言实现四：双向链表实现的栈，能存储任意类型的数据。

1. C语言实现一：数组实现的栈，并且只能存储int数据

实现代码(array_stack.c)

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
#include <stdio.h>
#include <malloc.h>

/**
 * C 语言: 数组实现的栈，只能存储int数据。
 *
 * @author skywang
 * @date 2013/11/07
 */

// 保存数据的数组
static int *arr=NULL;
// 栈的实际大小
static int count;

// 创建“栈”，默认大小是12
int create_array_stack(int sz) 
{
    arr = (int *)malloc(sz*sizeof(int));
    if (!arr) 
    {
        printf("arr malloc error!");
        return -1;
    }

    return 0;
}

// 销毁“栈”
int destroy_array_stack() 
{
    if (arr) 
    {
        free(arr);
        arr = NULL;
    }

    return 0;
}

// 将val添加到栈中
void push(int val) 
{
    arr[count++] = val;
}

// 返回“栈顶元素值”
int peek() 
{
    return arr[count-1];
}

// 返回“栈顶元素值”，并删除“栈顶元素”
int pop() 
{
    int ret = arr[count-1];
    count--;
    return ret;
}

// 返回“栈”的大小
int size() 
{
    return count;
}

// 返回“栈”是否为空
int is_empty()
{
    return size()==0;
}

// 打印“栈”
void print_array_stack()
{
    if (is_empty()) 
    {
        printf("stack is Empty\n");
        return ;
    }

    printf("stack size()=%d\n", size());

    int i=size()-1;
    while (i>=0)
    {
        printf("%d\n", arr[i]);
        i--;
    }
}


void main() 
{
    int tmp=0;

    // 创建“栈”
    create_array_stack(12);

    // 将10, 20, 30 依次推入栈中
    push(10);
    push(20);
    push(30);

    //print_array_stack();    // 打印栈

    // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
    tmp = pop();
    printf("tmp=%d\n", tmp);
    //print_array_stack();    // 打印栈

    // 只将“栈顶”赋值给tmp，不删除该元素.
    tmp = peek();
    printf("tmp=%d\n", tmp);
    //print_array_stack();    // 打印栈

    push(40);
    print_array_stack();    // 打印栈

    // 销毁栈
    destroy_array_stack();
}

运行结果：

1
2
3
4
5
6
tmp=30
tmp=20
stack size()=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
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h>
#include <malloc.h>

/**
 * C 语言: 单向链表实现的栈，只能存储int数据。
 *
 * @author skywang
 * @date 2013/11/07
 */

// 单向链表的“节点”
struct node {
    int val;
    struct node* next;
};

// 单向链表的“表头”
static struct node *phead=NULL;

// 创建节点，val为节点值
static struct node* create_node(int val) 
{
    struct node *pnode=NULL;
    pnode = (struct node*)malloc(sizeof(struct node));
    if (!pnode)
        return NULL;
    pnode->val = val;
    pnode->next = NULL;
    
    return pnode;
}

// 销毁单向链表
static int destroy_single_link() 
{
    struct node *pnode=NULL;

    while (phead != NULL) {
        pnode = phead;
        phead = phead->next;
        free(pnode);
    }
    return 0;
}

// 将val插入到链表的表头位置
static struct node* push(int val) 
{
    struct node *pnode = NULL;
    
    pnode = create_node(val);
    pnode->next = phead;
    phead = pnode;
    
    return phead;
}

// 删除链表的表头
static int pop() 
{
    if (!phead)
    {
        printf("remove failed! link is empty!");
        return -1;
    }
    
    int ret;
    struct node *pnode;
    ret = phead->val;
    pnode = phead;
    phead = phead->next;
    free(pnode);

    return ret;
}

// 返回链表的表头节点的值
static int peek() 
{
    if (!phead)
    {
        printf("peek failed! link is empty!");
        return -1;
    }

    return phead->val;
}

// 返回链表中节点的个数
static int size() 
{
    int count=0;
    struct node *pnode=phead;

    while (pnode != NULL) {
        pnode = pnode->next;
        count++;
    }
    return count;
}

// 链表是否为空
static int is_empty() 
{
    return phead==NULL;
}

// 打印“栈”
static void print_single_link()
{
    if (is_empty()) 
    {
        printf("stack is Empty\n");
        return 0;
    }

    printf("stack size()=%d\n", size());

    struct node *pnode=NULL;

    while (phead != NULL) {
        printf("%d\n", phead->val);
        pnode = phead;
        phead = phead->next;
        free(pnode);
    }
}

void main() 
{
    int tmp=0;

    // 将10, 20, 30 依次推入栈中
    push(10);
    push(20);
    push(30);

    //print_single_link();    // 打印栈

    // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
    tmp = pop();
    printf("tmp=%d\n", tmp);
    //print_single_link();    // 打印栈

    // 只将“栈顶”赋值给tmp，不删除该元素.
    tmp = peek();
    printf("tmp=%d\n", tmp);
    //print_single_link();    // 打印栈

    push(40);
    print_single_link();    // 打印栈

    // 销毁栈
    destroy_single_link();
}

代码说明：”运行结果” 以及 “主函数main的逻辑”都和”C语言实现一”的一样。不同的是，该示例中的栈是通过单向链表实现的。

3. C语言实现三：双向链表实现的栈，并且只能存储int数据

实现代码

双向链表的头文件(double_link.h)

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
#ifndef _DOUBLE_LINK_H
#define _DOUBLE_LINK_H

// 新建“双向链表”。成功，返回表头；否则，返回NULL
extern int create_dlink();
// 撤销“双向链表”。成功，返回0；否则，返回-1
extern int destroy_dlink();

// “双向链表是否为空”。为空的话返回1；否则，返回0。
extern int dlink_is_empty();
// 返回“双向链表的大小”
extern int dlink_size();

// 获取“双向链表中第index位置的元素的值”。成功，返回节点值；否则，返回-1。
extern int dlink_get(int index);
// 获取“双向链表中第1个元素的值”。成功，返回节点值；否则，返回-1。
extern int dlink_get_first();
// 获取“双向链表中最后1个元素的值”。成功，返回节点值；否则，返回-1。
extern int dlink_get_last();

// 将“value”插入到index位置。成功，返回0；否则，返回-1。
extern int dlink_insert(int index, int value);
// 将“value”插入到表头位置。成功，返回0；否则，返回-1。
extern int dlink_insert_first(int value);
// 将“value”插入到末尾位置。成功，返回0；否则，返回-1。
extern int dlink_append_last(int value);

// 删除“双向链表中index位置的节点”。成功，返回0；否则，返回-1
extern int dlink_delete(int index);
// 删除第一个节点。成功，返回0；否则，返回-1
extern int dlink_delete_first();
// 删除组后一个节点。成功，返回0；否则，返回-1
extern int dlink_delete_last();

// 打印“双向链表”
extern void print_dlink();

#endif

双向链表的实现文件double_link.c)

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
#include <stdio.h>
#include <malloc.h>

/**
 * c语言实现的双向链表
 *
 * @author skywang
 * @date   2013/11/07
 */
// 双向链表节点
typedef struct tag_node 
{
    struct tag_node *prev;
    struct tag_node *next;
    int value;
}node;

// 表头。注意，表头不存放元素值！！！
static node *phead=NULL;
// 节点个数。
static int  count=0;

// 新建“节点”。成功，返回节点指针；否则，返回NULL。
static node* create_node(int value)
{
    node *pnode=NULL;
    pnode = (node *)malloc(sizeof(node));
    if (!pnode)
    {
        printf("create node error!\n");
        return NULL;
    }
    // 默认的，pnode的前一节点和后一节点都指向它自身
    pnode->prev = pnode->next = pnode;
    // 节点的值为value
    pnode->value = value;

    return pnode;
}

// 新建“双向链表”。成功，返回0；否则，返回-1。
int create_dlink()
{
    // 创建表头
    phead = create_node(-1);
    if (!phead)
        return -1;

    // 设置“节点个数”为0
    count = 0;

    return 0;
}

// “双向链表是否为空”
int dlink_is_empty()
{
    return count == 0;
}

// 返回“双向链表的大小”
int dlink_size() {
    return count;
}

// 获取“双向链表中第index位置的节点”
static node* get_node(int index) 
{
    if (index<0 || index>=count)
    {
        printf("%s failed! the index in out of bound!\n", __func__);
        return NULL;
    }

    // 正向查找
    if (index <= (count/2))
    {
        int i=0;
        node *pnode=phead->next;
        while ((i++) < index) 
            pnode = pnode->next;

//        printf("%s %d i=%d, pnode->value=%d\n", 
//                __func__, __LINE__, i, pnode->value);
        return pnode;
    }

    // 反向查找
    int j=0;
    int rindex = count - index - 1;
    node *rnode=phead->prev;
    while ((j++) < rindex) 
        rnode = rnode->prev;

//    printf("%s %d j=%d, rnode->value=%d\n", 
//            __func__, __LINE__, j, rnode->value);
    return rnode;
}

// 获取“第一个节点”
static node* get_first_node() 
{
    return get_node(0);
}

// 获取“最后一个节点”
static node* get_last_node() 
{
    return get_node(count-1);
}

// 获取“双向链表中第index位置的元素的值”。成功，返回节点值；否则，返回-1。
int dlink_get(int index)
{
    node *pindex=get_node(index);
    if (!pindex) 
    {
        printf("%s failed!\n", __func__);
        return -1;
    }

    return pindex->value;

}

// 获取“双向链表中第1个元素的值”
int dlink_get_first()
{
    return dlink_get(0);
}

// 获取“双向链表中最后1个元素的值”
int dlink_get_last()
{
    return dlink_get(count-1);
}

// 将“value”插入到index位置。成功，返回0；否则，返回-1。
int dlink_insert(int index, int value) 
{
    // 插入表头
    if (index==0)
        return dlink_insert_first(value);

    // 获取要插入的位置对应的节点
    node *pindex=get_node(index);
    if (!pindex) 
        return -1;

    // 创建“节点”
    node *pnode=create_node(value);
    if (!pnode)
        return -1;

    pnode->prev = pindex->prev;
    pnode->next = pindex;
    pindex->prev->next = pnode;
    pindex->prev = pnode;
    // 节点个数+1
    count++;

    return 0;
}

// 将“value”插入到表头位置
int dlink_insert_first(int value) 
{
    node *pnode=create_node(value);
    if (!pnode)
        return -1;

    pnode->prev = phead;
    pnode->next = phead->next;
    phead->next->prev = pnode;
    phead->next = pnode;
    count++;
    return 0;
}

// 将“value”插入到末尾位置
int dlink_append_last(int value) 
{
    node *pnode=create_node(value);
    if (!pnode)
        return -1;
    
    pnode->next = phead;
    pnode->prev = phead->prev;
    phead->prev->next = pnode;
    phead->prev = pnode;
    count++;
    return 0;
}

// 删除“双向链表中index位置的节点”。成功，返回0；否则，返回-1。
int dlink_delete(int index)
{
    node *pindex=get_node(index);
    if (!pindex) 
    {
        printf("%s failed! the index in out of bound!\n", __func__);
        return -1;
    }

    pindex->next->prev = pindex->prev;
    pindex->prev->next = pindex->next;
    free(pindex);
    count--;

    return 0;
}    

// 删除第一个节点
int dlink_delete_first() 
{
    return dlink_delete(0);
}

// 删除组后一个节点
int dlink_delete_last() 
{
    return dlink_delete(count-1);
}

// 撤销“双向链表”。成功，返回0；否则，返回-1。
int destroy_dlink()
{
    if (!phead)
    {
        printf("%s failed! dlink is null!\n", __func__);
        return -1;
    }

    node *pnode=phead->next;
    node *ptmp=NULL;
    while(pnode != phead)
    {
        ptmp = pnode;
        pnode = pnode->next;
        free(ptmp);
    }

    free(phead);
    phead = NULL;
    count = 0;

    return 0;
}

// 打印“双向链表”
void print_dlink()
{
    if (count==0 || (!phead))
    {
        printf("stack is Empty\n");
        return ;
    }

    printf("stack size()=%d\n", count);
    node *pnode=phead->next;
    while(pnode != phead)
    {
        printf("%d\n", pnode->value);
        pnode = pnode->next;
    }
}

双向链表的测试程序(dlink_stack.c)

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
#include <stdio.h>
#include "double_link.h"

/**
 * C 语言: 双向链表实现栈，只能存储int数据。
 *
 * @author skywang
 * @date 2013/11/07
 */
// 创建栈
int create_dlink_stack() 
{
    return create_dlink();
}

// 销毁栈
int destroy_dlink_stack() 
{
    return destroy_dlink();
}

// 将val添加到栈中
int push(int val) 
{
    return dlink_insert_first(val);
}

// 返回“栈顶元素值”
int peek() 
{
    return dlink_get_first();
}

// 返回“栈顶元素值”，并删除“栈顶元素”
int pop() 
{
    int ret = peek();
    dlink_delete_first();
    return ret;
}

// 返回“栈”的大小
int size() 
{
    return dlink_size();
}

// 返回“栈”是否为空
int is_empty()
{
    return dlink_is_empty();
}

// 打印“栈”
void print_dlink_stack()
{
    return print_dlink();
}

void main()
{
    int tmp=0;

    // 创建“栈”
    create_dlink_stack();

    // 将10, 20, 30 依次推入栈中
    push(10);
    push(20);
    push(30);

    //print_dlink_stack();    // 打印栈

    // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
    tmp = pop();
    printf("tmp=%d\n", tmp);
    //print_dlink_stack();    // 打印栈

    // 只将“栈顶”赋值给tmp，不删除该元素.
    tmp = peek();
    printf("tmp=%d\n", tmp);
    //print_dlink_stack();    // 打印栈

    push(40);
    print_dlink_stack();    // 打印栈

    // 销毁栈
    destroy_dlink_stack();
}

代码说明：”运行结果” 以及 “主函数main的逻辑”都和前两个示例的一样。不同的是，该示例中的栈是通过双向链表实现的。

4. C语言实现四：双向链表实现的栈，能存储任意类型的数据

实现代码

双向链表的头文件(double_link.h)

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
#ifndef _DOUBLE_LINK_H
#define _DOUBLE_LINK_H

// 新建“双向链表”。成功，返回表头；否则，返回NULL
extern int create_dlink();
// 撤销“双向链表”。成功，返回0；否则，返回-1
extern int destroy_dlink();

// “双向链表是否为空”。为空的话返回1；否则，返回0。
extern int dlink_is_empty();
// 返回“双向链表的大小”
extern int dlink_size();

// 获取“双向链表中第index位置的元素”。成功，返回节点指针；否则，返回NULL。
extern void* dlink_get(int index);
// 获取“双向链表中第1个元素”。成功，返回节点指针；否则，返回NULL。
extern void* dlink_get_first();
// 获取“双向链表中最后1个元素”。成功，返回节点指针；否则，返回NULL。
extern void* dlink_get_last();

// 将“value”插入到index位置。成功，返回0；否则，返回-1。
extern int dlink_insert(int index, void *pval);
// 将“value”插入到表头位置。成功，返回0；否则，返回-1。
extern int dlink_insert_first(void *pval);
// 将“value”插入到末尾位置。成功，返回0；否则，返回-1。
extern int dlink_append_last(void *pval);

// 删除“双向链表中index位置的节点”。成功，返回0；否则，返回-1
extern int dlink_delete(int index);
// 删除第一个节点。成功，返回0；否则，返回-1
extern int dlink_delete_first();
// 删除组后一个节点。成功，返回0；否则，返回-1
extern int dlink_delete_last();

#endif

双向链表的实现文件(double_link.c)

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
#include <stdio.h>
#include <malloc.h>


/**
 * C 语言实现的双向链表，能存储任意数据。
 *
 * @author skywang
 * @date 2013/11/07
 */
// 双向链表节点
typedef struct tag_node 
{
    struct tag_node *prev;
    struct tag_node *next;
    void* p;
}node;

// 表头。注意，表头不存放元素值！！！
static node *phead=NULL;
// 节点个数。
static int  count=0;

// 新建“节点”。成功，返回节点指针；否则，返回NULL。
static node* create_node(void *pval)
{
    node *pnode=NULL;
    pnode = (node *)malloc(sizeof(node));
    if (!pnode)
    {
        printf("create node error!\n");
        return NULL;
    }
    // 默认的，pnode的前一节点和后一节点都指向它自身
    pnode->prev = pnode->next = pnode;
    // 节点的值为pval
    pnode->p = pval;

    return pnode;
}

// 新建“双向链表”。成功，返回0；否则，返回-1。
int create_dlink()
{
    // 创建表头
    phead = create_node(NULL);
    if (!phead)
        return -1;

    // 设置“节点个数”为0
    count = 0;

    return 0;
}

// “双向链表是否为空”
int dlink_is_empty()
{
    return count == 0;
}

// 返回“双向链表的大小”
int dlink_size() {
    return count;
}

// 获取“双向链表中第index位置的节点”
static node* get_node(int index) 
{
    if (index<0 || index>=count)
    {
        printf("%s failed! index out of bound!\n", __func__);
        return NULL;
    }

    // 正向查找
    if (index <= (count/2))
    {
        int i=0;
        node *pnode=phead->next;
        while ((i++) < index) 
            pnode = pnode->next;

        return pnode;
    }

    // 反向查找
    int j=0;
    int rindex = count - index - 1;
    node *rnode=phead->prev;
    while ((j++) < rindex) 
        rnode = rnode->prev;

    return rnode;
}

// 获取“第一个节点”
static node* get_first_node() 
{
    return get_node(0);
}

// 获取“最后一个节点”
static node* get_last_node() 
{
    return get_node(count-1);
}

// 获取“双向链表中第index位置的元素”。成功，返回节点值；否则，返回-1。
void* dlink_get(int index)
{
    node *pindex=get_node(index);
    if (!pindex) 
    {
        printf("%s failed!\n", __func__);
        return NULL;
    }

    return pindex->p;

}

// 获取“双向链表中第1个元素的值”
void* dlink_get_first()
{
    return dlink_get(0);
}

// 获取“双向链表中最后1个元素的值”
void* dlink_get_last()
{
    return dlink_get(count-1);
}

// 将“pval”插入到index位置。成功，返回0；否则，返回-1。
int dlink_insert(int index, void* pval) 
{
    // 插入表头
    if (index==0)
        return dlink_insert_first(pval);

    // 获取要插入的位置对应的节点
    node *pindex=get_node(index);
    if (!pindex) 
        return -1;

    // 创建“节点”
    node *pnode=create_node(pval);
    if (!pnode)
        return -1;

    pnode->prev = pindex->prev;
    pnode->next = pindex;
    pindex->prev->next = pnode;
    pindex->prev = pnode;
    // 节点个数+1
    count++;

    return 0;
}

// 将“pval”插入到表头位置
int dlink_insert_first(void *pval) 
{
    node *pnode=create_node(pval);
    if (!pnode)
        return -1;

    pnode->prev = phead;
    pnode->next = phead->next;
    phead->next->prev = pnode;
    phead->next = pnode;
    count++;
    return 0;
}

// 将“pval”插入到末尾位置
int dlink_append_last(void *pval) 
{
    node *pnode=create_node(pval);
    if (!pnode)
        return -1;
    
    pnode->next = phead;
    pnode->prev = phead->prev;
    phead->prev->next = pnode;
    phead->prev = pnode;
    count++;
    return 0;
}

// 删除“双向链表中index位置的节点”。成功，返回0；否则，返回-1。
int dlink_delete(int index)
{
    node *pindex=get_node(index);
    if (!pindex) 
    {
        printf("%s failed! the index in out of bound!\n", __func__);
        return -1;
    }

    pindex->next->prev = pindex->prev;
    pindex->prev->next = pindex->next;
    free(pindex);
    count--;

    return 0;
}    

// 删除第一个节点
int dlink_delete_first() 
{
    return dlink_delete(0);
}

// 删除组后一个节点
int dlink_delete_last() 
{
    return dlink_delete(count-1);
}

// 撤销“双向链表”。成功，返回0；否则，返回-1。
int destroy_dlink()
{
    if (!phead)
    {
        printf("%s failed! dlink is null!\n", __func__);
        return -1;
    }

    node *pnode=phead->next;
    node *ptmp=NULL;
    while(pnode != phead)
    {
        ptmp = pnode;
        pnode = pnode->next;
        free(ptmp);
    }

    free(phead);
    phead = NULL;
    count = 0;

    return 0;
}

双向链表的测试程序(dlink_stack.c)

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
#include <stdio.h>
#include "double_link.h"

/**
 * C 语言: 双向链表实现栈，能存储任意数据。
 *
 * @author skywang
 * @date 2013/11/07
 */
// 创建栈
int create_dlink_stack() 
{
    return create_dlink();
}

// 销毁栈
int destroy_dlink_stack() 
{
    return destroy_dlink();
}

// 将val添加到栈中
int push(void *p) 
{
    return dlink_insert_first(p);
}

// 返回“栈顶元素值”
void* peek() 
{
    return dlink_get_first();
}

// 返回“栈顶元素值”，并删除“栈顶元素”
void* pop() 
{
    void *p = peek();
    dlink_delete_first();
    return p;
}

// 返回“栈”的大小
int size() 
{
    return dlink_size();
}

// 返回“栈”是否为空
int is_empty()
{
    return dlink_is_empty();
}


typedef struct tag_stu
{
    int id;
    char name[20];
}stu;

static stu arr_stu[] = 
{
    {10, "sky"},
    {20, "jody"},
    {30, "vic"},
    {40, "dan"},
};
#define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )

static void print_stu(stu *p) 
{
    if (!p)
        return ;

    printf("id=%d, name=%s\n", p->id, p->name);
}

void main()
{
    stu *pval=NULL;

    // 创建“栈”
    create_dlink_stack();

    // 将10, 20, 30 依次推入栈中
    int i=0;
    for (i=0; i<ARR_STU_SIZE-1; i++)
    {
        push(&arr_stu[i]);
    }

    // 将“栈顶元素”赋值给pval，并删除“栈顶元素”
    pval = (stu*)pop();
    //print_stu(pval) ;

    // 只将“栈顶”赋值给pval，不删除该元素.
    pval = peek();
    //print_stu(pval) ;

    push(&arr_stu[ARR_STU_SIZE-1]);


    // 打印栈中的所有元素
    while (!is_empty())
    {
        pval = pop();
        print_stu(pval) ;
    }

    // 销毁栈
    destroy_dlink_stack();
}

运行结果：

1
2
3
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
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
#ifndef ARRAY_STACK_HXX
#define ARRAY_STACK_HXX

#include <iostream>
#include "ArrayStack.h"
using namespace std;

template<class T> class ArrayStack{
    public:
        ArrayStack();
        ~ArrayStack();

        void push(T t);
        T peek();
        T pop();
        int size();
        int isEmpty();
    private:
        T *arr;
        int count;
};

// 创建“栈”，默认大小是12
template<class T>
ArrayStack<T>::ArrayStack() 
{
    arr = new T[12];
    if (!arr) 
    {
        cout<<"arr malloc error!"<<endl;
    }
}

// 销毁“栈”
template<class T>
ArrayStack<T>::~ArrayStack() 
{
    if (arr) 
    {
        delete[] arr;
        arr = NULL;
    }
}

// 将val添加到栈中
template<class T>
void ArrayStack<T>::push(T t) 
{
    //arr[count++] = val;
    arr[count++] = t;
}

// 返回“栈顶元素值”
template<class T>
T ArrayStack<T>::peek() 
{
    return arr[count-1];
}

// 返回“栈顶元素值”，并删除“栈顶元素”
template<class T>
T ArrayStack<T>::pop() 
{
    int ret = arr[count-1];
    count--;
    return ret;
}

// 返回“栈”的大小
template<class T>
int ArrayStack<T>::size() 
{
    return count;
}

// 返回“栈”是否为空
template<class T>
int ArrayStack<T>::isEmpty()
{
    return size()==0;
}

#endif

栈的测试程序(Main.cpp)

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
#include <iostream>
#include "ArrayStack.h"
using namespace std;

int main() 
{
    int tmp=0;
    ArrayStack<int> *astack = new ArrayStack<int>();

    cout<<"main"<<endl;

    // 将10, 20, 30 依次推入栈中
    astack->push(10);
    astack->push(20);
    astack->push(30);

    // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
    tmp = astack->pop();
    cout<<"tmp="<<tmp<<endl;

    // 只将“栈顶”赋值给tmp，不删除该元素.
    tmp = astack->peek();

    astack->push(40);

    while (!astack->isEmpty())
    {
        tmp = astack->pop();
        cout<<tmp<<endl;
    }

    return 0;
}

运行结果：

1
2
3
4
5
main
tmp=30
40
20
10

结果说明：关于”栈的声明和实现都在头文件中”的原因，是因为栈的实现利用了C++模板，而”C++编译器不能支持对模板的分离式编译”。这在”数据结构和算法01之 线性表”中已经介绍过了。 程序的实现和逻辑都非常简单。需要说明的是，采用C++模板实现的；但是，默认数组的大小只有12，而且该实现不支持动态扩展。

2. C++实现二：C++的 STL 中自带的”栈”(stack)的示例

实现代码(StlStack.cpp)

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
#include <iostream>
#include <stack>
using namespace std;

/**
 * C++ 语言: STL 自带的“栈”(stack)的示例。
 *
 * @author skywang
 * @date 2013/11/07
 */
int main ()
{
    int tmp=0;
    stack<int> istack;

    // 将10, 20, 30 依次推入栈中
    istack.push(10);
    istack.push(20);
    istack.push(30);

    // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
    istack.pop();

    // 只将“栈顶”赋值给tmp，不删除该元素.
    tmp = istack.top();

    istack.push(40);

    while (!istack.empty())
    {
        tmp = istack.top();
        istack.pop();
        cout<<tmp<<endl;
    }

    return 0;
}

运行结果：

1
2
3
40
20
10

栈的Java实现

和C++一样，JDK包中也提供了”栈”的实现，它就是集合框架中的Stack类。关于Stack类的原理，在”Java 集合系列07之 Stack详细介绍(源码解析)和使用示例”中，已经详细介绍过了。本部分给出2种Java实现

Java实现一：数组实现的栈，能存储任意类型的数据。

Java实现二：Java的 Collection集合 中自带的”栈”(stack)的示例。

1. Java实现一：数组实现的栈，能存储任意类型的数据

实现代码(GeneralArrayStack.java)

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
/**
 * Java : 数组实现的栈，能存储任意类型的数据
 *
 * @author skywang
 * @date 2013/11/07
 */
import java.lang.reflect.Array;

public class GeneralArrayStack<T> {

    private static final int DEFAULT_SIZE = 12;
    private T[] mArray;
    private int count;

    public GeneralArrayStack(Class<T> type) {
        this(type, DEFAULT_SIZE);
    }

    public GeneralArrayStack(Class<T> type, int size) {
        // 不能直接使用mArray = new T[DEFAULT_SIZE];
        mArray = (T[]) Array.newInstance(type, size);
        count = 0;
    }

    // 将val添加到栈中
    public void push(T val) {
        mArray[count++] = val;
    }

    // 返回“栈顶元素值”
    public T peek() {
        return mArray[count-1];
    }

    // 返回“栈顶元素值”，并删除“栈顶元素”
    public T pop() {
        T ret = mArray[count-1];
        count--;
        return ret;
    }

    // 返回“栈”的大小
    public int size() {
        return count;
    }

    // 返回“栈”是否为空
    public boolean isEmpty() {
        return size()==0;
    }

    // 打印“栈”
    public void PrintArrayStack() {
        if (isEmpty()) {
            System.out.printf("stack is Empty\n");
        }

        System.out.printf("stack size()=%d\n", size());

        int i=size()-1;
        while (i>=0) {
            System.out.println(mArray[i]);
            i--;
        }
    }

    public static void main(String[] args) {
        String tmp;
        GeneralArrayStack<String> astack = new GeneralArrayStack<String>(String.class);

        // 将10, 20, 30 依次推入栈中
        astack.push("10");
        astack.push("20");
        astack.push("30");

        // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
        tmp = astack.pop();
        System.out.println("tmp="+tmp);

        // 只将“栈顶”赋值给tmp，不删除该元素.
        tmp = astack.peek();
        System.out.println("tmp="+tmp);

        astack.push("40");
        astack.PrintArrayStack();    // 打印栈
    }
}

运行结果：

1
2
3
4
5
6
tmp=30
tmp=20
stack size()=3
40
20
10

结果说明：GeneralArrayStack是通过数组实现的栈，而且GeneralArrayStack中使用到了泛型。

2. Java实现二：Java的 Collection集合 中自带的”栈”(stack)的示例

实现代码(StackTest.java)

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
import java.util.Stack;

/**
 * Java : java集合包中的Stack的演示程序
 *
 * @author skywang
 * @date 2013/11/07
 */
public class StackTest {

    public static void main(String[] args) {
        int tmp=0;
        Stack<Integer> astack = new Stack<Integer>();

        // 将10, 20, 30 依次推入栈中
        astack.push(10);
        astack.push(20);
        astack.push(30);

        // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
        tmp = astack.pop();
        //System.out.printf("tmp=%d\n", tmp);

        // 只将“栈顶”赋值给tmp，不删除该元素.
        tmp = (int)astack.peek();
        //System.out.printf("tmp=%d\n", tmp);

        astack.push(40);
        while(!astack.empty()) {
            tmp = (int)astack.pop();
            System.out.printf("tmp=%d\n", tmp);
        }
    }
}

运行结果：

1
2
3
tmp=40
tmp=20
tmp=10