C 有标准的队列实现吗？

Question

是否有 C 语言“附带”的任何队列数据结构实现，或者我必须开发自己的队列数据结构实现（这是一个学校项目，因此我必须使用标准 gcc 安装中存在的东西，或者必须自己实现一个） ！）

其他通用数据结构，如链表、堆栈等呢？

Answer 1

试试这个。 Unix 附带了几种链接列表 - 您可以使用其中一种来创建其他可能基于列表的结构，例如堆栈。

man queue

Answer 2

不。但这是一个非常简单的实现：

typedef struct node {
   int val;
   struct node *next;
} node_t;

void enqueue(node_t **head, int val) {
   node_t *new_node = malloc(sizeof(node_t));
   if (!new_node) return;

   new_node->val = val;
   new_node->next = *head;

   *head = new_node;
}

int dequeue(node_t **head) {
   node_t *current, *prev = NULL;
   int retval = -1;

   if (*head == NULL) return -1;

   current = *head;
   while (current->next != NULL) {
      prev = current;
      current = current->next;
   }

   retval = current->val;
   free(current);

   if (prev)
      prev->next = NULL;
   else
      *head = NULL;

   return retval;
}

完整源码这里

Answer 3

您可以使用命名管道。它是一种 FIFO 数据结构，是 posix 标准的一部分。如果您想要的只是在后面排队并从前面删除它就可以了。不过，您需要手动跟踪消息边界，也许可以将第一个元素设置为下一条消息中的字节数。

Answer 4

使用 BSB 库。 sys/queue.h 和 sys/tree.h 有各种列表和树的实现。

Answer 5

您必须实施自己的。 C 在数据结构方面的知识非常少，迫使您采用有争议的技巧来实现抽象数据类型：如果您能找到一篇题为“作为抽象的不完整类型”的文章，或者看看如何应用这些原则，例如， PolarSSL 的 bignum.h 文件。另一方面，C++ 应该允许您完成 C 中可以做的几乎所有事情，并为您提供实现抽象数据结构的方法。

Answer 6

不完全标准，但许多系统都有

bsd/sys/queue.h

和

bsd/sys/tree.h

，它们是基于宏的库。

请参阅此处文档。

Answer 7

GLib（不要与 glibc 混淆）实现了许多常见的数据结构，包括双端队列。与 FreeBSD 基于宏的队列不同，GLib 的 GQueues 基于可能更容易调试和类型检查的函数。

https://developer.gnome.org/glib/stable/glib-Double-ending-Queues.html

Answer 8

据我所知，C 没有默认的结构（即没有默认的链表、堆栈、队列、树等） 必须自己做。

Answer 9

您必须实现自己的数据结构，但是存在许多数据结构库。