隊(duì)列

定義

一種可以實(shí)現(xiàn)“先進(jìn)先出”的存儲(chǔ)結(jié)構(gòu)皆疹。

分類

1. 鏈?zhǔn)疥?duì)列 （用鏈表實(shí)現(xiàn)）

圖

1. 靜態(tài)隊(duì)列 （用數(shù)組實(shí)現(xiàn)）

   

   圖

   靜態(tài)隊(duì)列通常都必須是循環(huán)隊(duì)列

   循環(huán)隊(duì)列的講解：

   1. 靜態(tài)隊(duì)列為什么必須是循環(huán)隊(duì)列

      減少空間的浪費(fèi)

   2. 循環(huán)隊(duì)列需要幾個(gè)參數(shù)來(lái)確定

      需要兩個(gè)參數(shù)來(lái)確定：

      1. front
      2. rear

   3. 循環(huán)隊(duì)列各個(gè)參數(shù)的含義

      2個(gè)參數(shù)不同場(chǎng)合有不同的含義

      1. 隊(duì)列初始化：front和rear的值都是零想括。

      2. 隊(duì)列非空：front代表的是隊(duì)列的第一個(gè)元素二驰，rear代表的是隊(duì)列的最后一個(gè)有效元素的下一個(gè)元素。

      3. 隊(duì)列為空：front和rear的值相等，但不定是零

   4. 循環(huán)隊(duì)列入隊(duì)偽算法講解

      1. 將值傳入r所代表的位置

      2. r = (r + 1) % 數(shù)組的長(zhǎng)度

   5. 循環(huán)隊(duì)列出隊(duì)偽算法講解

      f = (f + 1) % 數(shù)組的長(zhǎng)度

   6. 如何判斷循環(huán)隊(duì)列是否為空

      f == r的時(shí)候循環(huán)隊(duì)列為空

   7. 如何判斷循環(huán)隊(duì)列是否已滿

      1. 多增加一個(gè)標(biāo)識(shí)參數(shù)
      2. 少用一個(gè)元素［通常使用第這種方法］

      // 偽算法
      if( (r+1)%數(shù)組的長(zhǎng)度 == f )
          已滿
      else
          未滿
      

隊(duì)列算法

1. 入隊(duì)

   
   int en_queue(Queue *q, int val)
   {
       if (is_full(q)) {
           return 0;
       } else {
           q->pBase[q->rear] = val;
           
           // 入隊(duì)，rear加1
           q->rear = (q->rear + 1) % kQueue_len;
           
           return 1;
       }
   }
   
   

2. 出隊(duì)

   int out_queue(Queue *q, int *pVal)
   {
       if (is_empty_queue(q)) {
           return 0;
       }
       
       *pVal = q->pBase[q->front];
       
       // 出隊(duì)，front加1
       q->front = (q->front + 1)  % kQueue_len;
       
       return 1;
   }
   

隊(duì)列的具體應(yīng)用

所有和時(shí)間有關(guān)的操作都有隊(duì)列的影子

Example 1

以下是一個(gè)循環(huán)隊(duì)列的具體代碼實(shí)現(xiàn)的例子：

#include <stdio.h>
#include <stdlib.h>

// 定義隊(duì)列的長(zhǎng)度
static const int kQueue_len = 6;

// 定義隊(duì)列的結(jié)構(gòu)體
typedef struct Queue {
    int *pBase;
    int front;
    int rear;
} Queue;

// 初始化
void init(Queue *, int);

// 入隊(duì)
int en_queue(Queue *, int);

// 出隊(duì)
int out_queue(Queue *, int *);

// 遍歷
void traverse_queue(Queue *);

// 判斷隊(duì)列是否已滿
int is_full(Queue *);

// 判斷隊(duì)列是否為空
int is_empty_queue(Queue *q);

int main(void)
{
    Queue q = {0};
    init(&q, kQueue_len);
    en_queue(&q, 1);
    en_queue(&q, 2);
    en_queue(&q, 3);
    en_queue(&q, 4);
    en_queue(&q, 5);
    en_queue(&q, 6);
    en_queue(&q, 7);
    en_queue(&q, 8);
    traverse_queue(&q);
    
    int pVal;
    
    if (out_queue(&q, &pVal)) {
        printf("出隊(duì)成功昼窗，隊(duì)列出隊(duì)元素是%d\n", pVal);
    } else {
        printf("出隊(duì)失敗涛舍！\n");
    }
    
    traverse_queue(&q);
    
    return 0;
}

void init(Queue *q, int len)
{
    q->pBase = (int *)malloc(sizeof(int) * len);
    q->front = 0;
    q->rear = 0;
}

int en_queue(Queue *q, int val)
{
    if (is_full(q)) {
        return 0;
    } else {
        q->pBase[q->rear] = val;
        
        // 入隊(duì)澄惊，rear加1
        q->rear = (q->rear + 1) % kQueue_len;
        
        return 1;
    }
}

int out_queue(Queue *q, int *pVal)
{
    if (is_empty_queue(q)) {
        return 0;
    }
    
    *pVal = q->pBase[q->front];
    
    // 出隊(duì)，front加1
    q->front = (q->front + 1)  % kQueue_len;
    
    return 1;
}

int is_full(Queue *q)
{
    // rear緊挨著front一個(gè)元素的之間距的時(shí)候富雅，隊(duì)列就滿了
    if (((q->rear + 1) % kQueue_len) == q->front) {
        return 1;
    }
    
    return 0;
}

int is_empty_queue(Queue *q)
{
    // 只要front等于rear掸驱，隊(duì)列就為空
    if (q->front == q->rear) {
        return 1;
    }
    return 0;
}

void traverse_queue(Queue *q)
{
    int i = q->front;
    
    while (i != q->rear) {
        printf("%d\t", q->pBase[i]);
        
        // front位置不斷加1取余鏈表長(zhǎng)度，等于rear的時(shí)候没佑，遍歷完畢
        i = (i+1) % kQueue_len;
    }
    
    printf("\n");
}

代碼在Github這里code_01