蚕鸣夏季

标签： 队列

  • C基于链表实现队列

    本章内容是基于上一篇文章单链表的实现 C-单链表的实现 。

    队列是先进先出（First in First out）的线性数据结构. 通常有2个主要的操作：enqueue 和 dequeue。

    enqueue操作是将元素添加到列队中。

    dequeue操作是将元素从队列中移除。

    链表经常用于队列的实现。enqueue 操作是从链表的头部（head）添加元素，dequeue 操作是从链表的尾部（tail）移除元素。

    队列定义

    定义队列和相关操作

    // 定义队列
typedef LinkedList Queue;
// 初始化队列
void initQueue(Queue *queue)
{
    init_linkedlist(queue);
}

// 添加元素
void enqueue(Queue *queue, void *data) {
    addHead(queue, data);
}

// 移除元素
void* dequeue(Queue *queue) 
{
    pNode node = queue->head;
    void* data;
    if (queue->head == NULL){
        data = NULL;
    } else if (queue->head == queue->tail) {
        queue->head = queue->tail = NULL;
        data = node->data;
        free(node);
    } else {
        // 找到倒数第二个节点，由于之前实现的链表是单链表，只能这么找
        while (node->next != queue->tail)
        {
            node = node->next;
        }
        queue->tail= node;
        node = node->next;
        queue->tail->next = NULL;

        data = node->data;
        free(node);
    }

    return data;   
}

    示例说明

        Queue queue;
    // 初始化
    initQueue(&queue);
    int a = 20;
    int b = 30;
    int c = 40;
    int *ptr_1 = &a;
    int *ptr_2 = &b;
    int *ptr_3 = &c;

    enqueue(&queue, ptr_1);
    enqueue(&queue, ptr_2);
    enqueue(&queue, ptr_3);

    void *data = dequeue(&queue);
    printf("Dequeued %d\n", *((int*) data));

    data = dequeue(&queue);
    printf("Dequeued %d\n", *((int*) data));

    data = dequeue(&queue);
    printf("Dequeued %d\n", *((int*) data));

    结构打印：

    Dequeued 20
    Dequeued 30
    Dequeued 40

    以上内容，如有错误，欢迎留言交流或添加公众号交流。