数据结构-队

Posted on | In |

基本操作

描述：FIFO（先进先出）

只允许栈顶进行删除和插入

  • 创建
  • 销毁
  • 是否满
  • 是否空
  • 入队
  • 出队
  • 遍历

实现

顺序队
1
2
3
4
5
6
7
8
9
10
11
//队数据
typedef struct array_queue
{
    int size;//队列大小
    int num; //数据多少
    int head;//队头
    int tail;//队尾
    int *array;//数据存储区
}ArrayQueue;

void test(void);
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <stdbool.h>
#include <stdlib.h>

/**
 队是否空

 @param queue 队
 @return 是否空
 */
bool array_queue_is_empty(ArrayQueue *queue)
{
    return queue->num == 0;
}

/**
 队是否满

 @param queue 队
 @return 是否满
 */
bool array_queue_is_full(ArrayQueue *queue)
{
    return queue->num == queue->size;
}

/**
创建队
 
 @param size 队大小
 @return 队
 */
ArrayQueue *array_queue_create(int size)
{
    ArrayQueue *queue = (ArrayQueue *)malloc(sizeof(ArrayQueue));
    if (queue == NULL) {
        return NULL;
    }
    
    queue->array = (int *)malloc(sizeof(int) * size);
    if (queue->array == NULL) {
        free(queue);
        return NULL;
    }
    
    queue->size = size;
    queue->num = 0;
    queue->head = 0;
    queue->tail = 0;
    
    return queue;
}

/**
 销毁队

 @param queue 队
 */
void array_queue_destory(ArrayQueue *queue)
{
    if (queue == NULL) {
        return;
    }
    
    if (queue->array != NULL) {
        free(queue->array);
    }
    
    free(queue);
}

/**
 入队

 @param queue dui
 @param data 入队数据
 @return 是否入队成功
 */
int array_queue_enqueue(ArrayQueue *queue, int data)
{
    if ((queue == NULL) || array_queue_is_full(queue)) {
        return -1;
    }
    
    queue->num++;
    queue->array[queue->tail] = data;
    queue->tail = (queue->tail + 1) % queue->size;
    
    return 0;
}

/**
 出队

 @param queue 队
 @param data 出队数据
 @return 是否出队成功
 */
int array_queue_dequeue(ArrayQueue *queue, int *data)
{
    if ((queue == NULL) || (data == NULL) || array_queue_is_empty(queue)) {
        return -1;
    }
    
    *data = queue->array[queue->head];
    queue->num--;
    queue->head = (queue->head + 1) % queue->size;
    
    return 0;
}

/**
 队遍历

 @param queue 队
 */
void array_queue_dump(ArrayQueue *queue)
{
    if ((queue == NULL) || (array_queue_is_empty(queue))) {
        return;
    }
    
    printf("size:%d,num:%d,head:%d,tail:%d\n",queue->size, queue->num, queue->head, queue->tail);
    for (int i = 0; i < queue->num; i++) {
        int pos = (queue->head + i) % queue->size;
        printf("array[%d] = %d\n", pos, queue->array[pos]);
    }
}

/**
 测试
 */
void test()
{
    ArrayQueue *queue = array_queue_create(4);
    if (queue == NULL) {
        return;
    }
    
    int data = 0;
    int ret = array_queue_dequeue(queue, &data);
    if (ret != 0) {
        printf("出栈失败 %d\n",ret);
    }
    
    for (int i = 0; i < 5; i++) {
        int ret = array_queue_enqueue(queue, i);
        if (ret != 0) {
            printf("入栈失败 %d\n", ret);
        }
    }
    
    array_queue_dump(queue);
    
    data = 0;
    ret = array_queue_dequeue(queue, &data);
    if (ret != 0) {
        printf("出栈失败 %d\n",ret);
    }
    
    printf("data = %d\n",data);
    
    array_queue_dump(queue);
    
    data = 5;
    ret = array_queue_enqueue(queue, data);
    if (ret != 0) {
        printf("入栈失败 %d\n", data);
    }
    array_queue_dump(queue);
    
    array_queue_destory(queue);
}
链队
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
#include <stdio.h>
#include <stdbool.h>
/*
 不带头结点
 */

typedef struct link_queue_node
{
    int data;
    struct link_queue_node *next;
}LinkQueueNode;

typedef struct link_queue
{
    int num;
    LinkQueueNode *head;
    LinkQueueNode *tail;
}LinkQueue;

