隊列基礎

来源:https://www.cnblogs.com/flyingwords/archive/2019/08/24/11386478.html
-Advertisement-
Play Games

隊列的分類 隊列一般分為三種：順序隊列、迴圈隊列、鏈式隊列 其中順序隊列和迴圈隊列按照存儲方式又可以分為動態和靜態，鏈式隊列是動態的。 順序隊列 順序隊列存在”假溢出“現象：即隊頭由於出隊操作，還有剩餘空間，但隊尾指針已達到數組的末尾，如果繼續插入元素，隊尾指針就會越出數組的上界，而造成“溢出”，這 ...


隊列的分類

　　隊列一般分為三種：順序隊列、迴圈隊列、鏈式隊列

　　其中順序隊列和迴圈隊列按照存儲方式又可以分為動態和靜態，鏈式隊列是動態的。動態表示隊列元素採用動態記憶體分配，靜態表示隊列元素採用數組的方式分配。

 

順序隊列

　　順序隊列存在”假溢出“現象：即隊頭由於出隊操作，還有剩餘空間，但隊尾指針已達到數組的末尾，如果繼續插入元素，隊尾指針就會越出數組的上界，而造成“溢出”，這種溢出不是因為存儲空間不夠而產生的溢出，這種溢出不是因為存儲空間不夠而產生的溢出，像這種有存儲空間而不能插入元素的操作稱為“假溢出“。

　　由於存在順序隊列存在”假溢出“現象，因此一般使用順序隊列。

 

迴圈隊列

關於判斷隊滿和隊空

　　當迴圈隊列為空或為滿時，隊尾和隊頭指針都指向同一個元素，可以通過下麵幾種方式判斷隊列空或隊列滿：

　　（1）、犧牲一個隊列元素用來識別隊列滿和隊列空

　　（2）、通過計數器來判斷隊列滿和隊列空

　　（3）、通過一個讀寫標誌來判斷隊列滿和隊列空

 

靜態迴圈隊列

　　採用靜態迴圈隊列來展示三種隊列滿和隊列空的判斷方法，舉例如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define queue_max_length 5

#if 1    //犧牲一個隊列元素用來識別隊列滿和隊列空
typedef struct queue_srt
{
    int front;
    int rear;
    int queue_data[queue_max_length];
} queue_srt;


int queue_init(queue_srt *q_srt)
{
    q_srt->front = q_srt->rear = 0;
    memset(q_srt->queue_data, 0, sizeof(q_srt->queue_data));
    printf("queue init success\n");
    return 0;
}

int queue_read(queue_srt *q_srt, int *value)
{
    //判斷隊列是否為空
    if (q_srt->front == q_srt->rear)
    {    
        printf("the queue is empty\n");
        return 1;
    }
    *value = q_srt->queue_data[q_srt->front];
    q_srt->front = (q_srt->front + 1) % queue_max_length;
    return 0;
}

int queue_write(queue_srt *q_srt, int value)
{
    //犧牲一個隊列元素用來判斷隊列滿
    if (((q_srt->rear + 1)%queue_max_length) == q_srt->front)
    {    
        printf("the queue is full\n");
        return 1;
    }
    q_srt->queue_data[q_srt->rear] = value;
    q_srt->rear = (q_srt->rear + 1) % queue_max_length;
    return 0;
}

int queue_length(queue_srt *q_srt)
{
    //計算隊列長度
    int length = (q_srt->rear - q_srt->front + queue_max_length) % queue_max_length;
    return length;
}
#endif 

#if 0    //通過計數器來判斷隊列滿和隊列空
typedef struct queue_srt
{
    int front;
    int rear;
    int queue_data[queue_max_length];
    int cnt;      //計數器，用來記錄隊列長度
} queue_srt;

int queue_init(queue_srt *q_srt)
{
    q_srt->front = q_srt->rear = 0;
    q_srt->cnt = 0;
    memset(q_srt->queue_data, 0, sizeof(q_srt->queue_data));
    printf("queue init success\n");
    return 0;
}

