小码农教你循环队列 设计循环队列

发表于

「这是我参与11月更文挑战的第13天，活动详情查看：2021最后一次更文挑战」

设计循环队列

题目

image-20211103204637814

我们会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

image-20211103204617520

image-20211103230000226

可以认为队尾tail不是队尾，而是我们认知上队尾的后一个

数组形式（通过下标控制来达到循环的效果）

环队结构体（数组）

1
2
3
4
5
6
c复制代码typedef struct {
    int* a;
    int front;
    int tail;
    int k;//数组元素(队列长度)
} MyCircularQueue;

环队初始化

1
2
3
4
5
6
7
c复制代码MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a = (int*)malloc(sizeof(int)*(k+1));//队列长度为k我们要多开一个
    q->front = q->tail = 0;
    q->k = k;
    return q;
}

判断环队为空

1
2
3
c复制代码bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail;
}

判断环队为满

1
2
3
c复制代码bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1) == obj->front;
}

环队入数据并入成功返回真

1
2
3
4
5
6
7
8
9
10
c复制代码bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(!myCircularQueueIsFull(obj))
    {
        obj->a[obj->tail] = value;//不是队满就下标tail的数据为value
        obj->tail++;
        obj->tail %= obj->k+1;//tail就步进一位
        return true;
    }
    return false;//队满就插不进去了
}

环队删数据并删成功返回真

1
2
3
4
5
6
7
8
9
c复制代码bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {
        obj->front++;//队不空就是出队，头标步进就行了
        obj->front %= obj->k+1;
        return true;
    }
    return false;//对空就删不了了
}

环队取队头数据（对空返回-1）

1
2
3
4
5
6
7
c复制代码int myCircularQueueFront(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {
        return obj->a[obj->front]; //取front位置的数据就行       
    }
    return -1;
}

环队取队尾数据（对空返回-1）

1
2
3
4
5
6
7
c复制代码int myCircularQueueRear(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {        
        return obj->a[obj->tail == 0 ? obj->k : obj->tail-1];//取tail前一个数据就行，tail为0，前一个就是k位置数据      
    }
    return -1;
}

环队销毁

1
2
3
4
5
6
7
8
c复制代码void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->a = NULL;
    obj->front = 0;
    obj->tail = 0;
    obj->k = 0;
    free(obj);
}

image-20211104220502511

image-20211104220526761

环队（数组实现）

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
c复制代码typedef struct {
    int* a;
    int front;
    int tail;
    int k;//数组元素(队列长度)
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a = (int*)malloc(sizeof(int)*(k+1));//队列长度为k我们要多开一个
    q->front = q->tail = 0;
    q->k = k;
    return q;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(!myCircularQueueIsFull(obj))
    {
        obj->a[obj->tail] = value;//不是队满就下标tail的数据为value
        obj->tail++;
        obj->tail %= obj->k+1;//tail就步进一位
        return true;
    }
    return false;//队满就插不进去了
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {
        obj->front++;//队不空就是出队，头标步进就行了
        obj->front %= obj->k+1;
        return true;
    }
    return false;//对空就删不了了
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {
        return obj->a[obj->front]; //取front位置的数据就行       
    }
    return -1;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {        
        return obj->a[obj->tail == 0 ? obj->k : obj->tail-1];//取tail前一个数据就行，tail为0，前一个就是k位置数据      
    }
    return -1;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1) == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->a = NULL;
    obj->front = 0;
    obj->tail = 0;
    obj->k = 0;
    free(obj);
}

链表形式

环队结构体（链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
c复制代码typedef int CQDataType;//环队数据类型

typedef struct CQNode
{
    CQDataType x;//环队节点数据
    struct CQNode* next;//环队节点指针
}CQNode;

typedef struct {
    CQNode* head;
    CQNode* tail;
    int k;
} MyCircularQueue;//空环队就两个裸指针

