DoubleLinkedListQueue双链队列

github源码

队列的结点数据结构定义如下：

1
2
3
4
5
typedef struct DLLQNode{
    DLLQElemType *elem;
    struct DLLQNode *prior;
    struct DLLQNode *next;
}DLLQNode;

队列的对象数据结构定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct DLLQueue{
    DLLQNode *front;
    DLLQNode *tear;
    void (*clear)(struct DLLQueue *This);
    int (*isEmpty)(struct DLLQueue *This);
    int (*length)(struct DLLQueue *This);
    void (*riseTraverse)(struct DLLQueue *This,int (*visit)(DLLQElemType **e));
    void (*downTraverse)(struct DLLQueue *This,int (*visit)(DLLQElemType **e));
    int (*getHead)(struct DLLQueue *This, DLLQElemType **e);
    int (*enQueue)(struct DLLQueue *This, DLLQElemType *e);
    int (*deQueue)(struct DLLQueue *This, DLLQElemType **e);
}DLLQueue;

DLLQueue.c

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <stdio.h>
#include <malloc.h>
#include "DLLQueue.h"

static void clear(DLLQueue *This);
static int isEmpty(DLLQueue *This);
static int length(DLLQueue *This);
static void riseTraverse(DLLQueue *This,int (*visit)(DLLQElemType **e));
static void downTraverse(DLLQueue *This,int (*visit)(DLLQElemType **e));
static int getHead(DLLQueue *This, DLLQElemType **e);
static int enQueue(DLLQueue *This, DLLQElemType *e);
static int deQueue(DLLQueue *This, DLLQElemType **e);

DLLQueue *InitDLLQueue(){
    DLLQueue *Q = (DLLQueue *)malloc(sizeof(DLLQueue));
    if(!Q) return NULL;
    DLLQNode *p = (DLLQNode *)malloc(sizeof(DLLQNode));
    if(!p){
        free(Q);
        return NULL;
    }
    Q->front = p;
    Q->tear = Q->front;
    p->prior = NULL;
    p->next = NULL;
    Q->clear = clear;
    Q->isEmpty = isEmpty;
    Q->length = length;
    Q->riseTraverse = riseTraverse;
    Q->downTraverse = downTraverse;
    Q->getHead = getHead;
    Q->enQueue = enQueue;
    Q->deQueue = deQueue;
    return Q;
}

void DestroyDLLQueue(DLLQueue *Q){
    if(Q){
        if(Q->front){
            Q->clear(Q);
            free(Q->front);
        }
        free(Q);
        Q = NULL;
    }
}

static void clear(DLLQueue *This){
    DLLQNode *p = This->front->next;
    DLLQNode *temp = NULL;
    while(p){
        temp = p;
        p = p->next;
        free(temp);
    } 
    p = This->front;
    p->next = NULL;
    This->tear = This->front;
}

static int isEmpty(DLLQueue *This){
    DLLQNode *p = This->front;
    if(p->next){
        return 0;
    }else{
        return 1;
    }
}

static int length(DLLQueue *This){
    int j = 0;
    DLLQNode *p = This->front->next;
    while(p){
        j++;
        p = p->next;
    } 
    return j;
}

static void riseTraverse(DLLQueue *This,int (*visit)(DLLQElemType **e)){
    DLLQNode *p = This->front->next;
    while(p){
        if(visit(&(p->elem)) != 0) break;
        p = p->next;
    } 
}

static void downTraverse(DLLQueue *This,int (*visit)(DLLQElemType **e)){
    DLLQNode *p = This->tear;
    while(p != This->front){
        if(visit(&(p->elem)) != 0) break;
        p = p->prior;
    } 
}


static int getHead(DLLQueue *This, DLLQElemType **e){
    if(isEmpty(This)) return -1;
    *e = This->front->next->elem;
    return 0;
}

static int enQueue(DLLQueue *This, DLLQElemType *e){
    DLLQNode *p = This->tear;
    DLLQNode *temp = (DLLQNode *)malloc(sizeof(DLLQNode));
    if(!temp) return -1;
    temp->elem = e;
    p->next = temp;
    temp->prior = p;
    This->tear = temp;
    temp->next =  NULL;
    return 0;
}

static int deQueue(DLLQueue *This, DLLQElemType **e){
    if(This->front == This->tear){
        *e = NULL;
        return -1;
    }
    DLLQNode *p = This->front->next;
    *e = p->elem;
    This->front->next = p->next;
    if(This->tear == p){
        This->tear = This->front;
    }else{
        p->next->prior = This->front;
    }
    free(p);
    return 0;
}

