基于数组的队列和基于列表的队列的区别

---

介绍

队列是一种线性数据结构，它按照特定的顺序插入和删除队列元素。我们可以使用数组和链表在C++中实现队列。两种队列实现都有其优点和用途。在本教程中，我们将区分基于数组的队列和基于列表的队列。

什么是队列？

队列是一系列元素，它使用FIFO（先进先出）原则来插入和删除其元素。计算机科学中的队列类似于现实生活中的队列，先进入队列的人将先被移除。

删除队列数据的过程称为出队（deQueue）。向队列中添加数据的操作称为入队（enQueue）。

队列有两个指针：

• 尾部 (Rear) − 元素从这里插入队列。

• 头部 (Front) − 元素从这里删除队列。

我们可以使用两种方法实现队列：

• 基于数组的队列

• 基于列表的队列或链表队列

基于数组的队列

使用数组实现的队列称为基于数组的队列。它使用两个指针：头部(Front)和尾部(Rear)，分别表示队列中的删除和插入点。

在此实现中，数组大小在插入数据之前预先定义。这是插入和删除队列数据的最简单方法。

基于列表的队列

在基于列表的队列或基于链表的队列中，使用链表来实现队列。每个队列节点包含两部分：一部分用于存储数据，另一部分是链接部分或内存部分。

每个队列元素都连接到下一个队列元素的内存。在基于列表的队列中，有两个指针：

• 头部指针 (Front pointer) − 表示最后一个队列元素的内存。

• 尾部指针 (Rear pointer) − 表示第一个队列元素的内存。

基于数组的队列和基于列表的队列的区别

序号		基于数组的队列	基于链表的队列
1	复杂度	易于实现和执行操作。	不易于实现。
2	搜索过程	有助于轻松快速地搜索。	速度慢，搜索操作困难。
3	队列大小	在初始化时定义队列大小。	无需在队列初始化时定义队列大小。
4	插入和删除操作	在队列开头插入数据困难，在队列末尾插入数据容易。	它允许在队列的两端轻松插入数据。
5	访问数据	随机访问数据。	它提供对队列元素的顺序访问。
6	队列大小调整	很难更改队列大小。	易于调整队列大小。
7	内存使用	它消耗更少的内存。	它消耗更多内存。
8	优点	它更快，更容易实现。 它消耗更少的内存。 随机访问元素。	队列元素的插入和删除很容易。 易于调整队列大小，无需预先声明队列大小。
9	缺点	队列大小调整很困难。 需要预先声明队列大小。	处理速度慢。 它具有复杂的结构，并消耗更多内存。

基于数组的队列和基于列表的队列的用途

如果你的队列大小固定且不需要更改队列大小，则可以使用数组来实现队列。如果需要快速搜索且内存消耗较少，基于数组的队列也很有用。

当队列大小是动态的，并且队列元素被多次插入和删除时，基于链表的队列实现非常有用。尽管它消耗更多内存，但它用于大型应用程序。

结论

基于数组的队列和基于链表的队列的使用取决于需求。在大规模应用中，基于数组的队列是不成功的，而链表队列被使用。

基于数组的队列使用较少的内存，但是它会浪费大量的内存，因为在尾部插入元素后，第一个元素之前会留下一些未使用的内存。