《Hello算法》基于链表双向队列的学习

lugl4313820

《Hello算法》基于链表双向队列的学习 [复制链接]

对于双向队列而言，头部和尾部都可以执行入队和出队操作。换句话说，双向队列需要实现另一个对称方向的操作。为此，我们采用“双向链表”作为双向队列的底层数据结构。

如图 5-8 所示，我们将双向链表的头节点和尾节点视为双向队列的队首和队尾，同时实现在两端添加和删除节点的功能。

根据教程结合我自己的编程，我用代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/* 双向链表节点 */
typedef struct DoublyListNode {
    int val;
    struct DoublyListNode *prev;
    struct DoublyListNode *next;
} DoublyListNode;

/* 构造函数 */
DoublyListNode *newDoublyListNode(int val) {
    DoublyListNode *node = (DoublyListNode *)malloc(sizeof(DoublyListNode));
    if(node == NULL)
    {
        printf("malloc failed\n");
        return NULL;
    }
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

/* 链表节点析构函数 */
void freeDoublyListNode(DoublyListNode *node)
{
    if(node != NULL)
    {
        printf("free node\n");
        free(node);
    }
    else {
        printf("错误输入参数\n");
    }
}

/* 双向链表实现的双向队列 */
typedef struct DoublyLinkedListDeque {
    DoublyListNode *front;  // 队首节点
    DoublyListNode *rear;   //
    int queSize;    // 队列长度
} DoublyLinkedListDeque;

/* 构造函数    */
DoublyLinkedListDeque *newLinkedListDeque() {
    DoublyLinkedListDeque *deque = (DoublyLinkedListDeque *)malloc(sizeof(DoublyLinkedListDeque));
    if(deque == NULL)
    {
        printf("malloc failed\n");
        return NULL;
    }
    deque->front = NULL;
    deque->rear = NULL;
    deque->queSize = 0;
    return deque;
}

/* 析构函数 */
void freeLinkedListDeque(DoublyLinkedListDeque *deque)
{
    if(deque != NULL)
    {
        printf("free deque\n");
        free(deque);
    }
    for(int i=0; i<deque->queSize && deque->front != NULL; i++)
    {
        DoublyListNode *node = deque->front;
        deque->front = deque->front->next;
        freeDoublyListNode(node);
    }
    free(deque);
}

/* 获取双向队列长度 */
int getLinkedListDequeSize(DoublyLinkedListDeque *deque, int *len)
{
    if(deque == NULL)
    {
        printf("错误输入参数\n");
        return -1;
    }
    *len = deque->queSize;
    return 0;
}

/* 判断双向队列是否为空 */
int isLinkedListDequeEmpty(DoublyLinkedListDeque *deque, bool *flag)
{
    if(deque == NULL)
    {
        printf("错误输入参数\n");
        return -1;
    }
    *flag = (deque->queSize == 0);
    return 0;
}

/* 入列 */
int push(DoublyLinkedListDeque *deque, int val, bool isFront) {
    if(deque == NULL)
    {
        printf("错误输入参数\n");
        return -1;
    }
    DoublyListNode *node = newDoublyListNode(val);
    if (node == NULL)
    {
        printf("malloc failed\n");
        return -1;
    }
    int ret = 0;
    bool flag;
    ret = isLinkedListDequeEmpty(deque, &flag);
    if(ret == 0)
    {
        if(flag)
        {
            deque->front = deque->rear = node;
        }
        else if(isFront) {
            // 将node添加到头部
            node->next = deque->front;
            deque->front->prev = node;
            deque->front = node;
        }
        else //队尾入队操作
        {
            // 将node 添加到尾部
            deque->rear->next = node;
            node->prev = deque->rear;
            deque->rear = node;
        }
        deque->queSize++; // 队列长度加1
        return 0;
    }
    return -1;
}

/* 队首入列 */
int pushFirst(DoublyLinkedListDeque *deque, int val)
{
    int ret = push(deque, val, true);
    if(ret == 0)
    {
        printf("入队成功\n");
        return 0;
    }
    printf("入队失败\n");
    return -1;
}

/* 队尾入列 */
int pushLast(DoublyLinkedListDeque *deque, int val)
{
    int ret = push(deque, val, false);
    if(ret == 0)
    {
        printf("入队成功\n");
        return 0;
    }
    printf("入队失败\n");
    return -1;
}

/* 访问队首元素 */
int peekFirst(DoublyLinkedListDeque *deque, int *val)
{
    if(deque == NULL)
    {
        printf("错误输入参数\n");
        return -1;
    }
    if(deque->front == NULL)
    {
        printf("队列为空\n");
        return -1;
    }
    *val = deque->front->val;
    return 0;
}

/* 访问队尾元素 */
int peekLast(DoublyLinkedListDeque *deque, int *val)
{
    if(deque == NULL)
    {
        printf("错误输入参数\n");
        return -1;
    }
    if(deque->rear == NULL)
    {
        printf("队列为空\n");
        return -1;
    }
    *val = deque->rear->val;
    return 0;
}

/* 出列  */
int pop(DoublyLinkedListDeque *deque, int * val, bool isFront)
{
    if(deque == NULL)
    {
        printf("错误输入参数\n");
        return -1;
    }
    bool flag;
    int ret = isLinkedListDequeEmpty(deque, &flag);
    if(ret == 0)
    {
        if(flag)
        {
            printf("队列为空\n");
            return -1;
        }

        if(isFront)
        {
            // 队首出列
            ret = peekFirst(deque, val); //暂存节点值
            if(ret != 0)
            {
                printf("队列为空\n");
                return -2;
            }
            DoublyListNode *fNext = deque->front->next;
            if(fNext != NULL)
            {
                fNext->prev = NULL;
                deque->front->next = NULL;
            }
            freeDoublyListNode(deque->front);
            deque->front = fNext;
       } else
       {
         ret = peekLast(deque, val);
         if(ret != 0)
         {
             printf("队列为空\n");
             return -2;
         }
         DoublyListNode *rPrev = deque->rear->prev;
         if(rPrev != NULL)
         {
             rPrev->next = NULL;
             deque->rear->prev = NULL;
         }
         freeDoublyListNode(deque->rear);
         deque->rear = rPrev; // 更新尾节点
       }
       deque->queSize--;
       return 0;
    }
    printf("队列为空\n");
    return -1;
}
/* 队首出列 */
int popFirst(DoublyLinkedListDeque *deque, int *val)
{
    int ret = pop(deque, val, true);
    if(ret == 0)
    {
        printf("出队成功\n");
        return 0;
    }
    printf("出队失败\n");
    return -1;
}

/* 队尾出列 */
int popLast(DoublyLinkedListDeque *deque, int *val)
{
    int ret = pop(deque, val, false);
    if(ret == 0)
    {
        printf("出队成功\n");
        return 0;
    }
    printf("出队失败\n");
    return -1;
}

/* 打印双向队列 */
void printLinkedListDeque(DoublyLinkedListDeque *deque)
{
    if(deque == NULL)
    {
        printf("错误输入参数\n");
        return;
    }

    DoublyListNode *node = deque->front;
    while (node != NULL)
    {
        printf("node val: %d\r\n", node->val);
        node = node->next;
    }
}

int main()
{
   //  测试双向队列
    DoublyLinkedListDeque *deque = newLinkedListDeque();
    if(deque == NULL)
    {
        printf("malloc failed\n");
        return -1;
    }
    pushFirst(deque, 1);
    pushFirst(deque, 2);
    pushFirst(deque, 5);
    pushLast(deque, 3);
    printLinkedListDeque(deque);
    printf("开始出列\r\n");
    int val;
    popFirst(deque, &val);
    printf("出列的元素为: %d\r\n", val);
    printLinkedListDeque(deque);
}

经编译后，测试结果如下：

婢跺秴鍩�

登录后复制

liujianhuadeiMac:pro_node liujianhua$ gcc linklist_deque.c -Wall
liujianhuadeiMac:pro_node liujianhua$ ./a.out 
入队成功
入队成功
入队成功
入队成功
node val: 5
node val: 2
node val: 1
node val: 3
开始出列
free node
出队成功
出列的元素为: 5
node val: 2
node val: 1
node val: 3

【学习小结】

经过自己亲自写代码，理解了如何实现双向队例的实现。双向队列可以实现从头插入，或者从尾部插入，出列也可以双向实现，使用起来非常的方便。

查看本帖全部内容，请登录或者注册

Jacktang

楼主自己亲自写的代码，原汁原味，超级赞

《Hello算法》基于链表双向队列的学习 [复制链接]

最新回复

浏览过的版块