數據結構入門-隊列

一種可以實現"先進先出"的存儲結構

分類：

1. 鏈式隊列：用鏈表實現
2. 靜態隊列：用數組實現，靜態隊列通常都必須是迴圈隊列

迴圈隊列的講解：

1. 靜態隊列為什麼是迴圈隊列

   減少對記憶體的浪費

2. 迴圈隊列需要幾個參數來確定

   兩個參數，frant 、rear 但這2個參數不同場合有不同的含義，建議初學者先記住

3. 迴圈隊列各個參數的含義

   隊列初始化：front和rear的值都是零

   隊列非空：front代表隊列的第一個元素，rear代表隊列的最後一個有效元素的下一個元素

   隊列空：front和rear的值相等，但不一定是零

4. 迴圈隊列入隊偽演算法

   將值存入rear所代表的位置

   錯誤的寫法：r = r + 1

   正確的應該是r = (r+1)%數組長度

5. 迴圈隊列出隊偽演算法

   front = (front+1)%數組長度

6. 如何判斷迴圈隊列是否為空

   如果front和rear的值相等，則隊列為空

7. 如何判斷迴圈隊列已滿

   多增加一個表標識的參數

   少用一個元素，通常都是這樣：(rear+1) % 數組長度 == front

具體的實現

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


typedef struct Queue
{
    int * pBase;
    int front;
    int rear;
}QUEUE;

void init(QUEUE *);
bool full_queue(QUEUE *);
bool empty(QUEUE *);
bool en_queue(QUEUE * , int val); // 入隊
void traverse(QUEUE *);
bool out(QUEUE *, int * pVal);


int main(void)
{
    QUEUE Q;
    int val;

    init(&Q);
    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);

    traverse(&Q);
    if (out(&Q , &val))
    {
        printf("出隊成功，出隊的元素：%d\n", val);
        en_queue(&Q , 9);
        traverse(&Q);
    }
    else
    {
        printf("出隊失敗\n");
    }


    return 0;
}


void init(QUEUE * pQ)
{
    pQ->pBase = (int *)malloc(sizeof(int) * 6); // 初始化預設是長度是6
    if (NULL == pQ->pBase)
    {
        printf("初始化失敗\n");
        exit(-1);
    }

    pQ->front = 0;
    pQ->rear = 0;
}

bool full_queue(QUEUE *pQ)
{
    if ((pQ->rear+1)%6 == pQ->front)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool en_queue(QUEUE *pQ , int val)
{
    if (full_queue(pQ))
    {
        return false;
    }
    else
    {
        pQ->pBase[pQ->rear] = val;
        pQ->rear = (pQ->rear+1)%6;
        return true;
    }
}

void traverse(QUEUE * pQ)
{
    int i = pQ->front;

    while(i != pQ->rear)
    {
        printf("%d\n",pQ->pBase[i] );
        i = (i+1) % 6;
    }

    return;
}


bool empty(QUEUE * pQ)
{
    if (pQ->front == pQ->rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}


bool out(QUEUE * pQ, int * pVal)
{

    if (empty(pQ))
    {
        return false;
    }
    else
    {
        *pVal = pQ->pBase[pQ->front];
        pQ->front = (pQ->front+1) % 6;
        return true;
    }

}

隊列的應用

• 所有和時間有關的操作都有隊列的影子