DLLQueue.h

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
/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef _DLLQUEUE_H
#define _DLLQUEUE_H
/* Includes ------------------------------------------------------------------*/
#include "ElemTypeDefine.h"
/* Exported types ------------------------------------------------------------*/

typedef struct DLLQueue{
    DLLQNode *front;
    DLLQNode *tear;
    void (*clear)(struct DLLQueue *This);
    int (*isEmpty)(struct DLLQueue *This);
    int (*length)(struct DLLQueue *This);
    void (*riseTraverse)(struct DLLQueue *This,int (*visit)(DLLQElemType **e));
    void (*downTraverse)(struct DLLQueue *This,int (*visit)(DLLQElemType **e));
    int (*getHead)(struct DLLQueue *This, DLLQElemType **e);
    int (*enQueue)(struct DLLQueue *This, DLLQElemType *e);
    int (*deQueue)(struct DLLQueue *This, DLLQElemType **e);
}DLLQueue;

/* Exported macro ------------------------------------------------------------*/
DLLQueue *InitDLLQueue();
void DestroyDLLQueue(DLLQueue *Q);

#endif

为了方便在其他的工程代码里对不同元素类型使用DLLQueue，我把ElemTypeDefine抽取出来单独放在一个头文件里。这样，想要适用不同元素类型的DLLQueue，只要修改ElemTypeDefine.h里的 DLLQElemType定义即可。默认的元素类型为int。

ElemTypeDefine.h文件

1
2
3
4
5
6
7
8
9
10
11
12
13
/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef _ELEMTYPEDEFINE_H
#define _ELEMTYPEDEFINE_H

typedef int DLLQElemType;

typedef struct DLLQNode{
    DLLQElemType *elem;
    struct DLLQNode *prior;
    struct DLLQNode *next;
}DLLQNode;

#endif

testDLLQueue.c文件

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
#include <stdio.h>
#include <malloc.h>
#include "DLLQueue.h"

int printElem(DLLQElemType **e){
    printf("%d",**e);
    return 0;
}

int main(void){
    int i = 0,*elem;
    int *num = (int *)malloc(10*sizeof(int));
    if(!num) return 0;
    for(i=0;i<10;i++){
        *(num + i) = i;
    }
    DLLQueue *Q = InitDLLQueue();
    printf("is DLLQueue empty:%d\n",Q->isEmpty(Q));
    printf("DLLQueue length:%d\n",Q->length(Q));
    for(i=0;i<10;i++){
        Q->enQueue(Q,num + i);
    }
    printf("is DLLQueue empty:%d\n",Q->isEmpty(Q));
    printf("DLLQueue length:%d\n",Q->length(Q));
    Q->riseTraverse(Q,printElem);
    printf("\n");
    Q->clear(Q);
    printf("is DLLQueue empty:%d\n",Q->isEmpty(Q));
    printf("DLLQueue length:%d\n",Q->length(Q));
    for(i=0;i<10;i++){
        *(num + i) = i*2;
        Q->enQueue(Q,num + i);
    }
    Q->downTraverse(Q,printElem);
    printf("\n");
    for(i=0;i<10;i++){
        Q->getHead(Q,&elem);
        printf("Head elem:%d\n",*elem);
        Q->deQueue(Q,&elem);
        printf("deQueue elem:%d\n",*elem);
    }
    printf("is DLLQueue empty:%d\n",Q->isEmpty(Q));
    printf("DLLQueue length:%d\n",Q->length(Q));
    DestroyDLLQueue(Q);
    free(num);
    return 0;
}

编译：

1
gcc DLLQueue.c testDLLQueue.c -o testDLLQueue

执行testDLLQueue：

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
is DLLQueue empty:1
DLLQueue length:0
is DLLQueue empty:0
DLLQueue length:10
0123456789
is DLLQueue empty:1
DLLQueue length:0
181614121086420
Head elem:0
deQueue elem:0
Head elem:2
deQueue elem:2
Head elem:4
deQueue elem:4
Head elem:6
deQueue elem:6
Head elem:8
deQueue elem:8
Head elem:10
deQueue elem:10
Head elem:12
deQueue elem:12
Head elem:14
deQueue elem:14
Head elem:16
deQueue elem:16
Head elem:18
deQueue elem:18
is DLLQueue empty:1
DLLQueue length:0