Introductions to the 0.

Queues are characterized by first-movers, first-movers. There are only two basic queueing operations: enqueue(), putting data at the end of the queue; Dequeue (), fetching an element from the head of the queue. Like the stack, it is a linear table data structure with limited operations. Queues can be implemented as arrays or as linked lists. The queue implemented by array is called sequence queue, and the queue implemented by list is called chain queue. If the size of the queue is predetermined, an array is usually used. If the size of the queue is uncertain in advance, a chained queue is usually used.

1. Implement queues with arrays

First, the data structure of the queue with an array is as follows:

typedef struct tagarray_queue { int capacity; // Queue size int head; // Int tail; Int *data; // Int *data; // Array_queue;Copy the code

There are two important points to note here: (1) We assume that the data stored here is of type int, but in fact in the actual development process is not int. (2) Note the meaning of tail: the position next to the end of the queue.

First, create a queue:

array_queue *create_queue(int size) {
    if (size <= 0) {
        return NULL;
    }
    array_queue *queue = (array_queue *)malloc(sizeof(array_queue));
    if (queue == NULL) {
        return NULL;
    }
    queue->data = (int *)malloc(size * sizeof(int));
    if (queue->data == NULL) {
        free(queue);
        queue = NULL;
        return NULL;
    }
    queue->head = 0;
    queue->tail = 0;
    queue->capacity = size;
    return queue;
}
Copy the code

In this case, the parameter size passed to create_queue is the size of the array, that is, the size of the queue. At first, the head and tail of the queue both point to the 0th position in the array.

Second, we need to queue operations:

Int enqueue(array_queue *queue, int data) { Return 1 if ((queue = = NULL) | | (queue - > tail = = queue - > capacity)) {return ERR; } queue->data[queue->tail++] = data; return OK; }Copy the code

The first judgment is made on the queue: if the queue is full, it simply fails. Otherwise, add the data at the subscript tail, and tail++.

Finally, there is a need for team operation:

Int dequeue(array_queue *queue, int *data) { It returns an error if the ((queue = = NULL) | | (data = = NULL) | | (queue - > head = = queue - > tail)) {return ERR; } (*data) = queue->head; queue->head++; return OK; }Copy the code

In this case, dequeue takes two arguments, of which data is an outbound parameter, which is used to store data out of the queue. The dequeuing operation also makes a judgment first: if the queue is empty, it directly returns failure. Otherwise, pass the team head to DATA and the team head ++. The complete code can be found in Appendix 1.

1.1 improve

There is a problem with the above code implementation: as you continue to queue in and queue out, both head and tail move back. When tail is moved to the far right, it is no longer possible to add data to the queue even if there is free space in the array. This is a huge waste of memory. To solve this problem, data needs to be moved. When data is added to the queue at the end of the tail, if there is still free space, data needs to be moved once. So, for the exit function to remain unchanged, we need to change the implementation of the entry function. The specific code is as follows:

Int enqueue(array_queue *queue, int data) {if (queue == NULL) {return ERR; } if (queue->head == queue->size) {if (queue->head == 0) {return ERR; } int i; int baseIndex = queue->head; for (i = queue->head; i < queue->tail; i++) { queue->data[i - baseIndex]; } queue->tail -= baseIndex; queue->head = 0; } queue->data[queue->tail++] = data; return OK; }Copy the code

2. Circular queue

In the array-based queue implementation above, data is moved when tail == capacity, which results in performance degradation for enqueueing operations. To avoid data migration, circular queues can be used.

Here’s what to understand about circular queues:

1. Pseudo algorithm of circular queue entry

• Store the value where tail is
• tail = (tail + 1) % capacity

2. Pseudo-algorithm of circular queue dequeuing:

• Save the team value first
• head = (head + 1) % capacity

3. Determines whether the circular queue is empty

• head == tail

4. Determines whether the circular queue is full

As shown in the figure, suppose the array size is 7 and the queue has already put data 1,2,3,4,5,6. If you put one more piece of data, then head == tail, which is the same as the above condition to determine whether the circular queue is empty. There is no way to tell whether the queue is empty or full. So just to differentiate, we don’t use the last storage space. (tail + 1) % capacity == head) (tail + 1) % capacity == head In this case, the tail of the circular queue actually stores no data. So it’s going to waste an array.

And the reason why WE’re mod capacity here is because now tail = capacity -1 and head = 0. Tail + 1 = capacity. (tail + 1) % capacity = capacity % capacity = 0) The complete code implementation can be found in Appendix 2.

