您的位置: 首页  >  文章  >  栈的图文解析 和 对应3种语言的实现(C/C++/Java)

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

分类: 文章 • 2025-02-24 16:18:22

栈的介绍

栈（stack），是一种线性存储结构，它有以下几个特点：
(01) 栈中数据是按照"后进先出（LIFO, Last In First Out）"方式进出栈的。
(02) 向栈中添加/删除数据时，只能从栈顶进行操作。

栈通常包括的三种操作：push、peek、pop。
push -- 向栈中添加元素。
peek -- 返回栈顶元素。
pop  -- 返回并删除栈顶元素的操作。

 

1. 栈的示意图

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

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

 

2. 出栈

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

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

 

3. 入栈

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

入栈前：栈顶元素是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)

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

运行结果：

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)

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

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

 

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

实现代码
双向链表的头文件(double_link.h)

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

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

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

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

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

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

 

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

实现代码
双向链表的头文件(double_link.h)

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

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

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

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

栈的图文解析 和 对应3种语言的实现(C/C++/Java) 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)

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

栈的测试程序(Main.cpp)

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

运行结果：

main
tmp=30
40
20
10

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

 

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

实现代码(StlStack.cpp)

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

运行结果：

40
20
10

 

栈的Java实现

和C++一样，JDK包中也提供了"栈"的实现，它就是集合框架中的Stack类。关于Stack类的原理，在"Java 集合系列07之 Stack详细介绍(源码解析)和使用示例"中，已经详细介绍过了。本部分给出2种Java实现
Java实现一：数组实现的栈，能存储任意类型的数据。
Java实现二：Java的 Collection集合 中自带的"栈"(stack)的示例。

 

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

实现代码(GeneralArrayStack.java)

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

运行结果：

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

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

 

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

实现代码(StackTest.java)

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

运行结果：

tmp=40
tmp=20
tmp=10

如果你对编程感兴趣或者想往编程方向发展，可以关注微信公众号【筑梦编程】，大家一起交流讨论！小编也会每天定时更新既有趣又有用的编程知识！
 

相关推荐