DoubleLinkedListStack双链栈

github源码

栈的结点数据结构定义如下：

1
2
3
4
5
6
7
typedef int DLLSElemType;

typedef struct DLLSNode{
    DLLSElemType *elem;
    struct DLLSNode *prior;
    struct DLLSNode *next;
}DLLSNode;

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

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct DLLStack{
    DLLSNode *front;
    DLLSNode *tear;
    void (*clear)(struct DLLStack *This);
    int (*isEmpty)(struct DLLStack *This);
    int (*length)(struct DLLStack *This);
    void (*riseTraverse)(struct DLLStack *This,int (*visit)(DLLSElemType **e));
    void (*downTraverse)(struct DLLStack *This,int (*visit)(DLLSElemType **e));
    int (*getTopElem)(struct DLLStack *This, DLLSElemType **e);
    int (*pushElem)(struct DLLStack *This, DLLSElemType *e);
    int (*popElem)(struct DLLStack *This, DLLSElemType **e);
}DLLStack;

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

static void clear(DLLStack *This);
static int isEmpty(DLLStack *This);
static int length(DLLStack *This);
static void riseTraverse(DLLStack *This,int (*visit)(DLLSElemType **e));
static void downTraverse(DLLStack *This,int (*visit)(DLLSElemType **e));
static int getTopElem(DLLStack *This, DLLSElemType **e);
static int pushElem(DLLStack *This, DLLSElemType *e);
static int popElem(DLLStack *This, DLLSElemType **e);

DLLStack *InitDLLStack(){
    DLLStack *S = (DLLStack *)malloc(sizeof(DLLStack));
    if(!S) return NULL;
    DLLSNode *p = (DLLSNode *)malloc(sizeof(DLLSNode));
    if(!p){
        free(S);
        return NULL;
    }
    S->front = p;
    S->tear = S->front;
    p->prior = NULL;
    p->next = NULL;
    S->clear = clear;
    S->isEmpty = isEmpty;
    S->length = length;
    S->riseTraverse = riseTraverse;
    S->downTraverse = downTraverse;
    S->getTopElem = getTopElem;
    S->pushElem = pushElem;
    S->popElem = popElem;
    return S;
}

void DestroyDLLStack(DLLStack *S){
    if(S){
        if(S->front){
            S->clear(S);
            free(S->front);
        }
        free(S);
        S = NULL;
    }
}

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

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

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

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

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


static int getTopElem(DLLStack *This, DLLSElemType **e){
    if(isEmpty(This)) return -1;
    *e = This->tear->elem;
    return 0;
}

static int pushElem(DLLStack *This, DLLSElemType *e){
    DLLSNode *p = This->tear;
    DLLSNode *temp = (DLLSNode *)malloc(sizeof(DLLSNode));
    if(!temp) return -1;
    temp->elem = e;
    p->next = temp;
    temp->prior = p;
    This->tear = temp;
    temp->next =  NULL;
    return 0;
}

static int popElem(DLLStack *This, DLLSElemType **e){
    if(This->front == This->tear){
        *e = NULL;
        return -1;
    }
    DLLSNode *p = This->tear;
    DLLSNode *temp = NULL;
    temp = p->prior;
    *e = p->elem;
    free(p);
    This->tear = temp;
    temp->next = NULL;
    return 0;
}

DLLStack.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 _DLLSTACK_H
#define _DLLSTACK_H
/* Includes ------------------------------------------------------------------*/
#include "ElemTypeDefine.h"
/* Exported types ------------------------------------------------------------*/

typedef struct DLLStack{
    DLLSNode *front;
    DLLSNode *tear;
    void (*clear)(struct DLLStack *This);
    int (*isEmpty)(struct DLLStack *This);
    int (*length)(struct DLLStack *This);
    void (*riseTraverse)(struct DLLStack *This,int (*visit)(DLLSElemType **e));
    void (*downTraverse)(struct DLLStack *This,int (*visit)(DLLSElemType **e));
    int (*getTopElem)(struct DLLStack *This, DLLSElemType **e);
    int (*pushElem)(struct DLLStack *This, DLLSElemType *e);
    int (*popElem)(struct DLLStack *This, DLLSElemType **e);
}DLLStack;

/* Exported macro ------------------------------------------------------------*/
DLLStack *InitDLLStack();
void DestroyDLLStack(DLLStack *S);

#endif

为了方便在其他的工程代码里对不同元素类型使用DLLStack，我把ElemTypeDefine抽取出来单独放在一个头文件里。这样，想要适用不同元素类型的DLLStack，只要修改ElemTypeDefine.h里的 DLLSElemType定义即可。默认的元素类型为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 DLLSElemType;

typedef struct DLLSNode{
    DLLSElemType *elem;
    struct DLLSNode *prior;
    struct DLLSNode *next;
}DLLSNode;

#endif

testDLLStack.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 "DLLStack.h"

int printElem(DLLSElemType **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;
    }
    DLLStack *S = InitDLLStack();
    printf("is DLLStack empty:%d\n",S->isEmpty(S));
    printf("DLLStack length:%d\n",S->length(S));
    for(i=0;i<10;i++){
        S->pushElem(S,num + i);
    }
    printf("is DLLStack empty:%d\n",S->isEmpty(S));
    printf("DLLStack length:%d\n",S->length(S));
    S->riseTraverse(S,printElem);
    printf("\n");
    S->clear(S);
    printf("is DLLStack empty:%d\n",S->isEmpty(S));
    printf("DLLStack length:%d\n",S->length(S));
    for(i=0;i<10;i++){
        *(num + i) = i*2;
        S->pushElem(S,num + i);
    }
    S->downTraverse(S,printElem);
    printf("\n");
    for(i=0;i<10;i++){
        S->getTopElem(S,&elem);
        printf("top elem:%d\n",*elem);
        S->popElem(S,&elem);
        printf("pop elem:%d\n",*elem);
    }
    printf("is DLLStack empty:%d\n",S->isEmpty(S));
    printf("DLLStack length:%d\n",S->length(S));
    DestroyDLLStack(S);
    free(num);
    return 0;
}

编译：

1
gcc DLLStack.c testDLLStack.c -o testDLLStack

执行testDLLStack：

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