我想使用动态分配的数组实现队列。这提出了一些我不确定如何处理的问题。如何检查队列是否为空？如何在一个瞬间跟踪队列中有多少元素？
对于第二个问题，我想我可以创建一个变量来跟踪队列中的元素数量，这些元素在我使用realloc()的任何时候都会更新。不过我欢迎其他建议。
如果你有任何更多的考虑我应该考虑请呈现它们。
这是一个相当简单的基于数组的FIFO队列：
struct queue {
T *store; // where T is the data type you're working with
size_t size; // the physical array size
size_t count; // number of items in queue
size_t head; // location to pop from
size_t tail; // location to push to
};
struct queue q;
q.store = malloc( sizeof *q.store * SIZE );
if ( q.store )
{
q.size = SIZE;
q.count = q.head = q.tail = 0;
}
要推送项目，请执行以下操作：
int push( struct queue q, T new_value )
{
if ( q.count == q.size )
{
// queue full, handle as appropriate
return 0;
}
else
{
q.store[q.tail] = new_value;
q.count++;
q.tail = ( q.tail + 1 ) % q.size;
}
return 1;
}
流行音乐是相似的
int pop( struct queue q, T *value )
{
if ( q.count == 0 )
{
// queue is empty, handle as appropriate
return 0;
}
else
{
*value = q.store[q.head];
q.count--;
q.head = ( queue.head + 1 ) % q.size;
}
return 1;
}
如上所述，这是一个“循环”队列;当从队列中推送和弹出项目时，head和tail指针将会回绕。
与任何方法一样，这有优点和缺点。它很简单，它避免了过多的内存管理（只是分配后备存储）。只是更新count比尝试从head和tail计算它更简单。
扩展后备存储并不是那么简单;如果你的尾指针已经缠绕，你将不得不在head之后移动一切：
Before:
+---+---+---+---+---+
| x | x | x | x | x |
+---+---+---+---+---+
^ ^
| |
| +--- head
+------- tail
After:
+---+---+---+---+---+---+---+---+---+---+
| x | x | x | | | | | | x | x |
+---+---+---+---+---+---+---+---+---+---+
^ ^
| |
| +--- head
+------- tail
此外，如果您想要比简单FIFO更复杂的东西，您可能希望使用不同的数据结构作为后备存储。
通常，您将指针变量保留到队列的“头部”。当此指针为空时，列表为空，如果不为，则指向第一个节点。
现在，当谈到给定时间内队列中的元素数量时，您建议的另一个解决方案是实际运行所有节点并计数，但是根据元素的数量，这可能非常慢。
为了计数，只需保留已插入的元素数量的引用计数
INSERT () {
//code to insert element
size++;
}
POP(){
//code to remove element
size--;
}
SIZE(){
return size;
}
接下来，您将不得不决定使用哪种策略来插入元素。
大多数人只使用一个列表。而且由于队列通常是FILO（先进先出）或LILO（最后输出），因此可能会有点棘手。
列表就是这样
struct Node{
T* Value;
ptr Next;
}
你有一堆这些按顺序创建一个列表。每个插入都会生成一个新节点，删除将取出节点并重新附加列表。
如果你正在使用realloc，地址可以改变，所以你需要你的next，prev，head和tail使用索引。
使用固定大小的数组，您可以使用旋转缓冲区，只需保持偏移量和大小以及值数组，只要值保持不变，就不需要节点结构，只要值是常量。
对于动态大小，你可以弹出交换被删除的那个与最后一个。但是，这需要为每个节点存储前一个和下一个。您需要存储前一个，就像在最后交换节点时需要更新其父节点中的位置（下一个）。基本上你最终得到一个双向链表。
这样做的一个好处是，您可以使用一个阵列来实现多个链接列表。但是，这对于线程应用程序并不好，因为您将在单个资源上进行全局争用。
标准方法是使用malloc和free per节点。除了更多的内存管理之外，其他影响没有太大差异。您只需要存储每个节点下一个地址。您也可以使用指针而不是索引。对于许多可能永远不会发生或几乎不会发生的用例，破坏队列是O（N）。
malloc与realloc的性能特征可能因许多因素而异。这是要记住的事情。
根据经验，realloc很好，当它自然取代b = malloc(size + amount);memcopy(a, b, size);free(a);a = b;和a = realloc(a, size + amount);这样的东西时，如果你不得不做一些奇怪的事情来重新分配工作那么它可能是错误的构想。 Realloc应该解决你的问题。如果你的问题解决了realloc，那么realloc可能是你的问题。如果你使用realloc来替换与realloc相同的代码那么这很好，但另外问问自己是否必须弯曲代码以使其与realloc一起工作，如果这真的是最简单的事情可能有用，如果你'使用realloc来执行realloc的意图。也就是说，如果你用更少或更少的东西来替换它来使它工作那么它可能是好的但是如果你用更少的替换或者需要更多来使它工作那么它可能是坏的。简而言之，保持简单。你会注意到realloc的实现意味着更多的跳跃，所以它可能是错误的构思。
数据结构示例......
假设int是uint。
会员指的是您实际存储的内容。在此示例中使用void指针，以便它可以容纳任何类型。但是，如果它总是相同的话，您可以将其更改为类型指针或甚至类型本身。
当分配的内存量可能大于用于存储项目的量时，使用空间。
循环静态队列：
struct queue {
void* members[SPACE];
int offset;
int size;
};
成员可以包含任意类型的不同长度的指针类型。你可以有偏移，大小而不是头部，尾部。
循环动态初始大小：
struct queue {
void* members[];
int offset;
int size;
int space;
};
也可以询问指针有多少内存而不是存储空间。
尾部偏移+大小 - 1.您需要使用空间模数来获得真实的偏移。
创建后可以更改空间或将其用作向量。然而，调整大小操作可能非常昂贵，因为您可能必须移动多个元素使其O（N）而不是O（1）移位和推动。
Realloc矢量队列：
struct queue {
node* nodes;
int head;
int tail;
int size;
};
struct node {
void* member;
int next;
int prev;
};
Malloc节点队列：
struct queue {
void* head;
node* head;
node* tail;
};
struct node {
void* member;
node* next;
};