链式队列的表示和实现

表示

typedef struct node4q_t {
    data_t data;
    struct node4q_t *next;
} linknode4q_t, *linklist4q_t;

typedef struct
{
    linklist4q_t front, rear;
} linkqueue_t;

实现

//创建
linkqueue_t *CreateEmptyLinkqueue(void)
{
    linkqueue_t *queue;
    queue = (linkqueue_t *)malloc(sizeof(linkqueue_t));
    if (NULL != queue)
        queue->front = queue->rear = NULL;
    return queue;
}



//清空
int ClearLinkqueue(linkqueue_t *queue)
{
    linknode4q_t *node;
    if (NULL != queue) {
        while (NULL != queue->front) {
            node = queue->front;
            queue->front = node->next;
            free(node);
        }
        queue->rear = NULL;
        return 0;
        
    } else {
        return -1;
    }
}
//销毁
int DestroyLinkqueue(linkqueue_t *queue)
{
    if (NULL != queue) {
        ClearLinkqueue(queue);
        free(queue);
        return 0;
    } else {
        return -1;
    }
}
//是否为空
int EmptyLinkqueue(linkqueue_t *queue)
{
    if (NULL != queue) {
        return (queue->front == NULL ? 1 : 0);
    } else {
        return -1;
    }
}



//入队
int EnQueue(linkqueue_t *queue, data_t x)
{
    if (NULL == queue) return -1;
    
    linknode4q_t *node_new;
    node_new = (linknode4q_t *)malloc(sizeof(linknode4q_t));
    if (NULL == node_new) return -1;
    
    node_new->data = x;
    node_new->next = NULL;

    if (NULL != queue->front) {
        queue->rear->next = node_new;
        queue->rear = node_new;
    } else {
        queue->front = queue->rear = node_new;
    }
    return 0;
}
//出队
int DeQueue(linkqueue_t *queue, data_t *x)
{
    if (NULL == queue) return -1;
    if (NULL == queue->front) return -1;
    if (NULL == x) return -1;
    
    linknode4q_t *node_remove;
    node_remove = queue->front;
    
    queue->front = node_remove->next;
    
    if (NULL == queue->front) queue->rear = NULL;
    
    if (NULL != x)
        *x = node_remove->data;
        
    free(node_remove);
    
    return 0;
}

测试代码

void iterate_queue(linkqueue_t * queue)
{
    linknode4q_t *node;

    /* browse from the front to the rear */
    printf("queue = front{");

    node = queue->front;
    while (NULL != node) {
        printf("%d->", node->data);
        node = node->next;
    }
    
    if (1 == EmptyLinkqueue(queue)) {
        printf("}rear
");
    } 
    else {
        printf("}rear
");
    }

    return;
}

int main()
{
    int i;
    data_t data;
    linkqueue_t *queue;

    queue = CreateEmptyLinkqueue();

    for (i = 1; i < 10; i++) {
        printf("Enter %2d: ", i);
        EnQueue(queue, i);
        iterate_queue(queue);
    }

    while (!EmptyLinkqueue(queue)){
        DeQueue(queue, &data);
        printf("Out   %2d: ", data);
        iterate_queue(queue);
    }

    /* run again */
    for (i = 1; i < 10; i++) {
        printf("Enter %2d: ", i);
        EnQueue(queue, i);
        iterate_queue(queue);
    }

    while (!EmptyLinkqueue(queue)){
        DeQueue(queue, &data);
        printf("Out   %2d: ", data);
        iterate_queue(queue);
    }
    
    DestroyLinkqueue(queue);

    return 0;
}

结果

Enter  1: queue = front{1}rear
Enter  2: queue = front{1->2}rear
Enter  3: queue = front{1->2->3}rear
Enter  4: queue = front{1->2->3->4}rear
Enter  5: queue = front{1->2->3->4->5}rear
Enter  6: queue = front{1->2->3->4->5->6}rear
Enter  7: queue = front{1->2->3->4->5->6->7}rear
Enter  8: queue = front{1->2->3->4->5->6->7->8}rear
Enter  9: queue = front{1->2->3->4->5->6->7->8->9}rear
Out    1: queue = front{2->3->4->5->6->7->8->9}rear
Out    2: queue = front{3->4->5->6->7->8->9}rear
Out    3: queue = front{4->5->6->7->8->9}rear
Out    4: queue = front{5->6->7->8->9}rear
Out    5: queue = front{6->7->8->9}rear
Out    6: queue = front{7->8->9}rear
Out    7: queue = front{8->9}rear
Out    8: queue = front{9}rear
Out    9: queue = front{}rear
Enter  1: queue = front{1}rear
Enter  2: queue = front{1->2}rear
Enter  3: queue = front{1->2->3}rear
Enter  4: queue = front{1->2->3->4}rear
Enter  5: queue = front{1->2->3->4->5}rear
Enter  6: queue = front{1->2->3->4->5->6}rear
Enter  7: queue = front{1->2->3->4->5->6->7}rear
Enter  8: queue = front{1->2->3->4->5->6->7->8}rear
Enter  9: queue = front{1->2->3->4->5->6->7->8->9}rear
Out    1: queue = front{2->3->4->5->6->7->8->9}rear
Out    2: queue = front{3->4->5->6->7->8->9}rear
Out    3: queue = front{4->5->6->7->8->9}rear
Out    4: queue = front{5->6->7->8->9}rear
Out    5: queue = front{6->7->8->9}rear
Out    6: queue = front{7->8->9}rear
Out    7: queue = front{8->9}rear
Out    8: queue = front{9}rear
Out    9: queue = front{}rear