Of course, this is just one way to tell if a circular list is empty. Here’s another way: define an additional value, size, for the current array size. So the condition that the queue is full is that the size of the current queue is equal to the size of the array. So I don’t waste the last space of the array. It’s also easier to understand. (Of course, in this case, the data type is an int, I have an int parameter size, and it’s the same as without the last space. However, when the data type is not an int, but the size is larger than an int, the following implementation saves more memory.

typedef struct { int capacity; // The size of the queue array; // The size of the current queue array; // Int tail; Int *data; // Int *data; // Array} MyCircularQueue;Copy the code

For specific implementation, please refer to Appendix 3.

3. Implement the queue with a linked list

Queues implemented with linked lists do not have a full queue. The data structure of a queue implemented with a linked list is as follows. Again, we need two Pointers head and tail. Head points to the first node of the list, and tail points to the last node of the list. To join the queue, tail->next = new_node, tail = tail->next. Head = head->next. See Appendix 4 for specific implementation.

typedef struct tagQueue_node { int data; struct tagQueue_node *next; } queue_node; typedef struct tagList_queue { int num; // The number of current elements queue_node *head; queue_node *tail; } list_queue;Copy the code

4. Channel in Golang

Those of you who know the Go language know that a channel is a way of communicating between Goroutines provided by Golang at the language level. If you read the source code, you’ll see that the underlying data structure of a channel uses queues. Here are two blogs that examine the underlying data structure of a channel. I recommend you to check it out:

1. “Go Expert programming” Go Channel implementation principle analysis

2. Illustrate the channel underlying principle of Go

5. References

1. Blog.csdn.net/lpp09003201…
2. Time.geekbang.org/column/arti…

Appendix 1: Array C implementation of queues

#ifndef ARRAY_QUEUE_H #define ARRAY_QUEUE_H #define OK 0 #define ERR 1 typedef struct tagarray_queue { int capacity; // Queue size int head; // Int tail; Int *data; // Int *data; // Array_queue; #include <stdlib.h> #include <stdio.h> #include "array_queue.h" array_queue *create_queue(int size) { if (size <= 0) { return NULL; } array_queue *queue = (array_queue *)malloc(sizeof(array_queue)); if (queue == NULL) { return NULL; } queue->data = (int *)malloc(size * sizeof(int)); if (queue->data == NULL) { free(queue); queue = NULL; return NULL; } queue->head = 0; queue->tail = 0; queue->capacity = size; return queue; Int enqueue(array_queue *queue, int data) { Return 1 if ((queue = = NULL) | | (queue - > tail = = queue - > capacity)) {return ERR; } queue->data[queue->tail++] = data; return OK; Int dequeue(array_queue *queue, int *data) { It returns an error if the ((queue = = NULL) | | (data = = NULL) | | (queue - > head = = queue - > tail)) {return ERR; } (*data) = queue->head; queue->head++; return OK; } void destory_queue(array_queue *queue) {if (queue == NULL) {return; } if (queue->data ! = NULL) { free(queue->data); queue->data = NULL; } free(queue); return; Void print_queue(array_queue *queue) {printf("\n\n"); if (queue == NULL) { printf("\nqueue is NULL."); return; } printf("\n size:%d,head:%d, tail:%d.", queue->capacity, queue->head, queue->tail); int i; for (i = queue->head; i < queue->tail; i++) { printf("\n\t array[%d]:%d",i, queue->data[i]); } return; } int main() { int size = 4; array_queue *queue = create_queue(size); if (queue == NULL) { printf("\n queue create fail."); return ERR; } // Error is returned when the queue is empty int data = 0; int ret = dequeue(queue, &data); if (ret ! = OK) { printf("\n dequeue failed."); } int i; For (I = 0; i < size + 1; i++) { ret = enqueue(queue, i); if (ret ! = OK) { printf("\n queue %d enqueue failed.", i); } // Print_queue (queue); ret = dequeue(queue, &data); if (ret ! = OK) { printf("\n dequeue failed."); } print_queue(queue); ret = dequeue(queue, &data); if (ret ! = OK) { printf("\n dequeue failed."); } print_queue(queue); ret = dequeue(queue, &data); if (ret ! = OK) { printf("\n dequeue failed."); } print_queue(queue); ret = dequeue(queue, &data); if (ret ! = OK) { printf("\n dequeue failed."); } print_queue(queue); ret = enqueue(queue, 9); if (ret ! = OK) { printf("\n queue 9 enqueue failed."); } print_queue(queue); ret = enqueue(queue, 10); if (ret ! = OK) { printf("\n queue 10 enqueue failed."); } print_queue(queue); destory_queue(queue); return OK; }Copy the code

Appendix 2: C implementation of circular queue

Int enqueue(array_queue *queue, int data) {if (array_queue == NULL) {return ERR; } if ((queue->tail + 1) % queue->capacity == queue->head) { printf("\ntail:%d, capacity:%d, head:%d", queue->tail, queue->capacity, queue->head); return ERR; } queue->data[queue->tail] = data; queue->tail = (queue->tail + 1) % queue->capacity; return OK; } dequeue(array_queue *queue, int *data) { It returns an error if the ((queue = = NULL) | | (data = = NULL) | | (queue - > head = = queue - > tail)) {return ERR; } (*data) = queue->head; queue->head = (queue->head + 1) % queue->capacity; return OK; Void print_queue(array_queue *queue) {printf("\n\n"); if (queue == NULL) { printf("\nqueue is NULL."); return; } printf("\n capacity:%d,head:%d, tail:%d.", queue->capacity, queue->head, queue->tail); int i; if (queue->head < queue->tail) { for (i = queue->head; i < queue->tail; i++) { printf("\n\t array[%d]:%d",i, queue->data[i]); } } else { for (i = queue->head; i < queue->capacity; i++) { printf("\n\t array[%d]:%d",i, queue->data[i]); } for (i = 0; i < queue->tail; i++) { printf("\n\t array[%d]:%d",i, queue->data[i]); } } return; }Copy the code

Appendix 3: C implementation of circular queues with length

Designing circular queues

typedef struct { int capacity; // The size of the queue array; // The size of the current queue array; // Int tail; Int *data; // Int *data; // Array} MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue *queue = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); if (queue == NULL) { return NULL; } queue->size = 0; queue->head = 0; queue->tail = 0; queue->capacity = k; queue->data = (int *)malloc(sizeof(int) * k); return queue; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (obj->size == obj->capacity) { return false; } obj->data[obj->tail] = value; obj->tail = (obj->tail + 1) % (obj->capacity); // obj = 0 obj->size++; // obj = 0 obj->size++; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (obj->size == 0) { return false; } obj->head = (obj->head + 1) % (obj->capacity); obj->size--; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (obj->size == 0) { return -1; } return obj->data[obj->head]; } int myCircularQueueRear(MyCircularQueue* obj) { if (obj->size == 0) { return -1; } return obj->data[(obj->tail - 1 + obj->capacity) % (obj->capacity)]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return (obj->size == 0) ? true :false; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->size == obj->capacity) ? true : false; } void myCircularQueueFree(MyCircularQueue* obj) { if (obj == NULL) { return; } free(obj->data); obj->data = NULL; free(obj); return; }Copy the code

Appendix 4: Queue list C language implementation

// list_queue.h #ifndef LIST_QUEUE_H #define LIST_QUEUE_H #define OK 0 #define ERR 1 typedef struct tagQueue_node { int data; struct tagQueue_node *next; } queue_node; typedef struct tagList_queue { int num; // The number of current elements queue_node *head; queue_node *tail; } list_queue; #endif // list_queue.c #include <stdlib.h> #include <stdio.h> #include <stdbool.h> #include "list_queue.h" #include <pthread.h> bool list_queue_is_empty(list_queue *queue) {return queue->num == 0; } list_queue *list_queue_create() {list_queue *queue = (list_queue *)malloc(sizeof(list_queue)); if (queue == NULL) { return NULL; } queue->num = 0; queue->head = NULL; queue->tail = NULL; return queue; Int list_queue_enqueue(list_queue *queue, int data) {if (queue == NULL) {printf("enqueue fail, queue is NUll.\n"); return ERR; } queue_node *tmp = (queue_node *)malloc(sizeof(queue_node)); if (tmp == NULL) { printf("enqueue fail, malloc queue_node fail.\n"); return ERR; } tmp->data = data; tmp->next = NULL; if (queue->head == NULL) { queue->head = tmp; } else { queue->tail->next = tmp; } queue->tail = tmp; queue->num++; return OK; Int list_queue_dequeue(list_queue *queue, list_queue *queue, int *data) { if (queue == NULL) { printf("dequeue fail. queue is NULL.\n"); return ERR; } if (list_queue_is_empty(queue)) { printf("dequeue fail. queue is empty.\n"); return ERR; } queue_node *tmp = queue->head; (*data) = queue->head->data; queue->head = queue->head->next; queue->num--; if (queue->head == NULL) { queue->tail = NULL; } free(tmp); return OK; Void list_queue_destory(list_queue *queue) {if (queue == NULL) {return; } int data = 0; while (! list_queue_is_empty(queue)) { (void)list_queue_dequeue(queue, &data); } free(queue); return; Void list_queue_print(list_queue *queue) {if (queue == NULL) {return; } printf("print queue: num:%d: ", queue->num); queue_node *tmp = queue->head; while (tmp ! = NULL) { printf("%d ", tmp->data); tmp = tmp->next; } printf("\n\n"); return; } int main() { list_queue *queue = list_queue_create(); if (queue == NULL) { return ERR; } int i; int num = 6; int data = 0; for (i = 0; i < num; i++) { (void)list_queue_enqueue(queue, i); } list_queue_print(queue); int ret = list_queue_dequeue(queue, &data); if (ret ! = OK) { return ret; } printf("dequeue number is %d.\n", data); list_queue_print(queue); ret = list_queue_dequeue(queue, &data); if (ret ! = OK) { return ret; } printf("dequeue number is %d.\n", data); list_queue_print(queue); list_queue_destory(queue); return OK; }Copy the code