使用数组实现队列

我们可以通过使用线性数组轻松地表示队列。队列的实现中有两个变量，即 front 和 rear。Front 和 rear 变量指向在队列中执行插入和删除的位置。最初，front 和 queue 的值为 -1，表示一个空队列。下面图示了包含 5 个元素的队列的数组表示以及 front 和 rear 的相应值。

上图显示了组成英文单词“HELLO”的字符队列。由于到目前为止还没有执行删除操作，因此 front 的值保持为 -1。但是，每次在队列中执行插入操作时，rear 的值都会增加。在将元素插入上图所示的队列后，队列将如下所示。rear 的值将变为 5，而 front 的值保持不变。

删除元素后，front 的值将从 -1 增加到 0。但是，队列将如下所示。

向队列中插入任何元素的算法

通过将 rear 与 max - 1 进行比较来检查队列是否已满。如果是，则返回溢出错误。

如果元素是要插入列表中的第一个元素，则将 front 和 rear 的值设置为 0，并将元素插入到 rear 端。

否则，不断增加 rear 的值，并逐个插入元素，以 rear 作为索引。

算法

• 步骤 1: 如果 REAR = MAX - 1
  输出 OVERFLOW
  转到步骤
  [IF 结束]
• 步骤 2: 如果 FRONT = -1 且 REAR = -1
  设置 FRONT = REAR = 0
  否则
  设置 REAR = REAR + 1
  [IF 结束]
• 步骤 3: 设置 QUEUE[REAR] = NUM
• 步骤 4: 退出

C 函数

从队列中删除元素的算法

如果 front 的值是 -1 或 front 的值大于 rear，则输出 underflow 消息并退出。

否则，不断增加 front 的值，并在每次返回队列 front 端存储的项。

算法

• 步骤 1: 如果 FRONT = -1 或 FRONT > REAR
  输出 UNDERFLOW
  否则
  设置 VAL = QUEUE[FRONT]
  设置 FRONT = FRONT + 1
  [IF 结束]
• 步骤 2: 退出

C 函数

使用数组实现队列的菜单驱动程序

输出

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
123

Value inserted 

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
90

Value inserted 

*************Main Menu**************

===================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

value deleted 

*************Main Menu**************
==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

90

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?4

数组实现的缺点

虽然创建队列的技术很简单，但使用这种技术实现队列存在一些缺点。

• 内存浪费：用于存储队列元素的数组空间永远不能重复用于存储该队列的元素，因为元素只能在 front 端插入，而 front 的值可能很高，以至于它之前的所有空间都永远无法填充。

上图显示了队列的数组表示中内存空间是如何浪费的。在上图中，显示了一个大小为 10、包含 3 个元素的队列。front 变量的值是 5，因此我们无法在 front 位置之前的已删除元素的位置重新插入值。如此多的数组空间被浪费了，并且将来（对于此队列）无法使用。

• 确定数组大小

数组实现中最常见的问题之一是需要提前声明数组的大小。由于队列可以根据问题在运行时扩展，因此扩展数组大小是一个耗时的过程，并且在运行时几乎不可能执行，因为会进行大量的重新分配。因此，我们可以将数组声明得足够大，以便尽可能多地存储队列元素，但这种声明的主要问题是，大部分数组槽（近一半）永远无法重复使用。这同样会导致内存浪费。