算法设计------队列实现

发表于 | 分类于 ，

队列

队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中的元素进出是按先进先出的原则进行（FIFO–First In First Out）。

队列的C语言实现

.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
#ifndef Queue_h
#define Queue_h

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

typedef struct node {
    int member;//数据域
    struct node * pNext;
}Node, * pNode;

typedef struct queue{
    pNode pHead;//队头
    pNode pTail;//队尾
}Queue, * pQueue;

void InitQueue(pQueue);//初始化
bool InQueue(pQueue,int);//入队
int DeQueue(pQueue);//出队
bool EmptyQueue(pQueue);//判空
void ClearQueue(pQueue);//清空队列
void TraverQueue(pQueue);//遍历队列

#endif

.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
#include "Queue.h"
#include "stdlib.h"

void InitQueue(pQueue queue){
    queue -> pHead = malloc(sizeof(Node));
    if (NULL == queue -> pHead) {
        printf("分配内存失败");
        exit(-1);
    }else{
        queue -> pTail = queue -> pHead;
        queue -> pTail -> pNext = NULL;
    }
}
bool InQueue(pQueue queue,int num){
    pNode pNew = malloc(sizeof(Node));
    if (NULL == pNew) {
        printf("分配内存失败");
        return false;
    }else{
        queue -> pTail -> member = num;
        queue -> pTail -> pNext = pNew;
        queue -> pTail = pNew;
        return true;
    }
}
bool EmptyQueue(pQueue queue){
    if (queue -> pTail == queue -> pHead) {
        return true;
    }else{
        return false;
    }
}
int DeQueue(pQueue queue){
    
    if (EmptyQueue(queue)) {
        printf("Queue is Empty");
        exit(-1);
    }else{
        int return_val;
        pNode pTemp = queue -> pHead;
        queue -> pHead = queue -> pHead -> pNext;
        return_val = pTemp -> member;
        free(pTemp);
        return return_val;
    }
}

void ClearQueue(pQueue queue){
    
    pNode pHead = NULL;
    while (!EmptyQueue(queue)) {
        pHead = queue -> pHead;
        queue -> pHead = queue -> pHead -> pNext;
        free(pHead);
    }
}
void TraverQueue(pQueue queue){
    pNode  pHead = queue -> pHead;
    while (pHead != queue -> pTail) {
        printf("%d", pHead -> member);
        pHead = pHead -> pNext;

    }
}

测试代码

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
void testQueue (){
    Queue queue;
    int i;
    int re_num;
    InitQueue(&queue);
    
    for (i = 0;  i < 5; i ++) {
        printf("第 %d 个数：\n",i+1);
        if (InQueue(&queue, i + 100)) {
            continue;
        }else{
            printf("进行入队操作失败！\n");
            exit(-1);
        }
    }
    
    printf("queue after inQueue\n");
    TraverQueue(&queue);
    
    for (int i = 0; i < 3; i ++) {
        re_num = DeQueue(&queue);
        printf("remover %d \n",re_num);
        
        printf("queue after dequeue\n");
        TraverQueue(&queue);
    }
    
    ClearQueue(&queue);
    printf("queue after clear\n");
    TraverQueue(&queue);
    
}
时间复杂度：InQueue、Dequeue操作的时间复杂度均为 O(1)

如果对你有帮助的话，Star✨下一吧！