C/C++資料結構：佇列結構最全決議！帶你零基礎入門佇列結構

前言

上一章節針對于C語言堆疊結構做了決議，不清楚的可以回顧一下，

本章節主要針對于C語言的基礎資料結構佇列做以決議，

資料結構之佇列

佇列是一種特殊的 線性表 ，特殊之處在于它只允許在表的前端（front）進行洗掉操作，而在表的后端（rear）進行插入操作，和堆疊一樣，佇列是一種操作受限制的線性表，進行插入操作的端稱為隊尾，進行洗掉操作的端稱為隊頭，

故佇列基本操作如下：

（1）創建佇列

（2）入隊

（3）出隊

（4）判斷佇列是否為NULL

（5）獲取隊頭元素

資料結構之佇列分類

根據佇列實作方式與出隊方式，我們可以把堆疊分為以下三種描述方式：

（1）原生陣列佇列

（2）動態申請記憶體的陣列描述(普通佇列和回圈佇列）

（3）鏈式結構描述

優先佇列

原生陣列描述佇列

陣列描述堆疊，只不過多了先進先出的限制而已，它是靜態分配的，即使用前，它的記憶體就已經以陣列的形式分配好了，所以在使用時，需要注意隊頭隊尾的標記，

原生陣列描述佇列實作試題案例:逆序整數

動態陣列描述佇列

動態申請記憶體的陣列描述不再采用上述實用性的方法了，而是通過封裝相關佇列函式去描述這種結構，這是寫資料結構的一種大致方法，

1.結構體定義與佇列的創建程序：

結構體定義:描述佇列的屬性：隊頭標記，隊尾標記，佇列空間

創建佇列其實就是創建結構體變數

具體代碼

ps:隊頭和隊尾頂標記初始值一般都是-1 ，為了滿足佇列標記和陣列下標一致

2.入隊操作

注意: 我們的實作是將最新的元素放在了陣列的末尾, 那么陣列末尾的元素就是我們的佇列隊尾元素，故可以使用隊尾標記去計算佇列中的元素個數，然后每次入隊后，隊尾標記往后移動，

具體實作代碼：

3.出隊操作和獲取隊頭元素

注意: 出隊操作應該是將隊頭元素洗掉,由于陣列實作的佇列無法洗掉，故只能把隊頭標記往隊尾移動，簡稱為一種"偽洗掉"，

具體實作代碼：

4.判斷堆疊是否為空

用戶判斷堆疊中是否有元素，通過隊尾和隊頭標記去做即可

具體實作代碼：

動態申請記憶體的陣列描述佇列測驗代碼

ps:回圈佇列是通過取余形成的回圈，這里不過多介紹，有興趣的可以看看相關資料，

鏈式佇列

鏈式佇列： 鏈表的尾插法即可

具體實作原始碼獻上

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
  int data;
  struct Node* next;
}NODE,*LPNODE;

LPNODE createNode(int data)
{
  LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
  newNode->data =https://www.cnblogs.com/112Q/archive/2020/09/30/ data;
  newNode->next = NULL;
  return newNode;
}
typedef struct
{
  int queueSize;
  LPNODE frontNode;
  LPNODE tailNode;
}QUEUE,*LPQUEUE;
LPQUEUE createQueue()
{
  LPQUEUE queue = (LPQUEUE)malloc(sizeof(QUEUE));
  queue->queueSize = 0;
  queue->frontNode = NULL;
  queue->tailNode = NULL;
  return queue;
}
void push(LPQUEUE queue, int data)
{
  //無頭表頭鏈表的在封裝法
  LPNODE newNode = createNode(data);
  if (queue->queueSize == 0)
  {
    queue->frontNode = newNode;
    queue->tailNode = newNode;
  }
  else
  {
    //無表頭鏈表的表尾插入
    queue->tailNode->next = newNode;
    queue->tailNode = newNode;
  }
  queue->queueSize++;
}
//FILO  +FIFO
void pop(LPQUEUE queue)
{
  if (queue->queueSize != 0)
  {
    LPNODE nextNode = queue->frontNode->next;
    free(queue->frontNode); 
    queue->frontNode = nextNode;
    queue->queueSize--; 
  }
}
int front(LPQUEUE queue)
{
  return queue->frontNode->data;
}

int empty(LPQUEUE queue)
{
  return queue->queueSize==0;
}
int size(LPQUEUE queue)
{
  return queue->queueSize;
}

