队列的实现（2）：用链表实现队列

淩亂°似流年 2022-05-29 06:29 157阅读 0赞

上一篇文章：  
[http://blog.csdn.net/keheinash/article/details/51125063][http_blog.csdn.net_keheinash_article_details_51125063]  
利用数组实现了循环队列，这是静态的队列，缺点是需要预设大小，当队列满时，无法再插入新的数据，只有等队头的数据被取走以后才能往队列放入新的数据。

还可以利用链表实现队列，这种方式动态创建节点需要的内存，当有新的数据节点要加入时，才去申请内存空间，不需要预设大小，整个队列需要的内存空间不需要连续，并且插入删除更容易实现。但是同时也带来存取速度慢的缺点，操作也比数组的方式更加复杂。

其实用链表实现队列的方式十分简单，只需要在单链表的基础上，增加一个尾指针即可。因为队列的特点是“先进先出”，因此我们只需要在一头一尾两个指针，就可以快速地在队头取出数据，在队尾插入数据。

首先定义节点数据结构：

typedef struct linkList{
        int data;
        struct linkList* nextNode;
    }linkList_t;

*  1
 *  2
 *  3
 *  4

接着定义链表的结构，其实就是比单链表多了一个尾指针：

typedef struct linkContorl{
        linkList_t* head;
        linkList_t* tail;
    }linkContorl_t;

*  1
 *  2
 *  3
 *  4

除了初始化和销毁，因为目的是利用链表实现队列，这里只给出在队头取得节点和队尾删除节点的操作，像在特定位置插入/删除节点的操作一般而言队列是不会使用的，否则就违背了“先进先出”原则

#include <string.h>
    #include <malloc.h>
    #include <iostream>
    
    using namespace std;
    
    typedef struct linkList{
        int data;
        struct linkList* nextNode;
    }linkList_t;
    
    typedef struct linkContorl{
        linkList_t* head;
        linkList_t* tail;
    }linkContorl_t;
    
    void linkList_Init(linkContorl_t** lCtrl){
        *lCtrl = (linkContorl_t*)malloc(sizeof(linkContorl_t));
        memset(*lCtrl, 0, sizeof(linkContorl_t));
    }
    
    bool linkList_addNode(linkContorl_t* lCtrl, int nodeData){
        linkList_t* newNode = (linkList_t*)malloc(sizeof(linkList_t));
        if(!newNode){
            return false;
        }
    
        newNode->data = nodeData;   
        newNode->nextNode = NULL;   
    
        if((lCtrl->head == NULL) && (lCtrl->tail == NULL)){
            lCtrl->head = newNode;
            lCtrl->tail = newNode;          
        }
        else{
            lCtrl->tail->nextNode = newNode;
            lCtrl->tail = newNode;
        }
    
        return true;
    }
    
    bool linkList_removeNode(linkContorl_t* lCtrl){
        linkList_t* node = lCtrl->head;
        if(node != NULL){
            lCtrl->head = node->nextNode;
            if(node == lCtrl->tail){
                lCtrl->tail = NULL;
            }
            if(node){
                free(node);
            }
            return true;    
        }
        else{
            return false;
        }
    }
    
    void linkList_Deinit(linkContorl_t* lCtrl){
        linkList_t* tmpP = lCtrl->head;
        linkList_t* tmpQ;
        while(tmpP != NULL){
            tmpQ = tmpP;
            tmpP = tmpP->nextNode;      
            free(tmpQ);
        }
        if(lCtrl){
            free(lCtrl);
            lCtrl = NULL;
        }
    }
    
    void printLinkList(linkContorl_t* lCtrl){
        linkList_t* tmpP = lCtrl->head;
        while(tmpP != NULL){
            cout << tmpP->data << " ";
            tmpP = tmpP->nextNode;      
        }
        cout << endl;
    }
    
    int main()
    {
        linkContorl_t* lCtrl;
        linkList_Init(&lCtrl);
    
        linkList_addNode(lCtrl, 10);
        linkList_addNode(lCtrl, 20);
        linkList_addNode(lCtrl, 30);
        printLinkList(lCtrl);   
    
        linkList_removeNode(lCtrl);
        printLinkList(lCtrl);
    
        linkList_removeNode(lCtrl);
        printLinkList(lCtrl);
    
        linkList_removeNode(lCtrl);
        printLinkList(lCtrl);
    
        linkList_addNode(lCtrl, 30);
        printLinkList(lCtrl);   
    
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22
 *  23
 *  24
 *  25
 *  26
 *  27
 *  28
 *  29
 *  30
 *  31
 *  32
 *  33
 *  34
 *  35
 *  36
 *  37
 *  38
 *  39
 *  40
 *  41
 *  42
 *  43
 *  44
 *  45
 *  46
 *  47
 *  48
 *  49
 *  50
 *  51
 *  52
 *  53
 *  54
 *  55
 *  56
 *  57
 *  58
 *  59
 *  60
 *  61
 *  62
 *  63
 *  64
 *  65
 *  66
 *  67
 *  68
 *  69
 *  70
 *  71
 *  72
 *  73
 *  74
 *  75
 *  76
 *  77
 *  78
 *  79
 *  80
 *  81
 *  82
 *  83
 *  84
 *  85
 *  86
 *  87
 *  88
 *  89
 *  90
 *  91
 *  92
 *  93
 *  94
 *  95
 *  96
 *  97
 *  98
 *  99
 *  100
 *  101
 *  102
 *  103
 *  104
 *  105

*  上一篇 转自：http://blog.csdn.net/keheinash/article/details/51143573

[http_blog.csdn.net_keheinash_article_details_51125063]: http://blog.csdn.net/keheinash/article/details/51125063