如何在C中的链表中实现队列? [英] How to implement a queue in a linked list in c?

问题描述

我得到了这些结构声明，以实现使用循环链表的队列集合.

I am given these structure declarations in order to implement a queue collection that uses a circular linked list.

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;
}

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

I'm trying to create a function that will enqueue at a specified value (append it to the rear of the queue), and I need to consider the two cases in which the queue is empty and when the queue has one or more elements. This is the code I have so far:

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在最前面，但是我认为这可能是问题所在.非常感谢所有帮助.谢谢！

This code gives me a runtime error so I'm not sure whats wrong. In the code, I'm assuming queue->rear->next is the front, however I think this is where the problem might be. All help is greatly appreciated. Thanks!

更新-

我试图重新编写代码并得到以下信息:

I've tried to rework the code and got this:

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);

    }
}

这仅在为空时有效，而在不为空时无效.

This works only when it is empty but not when it is not empty.

推荐答案

链接列表中的循环队列

Circular Queue in Linked List

您的代码太大，无法读出，因此这里是我用来实现循环队列的内容:

#include使用命名空间std;

#include using namespace std;

// 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;
}

这篇关于如何在C中的链表中实现队列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！