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

转自：http://www.cnblogs.com/skywang12345/p/3562279.html

概要

本章和介绍"栈"时的流程一样，先对队列进行介绍，然后分别给出队列的C、C++和Java三种语言的实现。内容包括：
1. 队列的介绍
2. 队列的C实现
3. 队列的C++实现
4. 队列的Java实现

转载请注明出处：http://www.cnblogs.com/skywang12345/p/3562279.html

队列的介绍

队列（Queue），是一种线性存储结构。它有以下几个特点：
(01) 队列中数据是按照"先进先出（FIFO, First-In-First-Out）"方式进出队列的。
(02) 队列只允许在"队首"进行删除操作，而在"队尾"进行插入操作。
队列通常包括的两种操作：入队列和出队列。

1. 队列的示意图

队列中有10，20，30共3个数据。

2. 出队列

出队列前：队首是10，队尾是30。
出队列后：出队列(队首)之后。队首是20，队尾是30。

3. 入队列

入队列前：队首是20，队尾是30。
入队列后：40入队列(队尾)之后。队首是20，队尾是40。

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

队列的C实现

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

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

实现代码(array_queue.c)

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

运行结果：

tmp=10
tmp=20
is_empty()=0
size()=3
20
30
40

结果说明：该示例中的队列，是通过"数组"来实现的！
由于代码中已经给出了详细了注释，这里就不再对函数进行说明了。仅对主函数main的逻辑进行简单介绍。
(01) 在主函数main中，先将 "10, 20, 30"依次入队列。此时，队列的数据是： 10 --> 20 --> 30
(02) 接着通过pop()返回队首元素；pop()操作并不会改变队列中的数据。此时，队列的数据依然是： 10 --> 20 --> 30
(03) 接着通过front()返回并删除队首元素。front()操作之后，队列的数据是： 10 --> 30
(04) 接着通过add(40)将40入队列。add(40)操作之后，队列中的数据是： 10 --> 20 --> 40

2. C语言实现二：单向链表实现的队列，并且只能存储int数据

实现代码(slink_queue.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_queue.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_queue.c)

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

运行结果：

id=10, name=sky
id=20, name=jody
is_empty()=0
size()=3
id=20, name=jody
id=30, name=vic
id=40, name=dan

结果说明：该示例中的队列是通过双向链表实现的，并且能存储任意类型的数据。

队列的C++实现

C++的STL中本身就包含了list类，基本上该list类就能满足我们的需求，所以很少需要我们自己来实现。本部分介绍2种C++实现。
1. C++实现一：数组实现的队列，能存储任意类型的数据。
2. C++实现二：C++的 STL 中自带的"队列"(list)的示例。

1. C++实现一：数组实现的队列，能存储任意类型的数据

实现代码
队列的实现文件(ArrayQueue.h)

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

队列的测试程序(Main.cpp)

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

运行结果：

tmp=10
tmp=20
is_empty()=0
size()=3
20
30
40

结果说明：关于"队列的声明和实现都在头文件中"的原因，是因为队列的实现利用了C++模板，而"C++编译器不能支持对模板的分离式编译"。

2. C++实现二：C++的 STL 中自带的"队列"(list)的示例

实现代码(StlQueue.cpp)

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

运行结果：

tmp=20
empty()=0
size()=3
20
30
40

队列的Java实现

和C++一样，JDK包Queue中的也提供了"队列"的实现。JDK中的Queue接口就是"队列"，它的实现类也都是队列，用的最多的是LinkedList。本部分介绍给出2种Java实现
1. Java实现一：数组实现的队列，能存储任意类型的数据。
2. Java实现二：Java的 Collection集合中自带的"队列"(LinkedList)的示例。

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

实现代码(ArrayQueue.java)

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

运行结果：

tmp=10
tmp=20
isEmpty()=false
size()=3
size()=20
size()=30
size()=40

结果说明：ArrayQueue是通过数组实现的队列，而且ArrayQueue中使用到了泛型，因此它支持任意类型的数据。

2. Java实现二：Java的 Collection集合中自带的"队列"(LinkedList)的示例

实现代码(QueueTest.java)

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

运行结果：

tmp=10
tmp=20
isEmpty()=false
size()=3
tmp=20
tmp=30
tmp=40

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

概要

队列的介绍

队列的C实现

队列的C++实现

队列的Java实现

相关推荐

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