廖家龙的博客网站
队列的链式实现
廖家龙 用心听，不照做
  2019-03-15 23:40:00   2024-07-18 23:45:16    662 字  3 分钟

顺序存储：预分配的空间耗尽时队满
链式存储：一般不会队满，除非内存不足

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
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

//队列的链式实现(带头结点和不带头结点)
typedef struct LinkNode{  //链式队列结点
    int data;
    struct LinkNode *next;
}LinkNode;

typedef struct{  //链式队列
    LinkNode *front,*rear;  //队列的队头和队尾指针
    
    //int length;  //求队列的长度
}LinkQueue;

//初始化队列(带头结点)
void InitQueue(LinkQueue *Q){
    //初始时，front、rear都指向头结点
    Q->front=Q->rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q->front->next=NULL;
}

//判断队列是否为空
bool IsEmpty(LinkQueue *Q){
    if(Q->front==Q->rear){
        return true;
    }
    else{
        return false;
    }
}

//初始化(不带头结点)
//void InitQueue(LinkQueue *Q){
//    //初始时，front、rear都指向NULL
//    Q->front=NULL;
//    Q->rear=NULL;
//}

//判断队列是否为空(不带头结点)
//bool IsEmpty(LinkQueue *Q){
//    if(Q->front==NULL){
//        return true;
//    }
//    else{
//        return false;
//    }
//}

//新元素入队(带头结点)
void EnQueue(LinkQueue *Q,int x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q->rear->next=s;  //新结点插入到rear之后
    Q->rear=s;  //修改表尾指针
}

//新元素入队(不带头结点)
//void EnQueue(LinkQueue *Q,int x){
//    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
//    s->data=x;
//    s->next=NULL;
//    if(Q->front == NULL){  //在空队列中插入第一个元素
//        Q->front=s;  //修改队头队尾指针
//        Q->rear=s;  //不带头结点的队列，第一个元素入队时需要特别处理
//    }else{
//        Q->rear->next=s;  //新结点插入到rear之后
//        Q->rear=s;  //修改rear指针
//    }
//}

//队头元素出队(带头结点)
bool DeQueue(LinkQueue *Q,int *x){
    if(Q->front==Q->rear){
        return false;  //空队
    }
    LinkNode *p=Q->front->next;
    *x=p->data;  //用变量x返回队头元素
    Q->front->next=p->next;  //修改头结点的next指针
    if(Q->rear==p){  //此次是最后一个结点出队
        Q->rear=Q->front;  //修改rear指针
    }
    free(p);  //释放结点空间
    return true;
}

//队头元素出队(不带头结点)
//bool DeQueue(LinkQueue *Q,int *x){
//    if(Q->front==NULL){
//        return false;  //空队
//    }
//    LinkNode *p=Q->front;  //p指向此次出队的结点
//    *x=p->data;  //用变量x返回队头元素
//    Q->front=p->next;  //修改front指针
//    if(Q->rear==p){  //此次是最后一个结点出队
//        Q->front=NULL;  //front指向NULL
//        Q->rear=NULL;  //rear指向NULL
//    }
//    free(p);  //释放结点空间
//    return true;
//}

int main(){
    LinkQueue Q;  //声明一个队列
    InitQueue(&Q);  //初始化队列
    
    //...后续操作
}