环队初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c复制代码MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CQNode* cur = (CQNode*)malloc(sizeof(CQNode));
    cq->k = k;
    cq->head = cq->tail = cur;
    while(k--)
    {
        CQNode* newnode = (CQNode*)malloc(sizeof(CQNode));
        CQNode* tail = cq->tail;//最后一个节点
	    tail->next = newnode;//最后一个节点指向新的节点
	    newnode->next = cq->head;//新的节点指向头节点
        cq->tail=newnode;
    }
    cq->head = cq->tail;
    return cq;
}

判断环队为空

1
2
3
4
c复制代码bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    return obj->head == obj->tail;
}

判断环队为满

1
2
3
4
c复制代码bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    return obj->tail->next == obj->head;
}

环队入数据并入成功返回真

1
2
3
4
5
6
7
8
9
10
c复制代码bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsFull(obj))
    {
        obj->tail->x = value;
        obj->tail = obj->tail->next;
        return true;
    }
    return false;
}

环队删数据并删成功返回真

1
2
3
4
5
6
7
8
9
c复制代码bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsEmpty(obj))
    {
        obj->head = obj->head->next;
        return true;
    }
    return false;
}

环队取队头数据（对空返回-1）

1
2
3
4
5
6
c复制代码int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsEmpty(obj))
        return obj->head->x;
    return -1;
}

环队取队尾数据（对空返回-1）

1
2
3
4
5
6
7
8
9
10
11
12
13
c复制代码int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsEmpty(obj))
    {
        CQNode*ret=obj->head;
        while(ret->next!=obj->tail)
        {
            ret=ret->next;
        }
        return ret->x;
    }
    return -1;    
}

环队销毁

1
2
3
4
5
6
7
8
9
10
11
c复制代码void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    while(obj->head!=obj->tail)
    {
        CQNode*ret=obj->tail;
        obj->tail=obj->tail->next;
        free(ret);
    }
    free(obj->head);
    free(obj);
}

image-20211105064130129

环队（链表实现）

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
c复制代码typedef int CQDataType;//环队数据类型

typedef struct CQNode
{
    CQDataType x;//环队节点数据
    struct CQNode* next;//环队节点指针
}CQNode;

typedef struct {
    CQNode* head;
    CQNode* tail;
    int k;
} MyCircularQueue;//空环队就两个裸指针

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CQNode* cur = (CQNode*)malloc(sizeof(CQNode));
    cq->k = k;
    cq->head = cq->tail = cur;
    while(k--)
    {
        CQNode* newnode = (CQNode*)malloc(sizeof(CQNode));
        CQNode* tail = cq->tail;//最后一个节点
	    tail->next = newnode;//最后一个节点指向新的节点
	    newnode->next = cq->head;//新的节点指向头节点
        cq->tail=newnode;
    }
    cq->head = cq->tail;
    return cq;
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsFull(obj))
    {
        obj->tail->x = value;
        obj->tail = obj->tail->next;
        return true;
    }
    return false;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsEmpty(obj))
    {
        obj->head = obj->head->next;
        return true;
    }
    return false;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsEmpty(obj))
        return obj->head->x;
    return -1;
}

/*int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsEmpty(obj))
    {
        CQNode* ret = obj->head;//这个ret 是用来找tail前一个的，不可用直接返回tail，会改变原来环队的链接关系
        while(--obj->k)
        {
           obj->tail = obj->tail->next;
        }        
        ret = obj->tail;
        obj->tail = obj->tail->next;
        return obj->tail->x;
    }
    return -1;    
}*/
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(!myCircularQueueIsEmpty(obj))
    {
        CQNode*ret=obj->head;
        while(ret->next!=obj->tail)
        {
            ret=ret->next;
        }
        return ret->x;
    }
    return -1;    
}


bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    return obj->tail->next == obj->head;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    while(obj->head!=obj->tail)
    {
        CQNode*ret=obj->tail;
        obj->tail=obj->tail->next;
        free(ret);
    }
    free(obj->head);
    free(obj);
}

实际上这题我报错我不想找了太恶心了（家凌帮我找错的非常感谢）

img

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%