int main()
{
  LPQUEUE queue = createQueue();
  for (int i = 1; i <= 3; i++)
  {
    push(queue, i);
  }
  while (!empty(queue))
  {
    printf("%d\t", front(queue));
    pop(queue);
  }
  printf("\n");
  system("pause");
  return 0;
}

優先佇列:根據優先權去決定你出隊的元素，故資料中存在優先權衡量的值，相關實作代碼如下：

#include <iostream>
#define MaxQueueSize 100    //佇列的大小
//資料型別   資料本身  優先權
typedef int ElementType;  //定義資料型別地 別名
 
//資料 結構體
typedef struct 
{
  int priority;    //優先權---作業量
  ElementType element;//佇列中的元素
}DataType;
 
//佇列的結構體
typedef struct
{
  int size;
  //結構體的嵌套
  DataType Queue[MaxQueueSize];
}PriQueue;
//讀取檔案作業---調度讀取
//佇列操作
//初始化---初始化基本成員
//size   Queue
void InitQueue(PriQueue *Q)
{
  Q->size = 0;
}
//判斷佇列是否為空  NULL
//和它的初始化比較
int QueueEmpty(PriQueue *Q)
{
  // -> 指向運算子  C：結構體指標  C++： 類和結構體
  // :: 作用域限定符
  if (Q->size <= 0)
    return 0;   //標志
  else
    return 1;  //不為空
  //  return 0 函式結束
}
//入隊 檔案操作
int Push(PriQueue *Q, DataType data)
{
  //入隊前判斷是否滿
  if (Q->size >= MaxQueueSize)
  {
    std::cout << "杯子已滿，無法再倒水" << std::endl;
    return 0;
  }
  else
  {
    //Q->size=0;
    Q->Queue[Q->size] = data;
    //入隊了佇列長度就要增長
    Q->size++;
    return 1;
  }
 
}
//出隊
int Pop(PriQueue *Q, DataType *A)
{
  DataType min;    //最小的開始，排序
  int minIndex = 0;
  //短作業優先法
  //喝水，先判斷杯子有沒有水
  if (Q->size <= 0)
  {
    std::cout << "為空，無法出隊" << std::endl;
    return 0;
  }
  else
  {
    //假設第一個作業是最短的
    min = Q->Queue[0];  //1
    for (int i = 1; i < Q->size; i++)
    {
      //多了一個資料項  按照權值排序
      //0
      if (Q->Queue[i].priority < min.priority)
      {
        min = Q->Queue[i];
        minIndex = i;    //出隊依據就是最小作業序號
      }
    }
    *A = Q->Queue[minIndex];
    //難點 
    //洗掉完陣列后，后面的元素往前移動
    for (int i = minIndex + 1; i < Q->size; i++)
    {
      Q->Queue[i - 1] = Q->Queue[i];
      minIndex = i;
    }
    Q->size--;
    return 1;
  }
 
 
 
}
//獲取隊頭元素
int GetQueue(PriQueue *Q, DataType *A)
{
  DataType min;    //最小的開始，排序
  int minIndex = 0;
  //短作業優先法
  //喝水，先判斷杯子有沒有水
  if (Q->size <= 0)
  {
    std::cout << "為空，無法出隊" << std::endl;
    return 0;
  }
  else
  {
    //假設第一個作業是最短的
    min = Q->Queue[0];  //1
    for (int i = 1; i < Q->size; i++)
    {
      //多了一個資料項  按照權值排序
      //0
      if (Q->Queue[i].priority < min.priority)
      {
        min = Q->Queue[i];
        minIndex = i;    //出隊依據就是最小作業序號
      }
    }
    *A = Q->Queue[minIndex];
    return 1;
  }
}

希望對大家有幫助！

另外如果你想更好的提升你的編程能力，學好C語言C++編程！彎道超車，快人一步！

C語言C++編程學習交流圈子，QQ群1095293493【點擊進入】微信公眾號：C語言編程學習基地

分享（原始碼、專案實戰視頻、專案筆記，基礎入門教程）

歡迎轉行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！

編程學習軟體分享：

編程學習視頻分享：

標籤：其他

上一篇：劍指offer題解（二） - JZ11 ~ JZ20

下一篇：執行config_solo檔案夾中./generate.sh腳本報錯./bin/cryptogen ./bin/configtxgen: 沒有那個檔案或目錄