int queue_read(queue_srt *q_srt, int *value)
{
    //通過判斷計數器來識別隊列是否已經空
    if (q_srt->cnt == 0)
    {
        printf("the queue is empty\n");
        return 1;
    }
    *value = q_srt->queue_data[q_srt->front];
    q_srt->front = (q_srt->front + 1) % queue_max_length;
    q_srt->cnt--;//讀完數據，計數器減1
    return 0;
}

int queue_write(queue_srt *q_srt, int value)
{
    //通過判斷計數器來識別隊列是否已經滿
    if (q_srt->cnt == queue_max_length)
    {
        printf("the queue is full\n");
        return 1;
    }
    q_srt->queue_data[q_srt->rear] = value;
    q_srt->rear = (q_srt->rear + 1) % queue_max_length;
    q_srt->cnt++; //寫完數據，計數器加1
    return 0;
}

int queue_length(queue_srt *q_srt)
{
    //通過計數器獲取隊列長度
    int length = q_srt->cnt;
    return length;
}
#endif

#if 0    //通過一個讀寫標誌來判斷隊列滿和隊列空
typedef struct queue_srt
{
    int front;
    int rear;
    int queue_data[queue_max_length];
    char rw_flag; //讀寫標誌  w:表示寫完隊列  r:表示讀完隊列
} queue_srt;

int queue_init(queue_srt *q_srt)
{
    q_srt->front = q_srt->rear = 0;
    q_srt->rw_flag = 'r'; //初始為 r ，表示隊列為空
    memset(q_srt->queue_data, 0, sizeof(q_srt->queue_data));
    printf("queue init success\n");
    return 0;
}

int queue_read(queue_srt *q_srt, int *value)
{
    //通過讀寫標誌判斷隊列是否為空
    if ((q_srt->front == q_srt->rear) && (q_srt->rw_flag == 'r'))
    {    
        printf("the queue is empty\n");
        return 1;
    }
    *value = q_srt->queue_data[q_srt->front];
    q_srt->front = (q_srt->front + 1) % queue_max_length;
    q_srt->rw_flag = 'r'; //讀完隊列，讀寫標誌設置r
    return 0;
}

int queue_write(queue_srt *q_srt, int value)
{
    //通過讀寫標誌判斷隊列是否為空
    if ((q_srt->front == q_srt->rear) && (q_srt->rw_flag == 'w'))
    {    
        printf("the queue is full\n");
        return 1;
    }
    q_srt->queue_data[q_srt->rear] = value;
    q_srt->rear = (q_srt->rear + 1) % queue_max_length;
    q_srt->rw_flag = 'w'; //寫完隊列，讀寫標誌設置w
    return 0;
}

int queue_length(queue_srt *q_srt)
{
    int length = 0;       
    if ((q_srt->front == q_srt->rear) && (q_srt->rw_flag == 'w')) //通過讀寫標誌判斷是否隊滿
    {
        length = queue_max_length;
    }
    else 
    {
        length = (q_srt->rear - q_srt->front + queue_max_length) % queue_max_length;
    }
    return length;
}
#endif 

int main(void)
{
    int action = 0;
    int value = 0;
    queue_srt testqueue;
    queue_init(&testqueue);
    while (1)
    {
        printf("1:write 2:read 3:get length\n");
        printf("enter action:");
        scanf("%d", &action);
        switch(action)
        {
            case 1:
                printf("write queue to data:");
                scanf("%d", &value);
                queue_write(&testqueue, value);
                break;
            case 2:
                if (1 == queue_read(&testqueue, &value))
                    continue;
                printf("read data from queue: %d\n", value);
                break;
            case 3:
                value = queue_length(&testqueue);
                printf("the length of queue is: %d\n", value);
                break;
            default:
                printf("no such action\n");
        }
    }
    return 0;
}

 

 

 動態迴圈隊列

