c - 如何在c中的链表中实现队列？

Question

我得到这些结构声明是为了实现一个使用循环链表的队列集合。

typedef struct intnode {
int value;
struct intnode *next;
} intnode_t;

typedef struct {
intnode_t *rear;   // Points to the node at the tail of the 
                   // queue's linked list
int size;          // The # of nodes in the queue's linked list
} intqueue_t;

intnode_t *intnode_construct(int value, intnode_t *next)
{
    intnode_t *p = malloc(sizeof(intnode_t));
    assert (p != NULL);
    p->value = value;
    p->next = next;
    return p;
}


/* Return a pointer to a new, empty queue.
 * Terminate (via assert) if memory for the queue cannot be allocated.
 */

intqueue_t *intqueue_construct(void)
{
intqueue_t *queue = malloc(sizeof(intqueue_t));
assert(queue != NULL);

    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

我正在尝试创建一个将以指定值入队的函数(将其附加到队列的尾部)，我需要考虑两种情况，其中队列为空，当队列有一个或更多的元素。这是我到目前为止的代码:

void intqueue_enqueue(intqueue_t *queue, int value)
{

    intnode_t *p = intnode_construct(value, NULL);

    if(queue->rear->next == NULL) {
    //the queue is empty
    queue->rear->next =p;
}     else {
    //the queue is not empty
    queue->rear=p;
}
queue->rear=p;
queue->size++;
}

这段代码给我一个运行时错误，所以我不确定哪里出了问题。在代码中，我假设 queue->rear->next 是前面的，但我认为这可能是问题所在。非常感谢所有帮助。谢谢!

更新——

我尝试重新编写代码并得到了这个:

void intqueue_enqueue(intqueue_t *queue, int value)
{
assert(queue!=NULL);


  intnode_t *p = intnode_construct(value,NULL);

 if (queue->size==0){

    queue->rear=p;
    queue->size++;
    queue->rear->next=p;
    free(p);
    }
else {
    p->next = queue->rear;
    queue->rear=p;
    queue->size++;
    free(p);

    }
}

这只在它为空时有效，但当它不为空时则无效。

Answer 1

Circular Queue in Linked List

你的代码太大读不出来，所以这里我用的是实现循环队列:

#include 使用命名空间标准；

// Structure of a Node
struct Node
{
    int data;
    struct Node* link;
};

struct Queue
{
    struct Node *front, *rear;
};

// Function to create Circular queue
void enQueue(Queue *q, int value)
{
    struct Node *temp = new Node;
    temp->data = value;
    if (q->front == NULL)
        q->front = temp;
    else
        q->rear->link = temp;

    q->rear = temp;
    q->rear->link = q->front;
}

// Function to delete element from Circular Queue
int deQueue(Queue *q)
{
    if (q->front == NULL)
    {
        printf ("Queue is empty");
        return INT_MIN;
    }

    // If this is the last node to be deleted
    int value; // Value to be dequeued
    if (q->front == q->rear)
    {
        value = q->front->data;
        free(q->front);
        q->front = NULL;
        q->rear = NULL;
    }
    else  // There are more than one nodes
    {
        struct Node *temp = q->front;
        value = temp->data;
        q->front = q->front->link;
        q->rear->link= q->front;
        free(temp);
    }

    return value ;
}

// Function displaying the elements of Circular Queue
void displayQueue(struct Queue *q)
{
    struct Node *temp = q->front;
    printf("\nElements in Circular Queue are: ");
    while (temp->link != q->front)
    {
        printf("%d ", temp->data);
        temp = temp->link;
    }
    printf("%d", temp->data);
}

/* Driver of the program */
int main()
{
    // Create a queue and initialize front and rear
    Queue *q = new Queue;
    q->front = q->rear = NULL;

    // Inserting elements in Circular Queue
    enQueue(q, 14);
    enQueue(q, 22);
    enQueue(q, 6);

    // Display elements present in Circular Queue
    displayQueue(q);

    // Deleting elements from Circular Queue
    printf("\nDeleted value = %d", deQueue(q));
    printf("\nDeleted value = %d", deQueue(q));

    // Remaining elements in Circular Queue
    displayQueue(q);

    enQueue(q, 9);
    enQueue(q, 20);
    displayQueue(q);

    return 0;
}