c - 队列的实现（fifo）

Question

我的任务是用 c 语言实现一个没有任何循环和任何递归的动态队列。队列应该包含下一个函数：安装、破坏、添加、删除和查看。我想制作一个链接结构，这样每个链接都会有一个指向下一个链接的指针，依此类推..但问题是我不知道如何在没有任何循环的情况下执行 destruct 函数，这是我能想到的唯一解决方案of 正在制作一个循环，将每个链接发送到删除函数（但同样，我需要它没有任何循环）。他们是否有可能在没有任何循环的情况下执行破坏功能？

ps destruct 函数应该释放我们用于队列的所有内存。

Answer 1

如果递归函数不算作约束的循环，则可以使用递归遍历列表并销毁项目。

另一种方法是将项目存储在一个数组中，并为队列的头部和尾部维护一个指向数组的指针。销毁队列只意味着释放数组或重置头/尾指针，不需要循环。

Answer 2

没有真正需要基于链表创建队列，它具有随机分配元素和缺乏空间局部性的所有缺点，调试起来相对困难，并且不会使用链表的主要优点（在 O(1) 处插入），因为它是一个只有一个插入点的队列（或者 2 个用于双端插入点）。

相反，您可以使用一个数组，并维护一个头和尾索引变量，在它们最后回绕时使用循环增量，并在需要时重新分配。如果队列包含基本数据类型，这也将允许您一次性释放整个队列，只需释放数组（尽管对于您必须手动分配的元素，我看不到任何避免迭代删除的方法，除非您移动到 c++)。

Answer 3

我假设要插入内存的项目的大小是恒定的。如果需要，它可以是指向内存块的指针。在这种情况下，您可以使用带有头尾指针的循环缓冲区。当任一指针“到达块的末尾”时，它应该换行 - 即您递增/递减modulo queue size。

初始化：

Create a memory space of finite size (max size of the buffer)

添加：

Update memory location at the current tail (if add to end) 
or head (if add to beginning), and update the tail/head pointer.

消除：

Read the data at the head/tail, and update the pointer

窥视：

Read the data at the head/tail, and don't move the pointer

破坏：

Free the memory block

没有循环，没有递归。它使用FIFO缓冲区仅允许在队列的开头/结尾进行更改的事实 - 无法删除“中间”的元素。

如果头和尾指针相遇，则队列“满”。在这种情况下，“插入”函数应该返回一个错误，除非您添加一个“破坏性插入”标志，表示“覆盖最旧的元素”。这似乎超出了您的家庭作业范围，但它在现实生活中的应用中很重要。有时您关心最旧的数据 - 有时您关心最新的数据。但是通常，如果您的队列正在填满，那么整个系统设计就会出现问题（基本上，您没有扩展清空队列的过程来处理它的填充速率）。

注意 - 如果队列中的每个元素都是指向动态分配内存的指针，您将需要遍历所有元素以释放该内存，否则您将创建内存泄漏。但是，如果队列的大小是恒定的，则不需要这样做。鉴于给定的约束，并且缺乏队列元素大小应该可变的规范，我建议您为固定大小的队列元素编写解决方案。