　　下麵展示一個動態迴圈隊列，隊列元素採用動態記憶體分配，舉例如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define queue_max_length 5
typedef struct queue_srt
{
    int *front;        //指向隊列頭
    int *rear;        //指向隊列尾
    int *queue_data;  //指向隊列動態記憶體
    int *end;        //指向隊列存儲空間之後
} queue_srt;


int queue_init(queue_srt *q_srt)
{
    q_srt->queue_data = (int *) (malloc)(sizeof(int) * queue_max_length);
    if (NULL == q_srt)
    {
        printf("malloc mem failed,queue init failed\n");
        return 1;
    }
    q_srt->front = q_srt->rear = q_srt->queue_data; //指向隊列首部
    q_srt->end = q_srt->queue_data + queue_max_length; //指向隊列存儲空間之後
    printf("queue init success\n");
    return 0;
}

int queue_read(queue_srt *q_srt, int *value)
{
    if (q_srt->front == q_srt->rear) //判斷隊列是否為空
    {    
        printf("the queue is empty\n");
        return 1;
    }
    *value = *(q_srt->front);
    if ((q_srt->front + 1) >= q_srt->end) //判斷隊頭指針是否到隊列尾
    {
        q_srt->front = q_srt->queue_data;
    }
    else
    {
        q_srt->front = q_srt->front + 1;
    }
    return 0;
}

int queue_write(queue_srt *q_srt, int value)
{
    //犧牲一個隊列元素用來識別隊列滿
    int *q_tmp = (q_srt->rear + 1 >= q_srt->end)? (q_srt->queue_data) : (q_srt->rear + 1);
    if (q_tmp == q_srt->front)
    {    
        printf("the queue is full\n");
        return 1;
    }
    *(q_srt->rear) = value;
    q_srt->rear = q_tmp;
    return 0;
}

int queue_length(queue_srt *q_srt)
{
    int length = 0;
    length = (q_srt->rear - q_srt->front + queue_max_length) % queue_max_length;return length; //獲取隊列長度
}

int main(void)
{
    int action = 0;
    int value = 0;
    queue_srt testqueue;
    queue_init(&testqueue);
    while (1)
    {
        printf("1:write 2:read 3:get length\n");
        printf("enter action:");
        scanf("%d", &action);
        switch(action)
        {
            case 1:
                printf("write queue to data:");
                scanf("%d", &value);
                queue_write(&testqueue, value);
                break;
            case 2:
                if (1 == queue_read(&testqueue, &value))
                    continue;
                printf("read data from queue: %d\n", value);
                break;
            case 3:
                value = queue_length(&testqueue);
                printf("the length of queue is: %d\n", value);
                break;
            default:
                printf("no such action\n");
        }
    }
    free(testqueue.queue_data);
    return 0;
}

 

鏈式隊列

　　鏈式隊列主要有兩個特點：1、隊列是動態的，即隊列元素採用動態記憶體分配　　2、隊列採用鏈表的邏輯來組織，因此隊列的長度沒有限制，這是跟迴圈隊列最大的差別

　　編寫一個帶頭結點的鏈式隊列，舉例如下：

#include <stdio.h>
#include <stdlib.h>
typedef struct LKNODE
{
    int data;                //保存節點數據
    struct LKNODE *next;    //指向下一個節點
} LKNODE;

typedef struct LINKQUEUE    //隊列結構體，採用頭尾指針構建鏈式隊列
{
    
    LKNODE *front; //頭指針，指向隊列頭結點
    LKNODE *rear;  //尾指針，指向隊列尾節點
}LINKQUEUE;

//初始化鏈式隊列
int InitLinkQueue(LINKQUEUE *lkqueue)
{
    
    LKNODE *head = (LKNODE*) malloc(sizeof(LKNODE)); //創建頭結點
    if (NULL == head)
    {
        printf("creat head node failed,init linkqueue failed\n");
        return 1;
    }
    head->next = NULL; //這裡要head節點的next設置為NULL，避免頭尾指針的next指向未知
    //頭尾指針指向頭結點
    lkqueue->front = lkqueue->rear = head;
    return 0;
}