/**
 队是否空
 
 @param queue 队
 @return 是否空
 */
bool link_queue_is_empty(LinkQueue *queue);

/**
 队长度
 
 @param queue 队
 @return 长度
 */
int link_queue_length(LinkQueue *queue);

/**
 创建队
 
 @return 队
 */
LinkQueue *link_queue_create(void);

/**
 入队
 
 @param queue 队
 @param data 入队数据
 @return 是否出入成功
 */
int link_queue_enqueue(LinkQueue *queue, int data);

/**
 出队
 
 @param queue 队
 @param data 出队数据
 @return 是否出队成功
 */
int link_queue_dequeue(LinkQueue *queue, int *data);

/**
 销毁队
 
 @param queue 队
 */
void link_queue_destroy(LinkQueue *queue);

/**
 队遍历
 
 @param queue 队
 */
void link_queue_dump(LinkQueue *queue);

void test(void);
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <stdbool.h>
#include <stdlib.h>

/**
 队是否空
 
 @param queue 队
 @return 是否空
 */
bool link_queue_is_empty(LinkQueue *queue)
{
    return queue->num == 0;
}

/**
 队长度

 @param queue 队
 @return 长度
 */
int link_queue_length(LinkQueue *queue)
{
    return queue->num;
}

/**
 创建队
 
 @return 队
 */
LinkQueue *link_queue_create()
{
    LinkQueue *queue = (LinkQueue *)malloc(sizeof(LinkQueue));
    if (queue == NULL) {
        return NULL;
    }
    
    queue->num = 0;
    queue->head = NULL;
    queue->tail = NULL;
    
    return queue;
}

/**
 入队
 
 @param queue 队
 @param data 入队数据
 @return 是否出入成功
 */
int link_queue_enqueue(LinkQueue *queue, int data)
{
    if (queue == NULL) {
        return -1;
    }
    
    LinkQueueNode *temp = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    if (temp == NULL) {
        return -1;
    }
    
    temp->data = data;
    temp->next = NULL;
    if (queue->head == NULL) {
        queue->head = temp;
    }
    else {
        queue->tail->next = temp;
    }
    queue->tail = temp;
    queue->num++;
    
    return 0;
}

/**
 出队
 
 @param queue 队
 @param data 出队数据
 @return 是否出队成功
 */
int link_queue_dequeue(LinkQueue *queue, int *data)
{
    if ((queue == NULL) || (data == NULL) || link_queue_is_empty(queue)) {
        return -1;
    }
    
    *data = queue->head->data;
    LinkQueueNode *temp = queue->head;
    queue->head = queue->head->next;
    queue->num--;
    
    if (queue->head == NULL) {
        queue->tail = NULL;
    }
    
    free(temp);
    
    return 0;
}

/**
 销毁队
 
 @param queue 队
 */
void link_queue_destroy(LinkQueue *queue)
{
    if ((queue == NULL) || link_queue_is_empty(queue)) {
        return;
    }
    
    int data = 0;
    while (!link_queue_is_empty(queue)) {
        link_queue_dequeue(queue, &data);
    }
    free(queue);
}

/**
 队遍历
 
 @param queue 队
 */
void link_queue_dump(LinkQueue *queue)
{
    if ((queue == NULL) || link_queue_is_empty(queue)) {
        return;
    }
    
    LinkQueueNode *temp = queue->head;
    printf("num = %d\n", queue->num);
    
    int i = 0;
    while (temp != NULL) {
        printf("node[%d] = %d\n",i, temp->data);
        i++;
        temp = temp->next;
    }
}


/**
 测试
 */
void test()
{
    LinkQueue *queue = link_queue_create();
    if (queue == NULL) {
        printf("创建失败\n");
        return;
    }
    
    for (int i = 0; i < 5; i++) {
        link_queue_enqueue(queue, i);
    }
    link_queue_dump(queue);
    
    int data = 0;
    int ret = link_queue_dequeue(queue, &data);
    if (ret != 0) {
        printf("出栈失败 %d", data);
    }
    printf("data = %d\n", data);
    link_queue_dump(queue);
    
    ret = link_queue_dequeue(queue, &data);
    if (ret != 0) {
        printf("出栈失败 %d", data);
    }
    printf("data = %d\n", data);
    link_queue_dump(queue);
    
    link_queue_enqueue(queue, data);
    link_queue_dump(queue);
}

当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？

我们一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求

另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。

那如何存储排队的请求呢？

我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求

队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢？

基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。

针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。

而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。