基於C語言的嵌入式適用的數據結構---佇列和回圈佇列

爲什麼要寫這篇部落格？

嵌入式開發中，在很多的環境下無法使用官方庫，可以自己寫數據結構，進行使用。

佇列特點：先進先出

• 構造
• 入隊
• 遍歷
• 出隊
• 釋放記憶體

結構體定義和初始化構造

// 請在下面 下麪實現佇列 Queue
typedef struct Queue{
    // 編號
    int *data;
    int head, tail, length;   
}Queue;

// 請在下面 下麪實現初始化函數 init
void init(Queue *q, int length){
    q->data = (int*)malloc(sizeof(int) * length);
    q->length = length;
    q->head = 0;
    q->tail = -1;
}

入隊方法

• 判斷佇列是否已滿（判斷隊尾標記是否大於陣列長度）
• 更新隊尾標記（+1），將新元素存入隊尾

// 請在下面 下麪實現插入函數 push
int push(Queue *q, int element){
    //判斷佇列是否已滿
    if(q->tail+1 >= q->length){
        return ERROR;
    }
    q->tail++;
    q->data[q->tail] = element;
    return OK;
}

出隊方法

• 比較隊尾標記和隊首標記的大小，當隊首標記大於隊尾標記則說明佇列爲空，此時出隊是非法操作。
• 令隊首標記後移一位，隊首標記後移即視爲原隊首出隊。（這裏的記憶體依然可以通過data進行存取）

// 請在下面 下麪實現刪除隊首元素函數 pop
void pop(Queue *q){
    // 這裏沒有刪除隊首元素記憶體，只不過將頭指示後移了
    q->head++;
}

遍歷方法

• 輸出隊首標記所在元素
• 隊首標記後移一位
• 若隊尾標記和隊首標記相等，輸出最後一個元素，否則返回步驟一。

void output(Queue *q){
    for(int i = q->head; i <= q->tail; i++){
        printf("%d ", q->data[i]);
    }
    printf("\n");
}

判斷佇列是否爲空empty和輸出隊首元素front

// 請在下面 下麪實現隊首元素輸出函數 front
// 這裏不是return q->data[0]，是因爲head的值是變化的，記錄了多少元素出隊。
int front(Queue *q){
    return q->data[q->head];
}

// 請在下面 下麪實現判斷佇列是否爲空的函數 empty
// 非空的話，head<tail，則返回0
int empty(Queue *q){
    return q->head > q->tail;
}

釋放記憶體

void clear(Queue *q){
    free(q->data);
    free(q);
}

 

回圈佇列實現

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

#define ERROR 0
#define OK 1

typedef struct Queue {
    int *data;
    int head, tail, length, count;
}Queue;

void init(Queue *q, int length) {
    q->data = (int *)malloc(sizeof(int) * length);
    q->length = length;
    q->head = 0;
    q->tail = -1;
    q->count = 0;
}

int push(Queue *q, int element) {
    if (q->count >= q->length) {
        return ERROR;
    }
    q->tail = (q->tail + 1) % q->length;
    q->data[q->tail] = element;
    q->count++;
    return OK;
}

void output(Queue *q) {
    int i = q->head;
    do {
        printf("%d ", q->data[i]);
        i = (i + 1) % q->length;
    } while(i != (q->tail + 1) % q->length);
    printf("\n");
}

int front(Queue *q) {
    return q->data[q->head];
}

void pop(Queue *q) {
    q->head = (q->head + 1)%q->length;
    q->count--;
}

int empty(Queue *q) {
    return q->count == 0;
}

void clear(Queue *q) {
    free(q->data);
    free(q);
}

int main() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    init(q, 100);
    for (int i = 1; i <= 10; i++) {
        push(q, i);
    }
    output(q);
    if (!empty(q)) {
        printf("%d\n", front(q));
        pop(q);        
    }
    output(q);
    clear(q);
    return 0;
}

以下是回圈佇列的基本方法流程示意圖

初始位置

向佇列中新增1-5，直到全部佔滿

隊首1出隊

再次入隊，可以看到存取的是data[0]處的記憶體

再讓隊首出隊