//節點入隊
int WriteLinkQueue(LINKQUEUE *lkqueue, int value)
{
    //創建新節點
    LKNODE *newnode = (LKNODE *)malloc(sizeof(LKNODE));
    if (NULL == newnode)
    {
        printf("creat newnode failed,write queue failed\n");
        return 1;
    }
    newnode->data = value;
    newnode->next = NULL; //這裡要指向空，避免隊列為空後，頭結點的next指針指向未知
    
    //尾指針連接新節點
    lkqueue->rear->next = newnode;
    
    //尾指針指向新節點
    lkqueue->rear = newnode;
    return 0;
}

//節點出隊
int ReadLinkQueue(LINKQUEUE *lkqueue, int *value)
{
    //LKNODE *temp = NULL;
    LKNODE *readnode = NULL;
    //判斷隊列是否為空隊列
    if (lkqueue->front == lkqueue->rear)
    {
        printf("link queue is empty\n");
        return 1;
    }
    //獲取讀取節點值
    readnode = lkqueue->front->next;
    *value = readnode->data;

    //頭結點連接讀取節點的下一個節點
    lkqueue->front->next = readnode->next;  //如果readnode是最後一個節點，則頭結點的next會指向NULL
    
    //判斷讀取的節點是不是最後一個節點，防止釋放讀取節點後尾指針指向空
    if (readnode == lkqueue->rear)
    {
        lkqueue->rear = lkqueue->front; //隊列為空，尾指針指向頭結點
    }
    //釋放讀取節點
    free(readnode);
    return 0;
}

//獲取隊列長度
int GetLinkQueueLen(LINKQUEUE *lkqueue)
{
    int length = NULL;
    LKNODE *temp = NULL; //創建臨時節點，因為頭尾指針的位置不能動
    temp = lkqueue->front->next; //獲取頭結點的下一個節點
    if (NULL == temp) //判斷隊列是否為空
    {
        length = 0;
    }
    else
    {
        while(temp != lkqueue->rear) //判斷是不是讀到尾節點
        {
            length++;
            temp = temp->next;
        }
        length++; //加上最後一個節點
    }
    return length;
}

//清空隊列
void ClearLinkQueue(LINKQUEUE *lkqueue)
{
    int value;
    int ret;
    while(1)
    {
        //讀取隊列元素，釋放動態記憶體，防止記憶體泄漏
        ret = ReadLinkQueue(lkqueue, &value);
        if (1 == ret) //判斷隊列是否讀完
        {
            printf("clear the link queue success\n");
            break;
        }
    }
}

//銷毀隊列
void DestroyLinkQueue(LINKQUEUE *lkqueue)
{
    //先清空隊列，釋放隊列的動態記憶體
    ClearLinkQueue(lkqueue);
    
    //釋放頭結點的動態記憶體
    free(lkqueue->front);
    
    //頭尾指針指向空
    lkqueue->front = lkqueue->rear = NULL;
    
    printf("destroy the link queue success\n");
}

//遍歷隊列
void TraverseLinkQueue(LINKQUEUE *lkqueue)
{
    int value;
    int ret = 0;
    int num = 0;
    LKNODE *temp = lkqueue->front->next;
    while(1)
    {
        if (NULL != temp)  //判斷隊列是否為空
        {
            num++;
            printf("%d node data is:%d\n", num, temp->data);
            temp = temp->next;
        }
        else
        {
            printf("traverse link queue success\n");
            break;
        }
    }
    
}

