【數據結構&演算法】09-隊列概念&參考源碼
- 2021 年 11 月 9 日
- 筆記
- /label/dataStructure, /label/lzm, 書籍筆記, 博文, 教程集合, 數據結構, 數據結構與演算法, 演算法, 線性表
前言
李柱明部落格：//www.cnblogs.com/lizhuming/p/15487349.html
隊列的定義
隊列（queue）– 只允許在一端進行插入操作，而在另一端進行刪除操作的線性表：
- FIFO：先進先出的線性表。
- 允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。
注意：隊列同樣是線性表，也有類似線性表的各種操作。只是插入只能在隊尾，刪除只能在隊頭。
隊列的抽象數據類型
隊列的抽象數據類型可由兩種實現：
- 順序隊列：由數組或指針實現。
- 鏈式隊列：由鏈表是實現。
循環隊列與鏈式隊列對比
時間上：都是 O(1)。
空間上：
- 循環隊列：事先申請好空間，使用期間不釋放。
- 鏈隊列：每次申請和釋放結點也會存在一些時間開銷。
- 循環隊列：固定長度，故存在存儲元素個數和空間浪費的問題。
- 鏈隊列：需要指針域，產生一些空間上的開銷，在空間上更靈活。
循環隊列
特點
循環隊列由數組實現。但是數組是有局限性的，所以循環隊列有以下特點：
-
當隊頭固定設為數組下標為 0 的位置時：入隊 O(1)，但出隊 O(n)。
-
當不限制隊頭必須在數組下標為 0 的位置時，可以提高一些性能。
- 需要引入兩個下標。對頭和隊尾。
-
採用游標&循環方式：
- 引入兩個指針，隊頭和隊尾。
- 循環方式，即是如隊尾溢出時便調到數組頭繼續。
定義
循環隊列的定義：
-
隊列的頭尾相接的順序存儲結構稱為循環隊列。
- 可以理解為數組尾就是數組頭，把頭尾接駁。
循環隊列相關計算
計算：
-
隊列 size：queue_size
-
隊列空判斷：head == tail
-
隊列長度計算：(tail – head + QueueSize) % queue_size
-
隊列滿判斷：head == (tail + 1) % queue_size
- 整個隊列需要保留一個空的元素。
-
入隊：tail = (tail + 1) % queue_size
-
出隊：head = (head +1) % queue_size
鏈式隊列
定義
鏈式隊列：
- 隊列的鏈式存儲結構，其實就是線性表的單鏈表，但只能尾進頭出，簡稱鏈隊列。
- 本筆記的 demo 需要一個哨兵。即是頭結點。哨兵為空節點（邏輯上不作為數據空間），有
queue->head指向。 - 隊頭指針指向鏈隊列的頭結點，隊尾指針指向終端結點。
- 空隊列：head 和 tail 都指向頭結點。
無哨兵鏈式隊列：
有哨兵鏈式隊列：
阻塞隊列
阻塞隊列：
-
就是在隊列基礎上增加了阻塞操作。
-
出隊：當隊列為空時，出隊阻塞。
-
入隊：當隊列滿時，入隊阻塞。
-
可參考 FreeRTOS，採用鏈表方式維護被阻塞的執行緒。
-
如有數據入隊正常入隊後，檢查出隊阻塞鏈表，阻塞鏈表中優先順序最高的任務解除阻塞。
- 把需要解除的任務的事件節點從消息隊列的等待接收鏈表中移除。
- 把需要解除的任務的狀態節點從延時鏈表中移除，並插入到就緒鏈表中。
-
若數據入隊阻塞，則：
- 把當前任務的事件節點插入到該隊列的等待發送鏈表中。
- 把當前任務的狀態節點從就緒鏈表移除，並插入到延時鏈表中。（RTOS 會實時檢查延時鏈表）
-
注意：出隊阻塞超時時，該任務會恢復就緒態，並在獲得 CPU 許可權後繼續執行入隊操作，看 API
BaseType_t xQueueReceive();可知，恢復執行後便檢查任務超時時間是否到期，若到期了，就把當前任務的事件節點從消息隊列等待接收鏈表中移除，並返回錯誤碼。
-
並發隊列
並發隊列：
- 執行緒安全的隊列叫作並發隊列。
- 可以通過鎖機制實現執行緒安全，意思是給隊列配個鎖。
- 但是鎖粒度大並發度會比較低，同一時刻僅允許一個存或者取操作。
- 基於數組的循環隊列，利用 CAS（Compare And Swap） 原子操作，可以實現非常高效的並發隊列。
程式碼實現
循環隊列程式碼
/** @file queue.c
* @brief 簡要說明
* @details 詳細說明
* @author lzm
* @date 2021-09-10 21:12:56
* @version v1.0
* @copyright Copyright By lizhuming, All Rights Reserved
* @blog //www.cnblogs.com/lizhuming/
*
**********************************************************
* @LOG 修改日誌:
**********************************************************
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 建議把本文件修改成循環隊列的底層文件。
// 創建時，上層提供原數類型大小和最大個數即可。
// 而本文件的隊列空間顆粒改為一個位元組。
// 循環隊列
typedef int qe_type; /* 元素類型 */
#define QUEUE_SIZE 100 /* 棧元素個數 */
typedef struct
{
qe_type data[QUEUE_SIZE]; /* 空間 */
int head; /* 頭指針 */
int tail; /* 尾指針 */
}queue_array_t;
/**
* @name queue_creat
* @brief
* @param
* @retval
* @author lzm
*/
queue_array_t *queue_array_creat(void)
{
queue_array_t *queue_ptr = NULL;
queue_ptr = (queue_array_t *)malloc(sizeof(queue_array_t));
if(queue_ptr == NULL)
return NULL;
memset(queue_ptr, 0x00, sizeof(queue_array_t));
queue_ptr->head = 0;
queue_ptr->tail = 0;
return queue_ptr;
}
/**
* @name queue_destroy
* @brief
* @param
* @retval
* @author lzm
*/
int queue_destroy(queue_array_t *queue)
{
if(queue != NULL)
{
free(queue);
return 0;
}
return -1;
}
/**
* @name queue_clear
* @brief
* @param
* @retval
* @author lzm
*/
int queue_clear(queue_array_t *queue)
{
if(queue == NULL)
return -1;
queue->head = 0;
queue->tail = 0;
return 0;
}
/**
* @name queue_empty
* @brief
* @param
* @retval
* @author lzm
*/
int queue_empty(queue_array_t *queue)
{
if(queue == NULL)
return -1;
if(queue->head == queue->tail)
return 1;
return 0;
}
/**
* @name queue_full
* @brief
* @param
* @retval
* @author lzm
*/
int queue_full(queue_array_t *queue)
{
if(queue == NULL)
return -1;
if(queue->head == (queue->tail + 1) % QUEUE_SIZE)
return 1;
return 0;
}
/**
* @name queue_length
* @brief
* @param
* @retval
* @author lzm
*/
int queue_length(queue_array_t *queue)
{
if(queue == NULL)
return -1;
return (queue->tail - queue->head + QUEUE_SIZE) % QUEUE_SIZE;
}
/**
* @name queue_insert
* @brief
* @param
* @retval
* @author lzm
*/
int queue_insert(queue_array_t *queue, qe_type elem)
{
if(queue_full(queue) != 0)
return -1;
queue->data[queue->tail] = elem;
queue->tail = (queue->tail + 1) % QUEUE_SIZE;
return 0;
}
/**
* @name queue_delete
* @brief
* @param
* @retval
* @author lzm
*/
int queue_delete(queue_array_t *queue, qe_type *elem)
{
if(queue_empty(queue) != 0 || elem == NULL)
{
return -1;
}
*elem = queue->data[queue->head];
queue->head = (queue->head + 1) % QUEUE_SIZE;
return 0;
}
/**
* @name queue_get_top
* @brief
* @param
* @retval
* @author lzm
*/
int queue_get_head(queue_array_t *queue, qe_type *elem)
{
if(queue_empty(queue) != 0 || elem == NULL)
{
return -1;
}
*elem = queue->data[queue->head];
return 0;
}
鏈式隊列實現
/** @file queue.c
* @brief 簡要說明
* @details 詳細說明
* @author lzm
* @date 2021-09-10 21:31:11
* @version v1.0
* @copyright Copyright By lizhuming, All Rights Reserved
* @blog //www.cnblogs.com/lizhuming/
*
**********************************************************
* @LOG 修改日誌:
**********************************************************
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 建議把本文件修改成循環隊列的底層文件。
// 創建時，上層提供原數類型大小和最大個數即可。
// 而本文件的隊列空間顆粒改為一個位元組。
/* 鏈式結構 */
typedef int qe_type; /* 元素類型 */
typedef struct queue_node
{
qe_type date;
struct queue_node *next;
}queue_node_t;
typedef struct
{
queue_node_t *head; /* 哨兵 */
queue_node_t *tail; /* 隊尾 */
}queue_link_t;
/**
* @name queue_link_creat
* @brief 使用了哨兵方式
* @param
* @retval
* @author lzm
*/
queue_link_t *queue_link_creat(int size)
{
queue_link_t *queue_ptr = NULL;
queue_ptr = (queue_link_t *)malloc(sizeof(queue_link_t));
if(queue_ptr == NULL)
return NULL;
memset(queue_ptr, 0x00, sizeof(queue_link_t));
queue_ptr->tail = (queue_node_t *)malloc(sizeof(queue_node_t));
if(queue_ptr->tail == NULL)
{
return NULL;
}
queue_ptr->head = queue_ptr->tail;
return queue_ptr;
}
/**
* @name queue_link_destroy
* @brief
* @param
* @retval
* @author lzm
*/
int queue_link_destroy(queue_link_t *queue)
{
if(queue == NULL)
return -1;
while(queue->head)
{
queue->tail = queue->head->next;
free(queue->head);
queue->head = queue->tail;
}
free(queue);
return 0;
}
/**
* @name queue_link_clear
* @brief
* @param
* @retval
* @author lzm
*/
int queue_link_clear(queue_link_t *queue)
{
queue_node_t *queue_cur = NULL;
queue_node_t *queue_last = NULL;
if(queue == NULL)
return -1;
queue->tail = queue->head;
queue_cur = queue->head->next;
queue->head->next = NULL;
while(queue_cur)
{
queue_last = queue_cur;
queue_cur = queue_cur->next;
free(queue_last);
}
return 0;
}
/**
* @name queue_link_empty
* @brief
* @param
* @retval
* @author lzm
*/
int queue_link_empty(queue_link_t *queue)
{
if(queue == NULL)
return -1;
if(queue->head == queue->tail)
return 1;
return 0;
}
/**
* @name queue_link_length
* @brief
* @param
* @retval
* @author lzm
*/
int queue_link_length(queue_link_t *queue)
{
int cnt = 0;
queue_node_t *queue_cur = NULL;
if(queue == NULL)
return -1;
queue_cur = queue->head;
while(queue_cur != queue->tail)
{
cnt++;
queue_cur = queue_cur->next;
}
return cnt;
}
/**
* @name queue_link_inster
* @brief
* @param
* @retval
* @author lzm
*/
int queue_link_inster(queue_link_t *queue, qe_type elem)
{
queue_node_t *queue_node_ptr = NULL;
queue_node_ptr = (queue_node_t *)malloc(sizeof(queue_node_t));
if(queue_node_ptr == NULL)
return -1;
memset(queue_node_ptr, 0x00, sizeof(queue_node_t));
queue_node_ptr->date = elem;
queue_node_ptr->next = NULL;
queue->tail->next = queue_node_ptr;
queue->tail = queue_node_ptr;
return 0;
}
/**
* @name queue_link_delete
* @brief
* @param
* @retval
* @author lzm
*/
int queue_link_delete(queue_link_t *queue, qe_type *elem)
{
queue_node_t *node = NULL;
if(queue_link_empty(queue) != 0 || elem == NULL)
{
return -1;
}
node = queue->head->next;
*elem = node->date;
queue->head->next = node->next;
if(node == queue->tail)
queue->tail = queue->head;
free(node);
return 0;
}
/**
* @name queue_link_get_top
* @brief
* @param
* @retval
* @author lzm
*/
int queue_link_get_top(queue_link_t *queue, qe_type *elem)
{
if(queue_link_empty(queue) != 0 || elem == NULL)
{
return -1;
}
*elem = queue->head->next->date;
return 0;
}
