C语言 在 C 中使用结构创建队列

Creating a queue with structs in C

提问by Renato Tavares

I have a code (at the end of this post) that implements a circular queue system. Everything works perfectly, but as can be seen in the function createQueuethe queue is implemented only for integers. I would like to modify this code to accept a struct informed by the user.

我有一个实现循环队列系统的代码（在本文末尾）。一切都完美无缺，但从函数中可以看出，createQueue队列仅针对整数实现。我想修改此代码以接受用户通知的结构。

I could create a known struct and replace all sites with integer, but this way I would be coupling the code to a known struct. Bad idea...

我可以创建一个已知的结构并用整数替换所有站点，但这样我会将代码耦合到一个已知的结构。馊主意...

How could pass to the function createQueuea struct for memory allocation without needing to know the struct previously? The struct Queue should also be changed, in int *elementsthe value should be changed from integer to void?

如何将createQueue用于内存分配的结构传递给函数而无需事先知道该结构？struct Queue 也应该更改，在int *elements 中，值应该从 integer 更改为 void？

#include <stdio.h>
#include <stdlib.h>

typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        int *elements;
}Queue;

Queue * createQueue(int maxElements)
{
        /* Create a Queue */
        Queue *Q;
        Q = (Queue *)malloc(sizeof(Queue));
        /* Initialise its properties */
        Q->elements = (int *)malloc(sizeof(int)*maxElements);
        Q->size = 0;
        Q->capacity = maxElements;
        Q->front = 0;
        Q->rear = -1;
        /* Return the pointer */
        return Q;
}
void Dequeue(Queue *Q)
{
        /* If Queue size is zero then it is empty. So we cannot pop */
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                return;
        }
        /* Removing an element is equivalent to incrementing index of front by one */
        else
        {
                Q->size--;
                Q->front++;
                /* As we fill elements in circular fashion */
                if(Q->front==Q->capacity)
                {
                        Q->front=0;
                }
        }
        return;
}
int front(Queue *Q)
{
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                exit(0);
        }
        /* Return the element which is at the front*/
        return Q->elements[Q->front];
}
void Enqueue(Queue *Q,int element)
{
        /* If the Queue is full, we cannot push an element into it as there is no space for it.*/
        if(Q->size == Q->capacity)
        {
                printf("Queue is Full\n");
        }
        else
        {
                Q->size++;
                Q->rear = Q->rear + 1;
                /* As we fill the queue in circular fashion */
                if(Q->rear == Q->capacity)
                {
                        Q->rear = 0;
                }
                /* Insert the element in its rear side */ 
                Q->elements[Q->rear] = element;
        }
        return;
}
int main()
{
        Queue *Q = createQueue(5);
        Enqueue(Q,1);
        Enqueue(Q,2);
        Enqueue(Q,3);
        Enqueue(Q,4);
        printf("Front element is %d\n",front(Q));
        Enqueue(Q,5);
        Dequeue(Q);
        Enqueue(Q,6);
        printf("Front element is %d\n",front(Q));
}

回答by Jean-Fran?ois Fabre

Even if you aren't good friends with C++, you can create a pseudo-template:

即使你不是 C++ 的好朋友，你也可以创建一个伪模板：

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_TEMPLATE(ELTTYPE) \
typedef struct \
{\
        int capacity;\
        int size;\
        int front;\
        int rear;\
        ELTTYPE *elements;\
}Queue_##ELTTYPE;\
\
Queue_##ELTTYPE * createQueue_##ELTTYPE(int maxElements)\
{\
        /* Create a Queue */\
        Queue_##ELTTYPE *Q;\
        Q = (Queue_##ELTTYPE *)malloc(sizeof(Queue_##ELTTYPE));\
        /* Initialise its properties */\
        Q->elements = malloc(sizeof(ELTTYPE)*maxElements);\
        Q->size = 0;\
        Q->capacity = maxElements;\
        Q->front = 0;\
        Q->rear = -1;\
        /* Return the pointer */\
        return Q;\
}\
void Dequeue_##ELTTYPE(Queue_##ELTTYPE *Q)\
{\
        /* If Queue size is zero then it is empty. So we cannot pop */\
        if(Q->size==0)\
        {\
                printf("Queue is Empty\n");\
                return;\
        }\
        /* Removing an element is equivalent to incrementing index of front by one */\
        else\
        {\
                Q->size--;\
                Q->front++;\
                /* As we fill elements in circular fashion */\
                if(Q->front==Q->capacity)\
                {\
                        Q->front=0;\
                }\
        }\
        return;\
}\
ELTTYPE front_##ELTTYPE(Queue_##ELTTYPE *Q)\
{\
        if(Q->size==0)\
        {\
                printf("Queue is Empty\n");\
                exit(0);\
        }\
        /* Return the element which is at the front*/\
        return Q->elements[Q->front];\
}\
void Enqueue_##ELTTYPE(Queue_##ELTTYPE *Q,ELTTYPE element)\
{\
        /* If the Queue is full, we cannot push an element into it as there is no space for it.*/\
        if(Q->size == Q->capacity)\
        {\
                printf("Queue is Full\n");\
        }\
        else\
        {\
                Q->size++;\
                Q->rear++;\
                /* As we fill the queue in circular fashion */\
                if(Q->rear == Q->capacity)\
                {\
                        Q->rear = 0;\
                }\
                /* Insert the element in its rear side */ \
                Q->elements[Q->rear] = element;\
        }\
        return;\
}

QUEUE_TEMPLATE(int);
QUEUE_TEMPLATE(float);

int main()
{
        Queue_int *Q = createQueue_int(5);
        Queue_float *QF = createQueue_float(5);
        Enqueue_int(Q,1);
        Enqueue_int(Q,2);
        Enqueue_int(Q,3);
        Enqueue_int(Q,4);
        printf("Front element is %d\n",front_int(Q));
        Enqueue_int(Q,5);
        Dequeue_int(Q);
        Enqueue_int(Q,6);
        printf("Front element is %d\n",front_int(Q));

        Enqueue_float(QF,1);
        Enqueue_float(QF,2);
        Enqueue_float(QF,3);
        Enqueue_float(QF,4);
        printf("Front element is %f\n",front_float(QF));
        Enqueue_float(QF,5);
        Dequeue_float(QF);
        Enqueue_float(QF,6);
        printf("Front element is %f\n",front_float(QF));
}

I have added 2 instanciations with 2 different types. Output is:

我添加了 2 个具有 2 种不同类型的实例。输出是：

Front element is 1
Front element is 2
Front element is 1.000000
Front element is 2.000000

Drawback of this method: compilation errors on the macro code may be painful to track down. You could create the code with a known type, debug/improve it, and then use a sedfilter to generate the macro code, replacing the type by ELTTYPEand adding the #defineand the trailing backslashes

这种方法的缺点：宏代码上的编译错误可能很难追踪。您可以使用已知类型创建代码，调试/改进它，然后使用sed过滤器生成宏代码，替换类型ELTTYPE并添加#define和尾随反斜杠

回答by John Bode

How much paindo you enjoy?

你享受多少痛苦？

Jean-Fran?ois Fabre's method is a good one, and is a fair approximation of using C++ templates. I have another one that avoids using the preprocessor, but it's a lotmore work, and is a poor-to-middling approximation of subclassing. I prefer this method to the preprocessor approach, though, mainly because I'm brain-damaged.

Jean-Fran?ois Fabre 的方法很好，并且是使用 C++ 模板的近似方法。我有另外一个使用预处理避免了，但它是一个很大更多的工作，并且是一个贫穷到中等近似子类的。不过，我更喜欢这种方法而不是预处理器方法，主要是因为我脑部受损。

We start with your basic Queuetype, but instead of storing an array of int, store an array of void *:

我们从您的基本Queue类型开始，但不是存储 的数组，而是int存储 的数组void *：

typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        void **elements; 
        ...
}Queue;

meaning that your Enqueueprototype is going to look like

这意味着你的Enqueue原型看起来像

void Enqueue( Queue *Q, void *element )

Now, as soon as we use void *, we have problems- we've thrown type safety out the window, andwe don't really know what the pointed-to data is supposed to look like. Secondly, we have to create a copyof whatever input data we get (we can't just write elementto the elementslist). We also can't use a void *to store scalars like intor floatvalues. So we need to add at least the following type-aware helper functions:

现在，只要我们使用void *，我们有问题-我们已经抛出类型安全窗外，而我们真的不知道什么指向的数据是应该的样子。其次，我们必须创建一个副本的任何输入数据，我们得到（我们不能只是写element在elements清单）。我们也不能使用 avoid *来存储标量int或float值。所以我们至少需要添加以下类型感知辅助函数：

• copy- allocates and assigns a copy of the input to Enqueue
• destroy- destroys an object removed from the queue

• copy- 为 Enqueue 分配和分配输入的副本
• destroy- 销毁从队列中移除的对象

So we add these functions to our Queuetype as follows:

所以我们将这些函数添加到我们的Queue类型中，如下所示：

typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        void *elements;
        void *(*copy)(const void *);
        void (*destroy)(const void *);
}Queue;

So, let's say we want to create a queue to store floats. We create the following helper functions:

因此，假设我们要创建一个队列来存储floats。我们创建以下辅助函数：