int main()
{
    int action = 0;
    int value = 0;
    int ret = 0;
    LINKQUEUE testlkqueue = {NULL, NULL};
    InitLinkQueue(&testlkqueue); //初始化鏈式隊列
    
    while(1)
    {
        printf("**********\n1 write    2 read 3 getlength 4 Traverse 5 Clear link queue 6 destroy link queue\n**********\n");
        printf("enter action:");
        scanf("%d", &action);
        switch(action)
        {
            case 1:
                printf("enter the value:");
                scanf("%d", &value);
                WriteLinkQueue(&testlkqueue, value);
                break;
            case 2:
                ret = ReadLinkQueue(&testlkqueue, &value);
                if (1 != ret)
                {
                    printf("the readnode data is:%d\n", value);
                }
                break;
            case 3:
                ret = GetLinkQueueLen(&testlkqueue);
                printf("the length of link queue is:%d\n", ret);
                break;
            case 4:
                TraverseLinkQueue(&testlkqueue);
                break;
            case 5:
                ClearLinkQueue(&testlkqueue);
                break;
            case 6:
                DestroyLinkQueue(&testlkqueue);
                return 0;
                break;
            default:
                break;
        }
    }
    return 0;
}

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • C#/Java 動態生成電子發票
    電子發票是電商時代的產物，PDF發票是最常見的電子發票之一。在這篇文章中，我將給大家分享一個免費的動態生成PDF電子發票的C#方案，併在文章末尾附上Java解決方案。 典型的發票包含客戶和供應商的名稱和地址、發票編號、購買物品的描述、付款金額等信息。為了動態地生成發票，我使用MS Word創建了一個 ...
  • 使用MTA HTML5統計API來分析數據
    在開發個人博客的時候，用到了騰訊移動分析(MTA)，相比其他數據統計平臺來說我喜歡她的簡潔高效，易上手，同時文檔也比較全面，提供了數據介面供用戶調用。 在看了MTA演示 "Demo" 和 "官方文檔" 後，我就決定使用 .NET Core將其HTML5統計API進行封裝，以供博客直接調用，省去各種鑒 ...
  • asp.net core系列 71 Web架構分層指南
    一.概述 本章Web架構分層指南，參考了“Microsoft應用程式體繫結構指南”（該書是在2009年出版的，當時出版是為了幫助開發人員和架構師更快速，更低風險地使用Microsoft平臺和.NET Framework設計和構建有效，高質量的應用程式）。雖然已過去十年了，技術架構已更新(如流行的DD ...
  • Linux 磁碟配額（XFS & EXT4）
    若是在 Linux 中搭建了 FTP 伺服器，為了安全性，就要考慮磁碟配額，以防伺服器磁碟空間被惡意占滿。 ...
  • 【原創】ARMv8 MMU及Linux頁表映射
    背景 By 魯迅 By 高爾基 說明： 1. Kernel版本：4.14 2. ARM64處理器，Contex A53，雙核 3. 使用工具：Source Insight 3.5， Visio 1. 介紹 要想理解好Linux的頁表映射，MMU的機制是需要去熟悉的，因此將這兩個模塊放到一起介紹。 關 ...
  • Linux網路管理
    1 網路相關的幾個文件說明 1.1 網卡配置文件ifcfg 在/etc/sysconfig/network scripts/目錄下有不少文件，絕大部分都是腳本類的文件，但有一類 ifcfg開頭 的文件為網卡配置文件(interface config)，所有ifcfg開頭的文件在啟動網路服務的時候都會 ...
  • ceph存儲基礎概念
    一．分散式文件系統： 是指文件系統管理的物理存儲資源不一定直接是連接在本地節點上，而是通過電腦網路與節點相連． 分散式文件系統的設計基與C/S架構（客戶端/伺服器） 常見的分散式文件系統:Ceph、（紅帽）Hadoop、FastDFS（國產） 二.Ceph分散式文件系統 特點：具有高擴展、高可用、 ...
  • Cacti+nagios 整合監控部署文檔
    目錄 Cacti+nagios監控部署步驟... 2 一、Cacti安裝... 2 1需要安裝的依賴軟體包：... 2 2安裝rrdtool 2 3啟動資料庫和httpd服務... 3 4將servername和ip對應寫入hosts 3 5安裝cacti 3 6創建cacti資料庫並授權：... ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類