栈的图解和实现(C/C++/Java)

本章会先对栈的原理进行介绍,然后分别通过C/C++/Java三种语言来演示栈的实现。

栈的介绍

栈(stack),是一种线性存储结构,它有以下几个特点:

  • 栈中数据是按照"后进先出(LIFO, Last In First Out)"方式进出栈的。
  • 向栈中添加/删除数据时,只能从栈顶进行操作。

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

1. 栈的示意图

img

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

2. 出栈

示意图如下:

img

出栈前:栈顶元素是30。此时,栈中的元素依次是 30 --> 20 --> 10

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

3. 入栈

示意图如下:

img

入栈前:栈顶元素是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语言实现四:双向链表实现的栈,能存储任意类型的数据。

栈的C++实现

本部分介绍2种C++实现的栈。

  1. C++实现一:数组实现的栈,能存储任意类型的数据。
  2. C++实现二:C++的 STL 中自带的"栈"(stack)的示例。

PS. C++的STL中本身就包含了stack类,基本上该stack类就能满足我们的需求,所以很少需要我们自己来实现。

栈的Java实现

本部分介绍给出2种Java实现的栈。

  1. Java实现一:数组实现的栈,能存储任意类型的数据。
  2. Java实现二:Java的 Collection集合 中自带的"栈"(stack)的示例。

PS. 和C++一样,JDK包中也提供了"栈"的实现,它就是集合框架中的Stack类。

by skywang
Previous     Next