C/C++ FIFO queue - 先进先出队列

爱被打了一巴掌 2022-11-02 09:07 148阅读 0赞

# **C/C++ FIFO queue - 先进先出队列** #

队列是一种特殊的线性表，只允许在表的前端 (front) 进行删除操作，而在表的后端 (rear) 进行插入操作。队列和栈都是操作受限制的线性表。队列中没有元素时，称为空队列。

进行插入操作的端称为队尾 - rear - tail - insert  
进行删除操作的端称为队头 - front - head - delete

在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出 (FIFO，first in first out) 线性表。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

## 1. C/C++ FIFO queue ##

实现 1  
取出第一个数据，后面的数据向前移动 (队首位置不会改变)。思想简单，但是效率低。  
![在这里插入图片描述][20210225021140729.png_pic_center]  
实现 2  
记录队首和队尾位置。效率高，但是占用内存较大。  
![在这里插入图片描述][20210225021150165.png_pic_center]  
实现 3 - 循环队列  
将数组当做一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲。如果空闲，则在数组头部进行插入。效率高，内存固定，但是思想较复杂。  
![在这里插入图片描述][20210225021157361.png_pic_center]

## 2. 带头节点的双向循环链表实现队列 (FIFO queue) ##

//============================================================================
    // Name        : FIFO queue - doubly linked list
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2019 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #ifndef _CRT_SECURE_NO_WARNINGS
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    #define MAX_NODE_LEN 401
    #define NULL 0
    
    #include <stdio.h>
    
    typedef struct NODE {
    	int data;
    	struct NODE *prev;
    	struct NODE *next;
    } Node;
    
    typedef struct QUEUE {
    	struct NODE head;
    	int count;
    } Queue;
    
    Node node_array[MAX_NODE_LEN];
    int node_array_idx = 0;
    
    void insert_first(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    
    	// equality: head->next->prev = node;
    	node->next->prev = node;
    	head->next = node;
    }
    
    void delete_node(const Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	// current node - node
    
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    void delete_node_v1(const Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    void delete_node_v2(Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    
    	node->prev = node->next = node;
    }
    
    void init_queue(Queue *queue)
    {
    	(queue->head).prev = (queue->head).next = &(queue->head);
    	queue->count = 0;
    }
    
    void in_queue(Queue *queue, Node *node)
    {
    	insert_first(&(queue->head), node);
    	queue->count += 1;
    }
    
    Node* out_queue(Queue *queue)
    {
    	if (queue->count <= 0)
    	{
    		return NULL;
    	}
    
    	Node *ret = (queue->head).prev;
    	delete_node(ret);
    	queue->count -= 1;
    
    	return ret;
    }
    
    void display(const Node *head)
    {
    	int n = 1;
    
    	Node *node = head->next;
    	while (node != head)
    	{
    		printf("node %d: %d\n", n, node->data);
    		++n;
    		node = node->next;
    	}
    }
    
    void display_v1(const Node *head)
    {
    	int n = 1;
    
    	Node *node = head->prev;
    	while (node != head)
    	{
    		printf("node %d: %d\n", n, node->data);
    		++n;
    		node = node->prev;
    	}
    }
    
    int main()
    {
    	// 头节点 (非头指针)
    	Queue queue_data;
    
    	init_queue(&queue_data);
    
    	for (int i = 0; i < MAX_NODE_LEN; ++i)
    	{
    		node_array[i].prev = NULL;
    		node_array[i].next = NULL;
    		node_array[i].data = 0;
    	}
    
    	// insert 0
    	node_array[0].data = 0;
    	in_queue(&queue_data, &(node_array[0]));
    
    	// insert 2
    	node_array[2].data = 2;
    	in_queue(&queue_data, &(node_array[2]));
    
    	// insert 4
    	node_array[4].data = 4;
    	in_queue(&queue_data, &(node_array[4]));
    
    	// insert 6
    	node_array[6].data = 6;
    	in_queue(&queue_data, &(node_array[6]));
    
    	// insert 8
    	node_array[8].data = 8;
    	in_queue(&queue_data, &(node_array[8]));
    
    	display(&(queue_data.head));
    	printf("node number = %d\n", queue_data.count);
    
    	// insert 10
    	node_array[10].data = 10;
    	in_queue(&queue_data, &(node_array[10]));
    	printf("\ninqueue data %d:\n", 10);
    
    	display(&(queue_data.head));
    	printf("node number = %d\n", queue_data.count);
    
    	for (int i = 0; i < 4; ++i) {
    		Node *node = out_queue(&queue_data);
    		if (node != NULL)
    		{
    			printf("\noutqueue data = %d\n", node->data);
    		}
    
    		display(&(queue_data.head));
    		printf("node number = %d\n", queue_data.count);
    	}
    
    	// insert 12
    	node_array[12].data = 12;
    	in_queue(&queue_data, &(node_array[12]));
    	printf("\ninqueue data %d:\n", 12);
    
    	display(&(queue_data.head));
    	printf("node number = %d\n", queue_data.count);
    
    	// insert 14
    	node_array[14].data = 14;
    	in_queue(&queue_data, &(node_array[14]));
    	printf("\ninqueue data %d:\n", 14);
    
    	display(&(queue_data.head));
    	printf("node number = %d\n", queue_data.count);
    
    	// insert 16
    	node_array[16].data = 16;
    	in_queue(&queue_data, &(node_array[16]));
    	printf("\ninqueue data %d:\n", 16);
    
    	display(&(queue_data.head));
    	printf("node number = %d\n", queue_data.count);
    
    	for (int i = 0; i < 2; ++i) {
    		Node *node = out_queue(&queue_data);
    		if (node != NULL)
    		{
    			printf("\noutqueue data = %d\n", node->data);
    		}
    
    		display(&(queue_data.head));
    		printf("node number = %d\n", queue_data.count);
    	}
    
    	// insert 18
    	node_array[18].data = 18;
    	in_queue(&queue_data, &(node_array[18]));
    	printf("\ninqueue data %d:\n", 18);
    
    	display(&(queue_data.head));
    	printf("node number = %d\n", queue_data.count);
    
    	return 0;
    }

node 1: 8
    node 2: 6
    node 3: 4
    node 4: 2
    node 5: 0
    node number = 5
    
    inqueue data 10:
    node 1: 10
    node 2: 8
    node 3: 6
    node 4: 4
    node 5: 2
    node 6: 0
    node number = 6
    
    outqueue data = 0
    node 1: 10
    node 2: 8
    node 3: 6
    node 4: 4
    node 5: 2
    node number = 5
    
    outqueue data = 2
    node 1: 10
    node 2: 8
    node 3: 6
    node 4: 4
    node number = 4
    
    outqueue data = 4
    node 1: 10
    node 2: 8
    node 3: 6
    node number = 3
    
    outqueue data = 6
    node 1: 10
    node 2: 8
    node number = 2
    
    inqueue data 12:
    node 1: 12
    node 2: 10
    node 3: 8
    node number = 3
    
    inqueue data 14:
    node 1: 14
    node 2: 12
    node 3: 10
    node 4: 8
    node number = 4
    
    inqueue data 16:
    node 1: 16
    node 2: 14
    node 3: 12
    node 4: 10
    node 5: 8
    node number = 5
    
    outqueue data = 8
    node 1: 16
    node 2: 14
    node 3: 12
    node 4: 10
    node number = 4
    
    outqueue data = 10
    node 1: 16
    node 2: 14
    node 3: 12
    node number = 3
    
    inqueue data 18:
    node 1: 18
    node 2: 16
    node 3: 14
    node 4: 12
    node number = 4
    请按任意键继续. . .

## References ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/1800c7b7d9614faf964d949bcdd5bd4b.png
[20210225021140729.png_pic_center]: /images/20221024/5ee6df8f3eaa4e8f945c9e1111041a08.png
[20210225021150165.png_pic_center]: /images/20221024/3f495a33d99c48c9b5ba260479ee2150.png
[20210225021157361.png_pic_center]: /images/20221024/fc61c4c3ce4d46ef94dafce93fde64b4.png