循环队列实现

Question

下面的循环队列实现来自数据结构书籍。

struct circqueue {
   int front,rear;
   int capacity;
   int *array;
};




struct circqueue *q(int size) {
   struct circqueue *q=malloc(sizeof(struct circqueue));
   if(!q)return NULL;
   q->capacity=size;
   q->front=-1;
   q->rear=-1;
   q->array=malloc(q->capacity*sizeof(int));
   if(!q->array)return NULL;
  return q;
}

int isemptyqueue(struct circqueue *q) {
   return(q->front==-1);
}

int isfullqueue(struct circqueue *q) {
   return((q->rear+1)%q->capacity==q->rear);
}

int queuesize(struct circqueue *q) {
   return(q->capacity-q->rear+q->front+1)%q->capacity;
}


void enqueue(struct circqueue *q,int x) {

   if(isfullqueue(q))
      printf("queue overflow\n");
   else{
      q->rear=(q->rear+1)%q->capacity;
      q->array[q->rear]=x;
      if(q->front==-1) {
         q->front=q->rear;
      }
   }
}

int dequeue(struct circqueue *q) {
   int data=0;

   if(isemptyqueue(q)) {
      printf("queue underflow");
      return 0;
   }
   else {
      data=q->array[q->front];
      if(q->front==q->rear)
         q->front=q->rear=-1;
      else
         q->front=(q->front+1)%q->capacity;
   }

   return data;
}

我无法理解struct circqueue *q(int size)的确切用途是什么？它是一个初始化队列的函数吗？还有如何从主函数main()中调用它？可以有人给我解释一下。谢谢。

- Vaibhav Sundriyal

Answer 1

struct circqueue* q(int size)
{
    struct circqueue *q=malloc(sizeof(struct circqueue));
    if(!q)
        return NULL;
    q->capacity=size;
    q->front=-1;
    q->rear=-1;
    q->array=malloc(q->capacity*sizeof(int));
    if(!q->array)
       return NULL;
    return q;
}

逐行解读:

1）函数q以队列的最大大小作为参数，并返回一个队列对象（C结构）。

3）将结构体存储在堆上，将q设置为引用此内存位置。

4）如果内存分配失败，则返回适当的非成功消息。

6）使用调用者使用的最大大小值填充circqueue容量。

7）和8）内部索引'push'和'pop'的位置。

9）为内部存储使用的数组分配堆内存。

10）类似于4）

12）将构造的对象返回给调用者。

要创建一个可以容纳最多100个整数的队列，请执行以下操作：

struct circqueue* num_q = q(100);

/* Add an integer */
enqueue(num_q, 3);

- Angus Comber

---

非常感谢您的解释。我正在尝试创建一个动态循环队列，并进行调整大小。当我尝试执行 q->array=realloc(q->array,q->newcapacity) 时，会出现错误 "assignment makes pointer from integer without cast"。您能告诉我我犯了什么错误吗？ - Vaibhav Sundriyal

这是因为您正在使用C ++编译器。在Visual Studio中，如果编译*.cpp文件，则会出现此行为。要么按C方式操作并将例如main.cpp重命名为main.c（然后将使用C规则），要么只需进行强制转换，如下所示：q->array =（struct circqueue *）realloc（q->array，q->newcapacity） - Angus Comber

Answer 2

是的，它初始化了一个 struct circqueue 的实例并为您提供指针：

int main()
{
    struct circqueue *queue = q( 10 );

    // do stuff with queue

    free( queue->array );
    free( queue );
}

- clcto