void *copyFloat( const void *f )
{
  float *p = malloc( sizeof *p );
  if ( p )
  {
    *p = *(float *) f;
  }
  return p;
}

void destroyFloat( const void *f )
{
  free( f );
}

and then create a new Queueobject that uses them:

然后创建一个Queue使用它们的新对象：

Queue * createQueue(int maxElements, 
                    void *(*copy)(const void *), 
                    void (*destroy)(const void *),
{
  /* Create a Queue */
  Queue *Q;
  Q = malloc( sizeof *Q );
  /* Initialise its properties */
  Q->elements = malloc(sizeof *Q->elements * maxElements);
  Q->size = 0;
  Q->capacity = maxElements;
  Q->front = 0;
  Q->rear = -1;

  Q->copy = copy;
  Q->destroy = destroy;

  /* Return the pointer */
  return Q;
}
...
Queue *floatQueue = CreateQueue( 100, copyFloat, destroyFloat );

Your Enqueuefunction now looks like

你的Enqueue函数现在看起来像

void Enqueue(Queue *Q, void *element)
{
  /* If the Queue is full, we cannot push an element into it as there is no space for it.*/
  if(Q->size == Q->capacity)
  {
    printf("Queue is Full\n");
  }
  else
  {
    Q->size++;
    Q->rear = Q->rear + 1;
    /* As we fill the queue in circular fashion */
    if(Q->rear == Q->capacity)
    {
      Q->rear = 0;
    }
    /* Insert the element in its rear side */ 
    Q->elements[Q->rear] = Q->copy( element ); // <--- create a copy of the input
  }
  return;
}

Why do we need to create the copy? Imagine if you called Enqueuelike the following:

为什么我们需要创建副本？想象一下，如果你Enqueue像下面这样调用：

float f;
...
f = get_new_value();
Enqueue( &queue, &f );

If we just copied the input parameter elementto the queue, we'd be writing the same address to every element of the queue - the address of the variable f. Thus, every element of the queue would be pointing to the same (invalid) thing.

如果我们只是将输入参数复制element到队列中，我们将向队列的每个元素写入相同的地址 - 变量的地址f。因此，队列的每个元素都将指向相同（无效）的事物。

Conversely, when we dequeue an object, we now have to make sure we clean up that memory:

相反，当我们出列一个对象时，我们现在必须确保清理内存：

void Dequeue(Queue *Q)
{
  /* If Queue size is zero then it is empty. So we cannot pop */
  if(Q->size==0)
  {
    printf("Queue is Empty\n");
    return;
  }
  /* Removing an element is equivalent to incrementing index of front by one */
  else
  {
    Q->destroy( Q->elements[Q->front] ); // deallocate the dequeued object
    Q->size--;
    Q->front++;
    /* As we fill elements in circular fashion */
    if(Q->front==Q->capacity)
    {
      Q->front=0;
    }
  }
  return;
}

And your frontfunction now returns a void *:

你的front函数现在返回一个void *：

void *front(Queue *Q)
{
  if(Q->size==0)
  {
    printf("Queue is Empty\n");
    exit(0);
  }
  /* Return the element which is at the front*/
  return Q->elements[Q->front];
}

We're not done yet - to make this work, we stillneed a type-aware front end:

我们还没有完成 - 为了完成这项工作，我们仍然需要一个类型感知前端：

void EnqueueFloat( Queue *floatQueue, float f )
{
  Enqueue( floatQueue, &f );
}

float frontFloat( Queue *floatQueue )
{
  float *p = front( floatQueue );
  return *p;
}

What a mess.

真是一团糟。

But...

但...

Once you have the basic queue mechanics in place, all you need to do is implement new copyand destroyfunctions for each new type you want to use, along with a new type-aware front end. You don't have to create a whole new Queue_XXXdata type for each data type, nor to you need to create whole new copies of Enqueue_XXXand front_XXXand Dequeue_XXX; you only need to implement a thin, type-aware wrapper for each.

一旦你有了基本的队列机制，你需要做的就是为你想要使用的每个新类型实现 newcopy和destroy函数，以及一个新的类型感知前端。您不必Queue_XXX为每种数据类型创建一个全新的数据类型，也不需要创建Enqueue_XXXandfront_XXX和 and 的全新副本Dequeue_XXX；你只需要为每个实现一个薄的、类型感知的包装器。

There are doubtless many ways to improve what I've written; there are ways to avoid allocating a deallocating a copy for every input, but then indexing into the queue becomes a little less clean.

毫无疑问，有很多方法可以改进我所写的内容；有一些方法可以避免为每个输入分配一个解除分配的副本，但随后对队列的索引变得不那么干净了。

Anyway, it's just food for thought.

无论如何，这只是思考的食物。