嵌入式培訓之數據結構學習（五）棧與隊列

一、棧

（一）棧的基本概念

1、棧的定義：

注：線性表中的棧在堆區（因為是malloc來的）；系統中的棧區存儲局部變量、函數形參、函數返回值地址。

2、棧頂和棧底：

????????允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)，不含任何數據元素的棧稱為空棧。

3、 LIFO 結構：棧又稱為后進先出(LastInFirst0ut)的線性表。

4、棧示意圖：

top為棧頂指針

5、棧對線性表的插入和刪除的位置進行了限制，并沒有對元素進出的時間進行限制，

也就是說，在不是所有元素都進棧的情況下，事先進去的元素也可以出棧，只要保證是

棧頂元素出棧就可以。

6、應用：解決的問題要回溯、遞歸可以用鏈棧；

? ? ? ? ? ? ? ?有優先級問題的用棧處理。

（1）直觀應用（eg：gdb調試中的where命令）：函數調用返回原函數用棧結構（一層

一層進、一層一層退）；

（2）（3 + 5 * 6）四則運算表達式

優先級問題、字符串解析（先掃一遍表達式，再套用優先級順序對優先級高的優先處理，最后在退回來處理表達式）。

（二）鏈棧的基本操作

1、創建鏈棧

LinkStack* CreateLinkStack()?
{?
? ? // 分配鏈棧結構體空間，void* 強轉為 LinkStack*?
? ? LinkStack* ls = (LinkStack*)malloc(sizeof(LinkStack));?
? ? if(NULL == ls)?
? ? {?
? ? ? ? // 打印錯誤信息到標準錯誤流?
? ? ? ? fprintf(stderr,"CreateLinkStack malloc\n");?
? ? ? ? return NULL; // 分配失敗返回空?
? ? }?
? ? ls->top = NULL; // 初始化棧頂指針為空（空棧）?
? ? ls->clen = 0; // 初始化棧長度為0?
? ? return ls; // 返回創建好的鏈棧指針?
}

2、入棧

int PushLinkStack(LinkStack* ls, DATATYPE* data)?
{?
? ? // 分配新節點空間?
? ? LinkStackNode* newnode = malloc(sizeof(LinkStackNode));?
? ? if(NULL == newnode)?
? ? {?
? ? ? ? fprintf(stderr,"PushLinkStack malloc\n"); // 打印內存分配失敗信息?
? ? ? ? return 1; // 失敗返回錯誤碼1?
? ? }?
? ? // 將數據拷貝到新節點的數據域?
? ? memcpy(&newnode->data, data, sizeof(DATATYPE));?
? ? newnode->next = NULL; // 新節點初始next指針為空?
? ? newnode->next = ls->top; // 新節點next指向原棧頂節點（頭插法）?
? ? ls->top = newnode; // 棧頂更新為新節點?
? ? ls->clen++; // 棧長度加1?
? ? return 0; // 成功返回0（原代碼缺失return，需補充）
}

3、出棧

int PopLinkStack(LinkStack* ls)?
{?
? ? if(IsEmptyLinkStack(ls)) // 檢查棧是否為空?
? ? {?
? ? ? ? return 1; // 空棧返回錯誤碼1?
? ? }?
? ? LinkStackNode* tmp = ls->top; // 保存當前棧頂節點指針?
? ? ls->top = ls->top->next; // 棧頂指針后移一位（指向原次棧頂）?
? ? free(tmp); // 釋放原棧頂節點內存?
? ? ls->clen--; // 棧長度減1?
? ? return 0; // 成功返回0?
}

4、判斷棧空

int IsEmptyLinkStack(LinkStack* ls)?
{?
? ? // 棧長度為0時返回1（真），否則返回0（假）?
? ? return 0 == ls->clen;?
}

5、獲取棧頂元素

DATATYPE* GetTopLinkStack(LinkStack* ls)?
{?
? ? if(IsEmptyLinkStack(ls)) // 檢查棧是否為空?
? ? {?
? ? ? ? return NULL; // 空棧返回空指針?
? ? }?
? ? // 返回棧頂節點數據域的地址（需確保調用時不為空）?
? ? return &ls->top->data;?
}

6、銷毀鏈棧

int DestroyLinkStack(LinkStack* ls)?
{?
? ? int len = GetSizeLinkStack(ls); // 獲取棧當前長度?
? ? for(int i = 0; i < len; ++i)?
? ? {?
? ? ? ? PopLinkStack(ls); // 循環調用出棧函數釋放所有節點?
? ? }?
? ? free(ls); // 釋放鏈棧結構體本身的內存?
? ? return 0; // 成功返回0?
}

注：查看是否內存泄漏：valgrind? ./app

7、獲取棧長度

int GetSizeLinkStack(LinkStack* ls)?
{?
? ? // 直接返回結構體中記錄的棧長度（O(1)時間復雜度）?
? ? return ls->clen;?
}

（三）棧練習：C語言文本檢查器（符號匹配）

1、代碼：

（1）文件讀取函數 readfile
?int readfile(char *filename, char *filecontext)?
{?
? ? // 以只讀模式打開文件?
? ? FILE *fp = fopen(filename, "r");?
? ? if (NULL == fp)?
? ? {?
? ? ? ? return 1; // 打開失敗返回1?
? ? }?
? ? // 從文件讀取1024字節到filecontext緩沖區，返回實際讀取塊數（此處塊大小為1字節）?
? ? fread(filecontext, 1024, 1, fp);?
? ? fclose(fp); // 關閉文件?
? ? return 0; // 成功返回0?
}

（2）主函數 main
?
int main(int argc, char **argv)?
{?
? ? char buf[1024] = {0}; // 初始化1024字節緩沖區?
? ? int ret = readfile("/home/linux/2.c", buf); // 讀取文件內容到buf?
? ? if (1 == ret)?
? ? {?
? ? ? ? return 1; // 讀取失敗直接退出?
? ? }?

? ? LinkStack *ls = CreateLinkStack(); // 創建鏈棧用于符號匹配?
? ? char *tmp = buf; // 臨時指針指向緩沖區起始位置?
? ? DATATYPE data = {0}; // 存儲符號及其行列信息的結構體?
? ? int row = 1; // 當前行號，初始為1?
? ? int col = 1; // 當前列號，初始為1?
? ? DATATYPE *top; // 用于存儲棧頂元素的指針?

? ? while (*tmp) // 遍歷緩沖區直到遇到'\0'?
? ? {?
? ? ? ? memset(&data, 0, sizeof(DATATYPE)); // 清空結構體數據?
? ? ? ? switch (*tmp) // 根據當前字符判斷類型?
? ? ? ? {
? ? ? ? ? ? // 處理左括號：( [ {
? ? ? ? ? ? case '(':?
? ? ? ? ? ? case '[':?
? ? ? ? ? ? case '{':?
? ? ? ? ? ? ? ? data.c = *tmp; // 存儲符號?
? ? ? ? ? ? ? ? data.col = col; // 存儲列號?
? ? ? ? ? ? ? ? data.row = row; // 存儲行號?
? ? ? ? ? ? ? ? PushLinkStack(ls, &data); // 將符號入棧?
? ? ? ? ? ? ? ? break;

? ? ? ? ? ? // 處理右括號：)
? ? ? ? ? ? case ')':?
? ? ? ? ? ? ? ? top = GetTopLinkStack(ls); // 獲取棧頂元素?
? ? ? ? ? ? ? ? // 棧頂存在且為匹配的'('?
? ? ? ? ? ? ? ? if ('(' == top->c && NULL != top)?
? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? PopLinkStack(ls); // 匹配成功，出棧?
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? else?
? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? if (NULL == top) // 棧空，說明缺少左括號?
? ? ? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? ? ? // 輸出錯誤：右括號無匹配左括號?
? ? ? ? ? ? ? ? ? ? ? ? printf("sym:%c row:%d col%d\n", ')', row, col);?
? ? ? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? ? ? else // 棧頂符號不匹配（如棧頂是'['或'{'）?
? ? ? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? ? ? // 輸出錯誤：棧頂符號與當前右括號不匹配?
? ? ? ? ? ? ? ? ? ? ? ? printf(
? ? ? ? ? ? ? ? ? ? ? ? ? ? "top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n",?
? ? ? ? ? ? ? ? ? ? ? ? ? ? top->c, top->row, top->col, *tmp, row, col);?
? ? ? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? ? ? return 1; // 匹配失敗，程序退出?
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? break;

? ? ? ? ? ? // 處理右括號：]（邏輯同'）'）
? ? ? ? ? ? case ']':?
? ? ? ? ? ? ? ? top = GetTopLinkStack(ls);?
? ? ? ? ? ? ? ? if ('[' == top->c && NULL != top)?
? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? PopLinkStack(ls);?
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? else?
? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? if (NULL == top)?
? ? ? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? ? ? printf("sym:%c row:%d col%d\n", ']', row, col); // 注意此處誤寫為')'，應為']'?
? ? ? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? ? ? else?
? ? ? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? ? ? printf(
? ? ? ? ? ? ? ? ? ? ? ? ? ? "top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n",?
? ? ? ? ? ? ? ? ? ? ? ? ? ? top->c, top->row, top->col, *tmp, row, col);?
? ? ? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? ? ? return 1;?
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? break;

? ? ? ? ? ? // 處理右括號：}（邏輯同'）'）
? ? ? ? ? ? case '}':?
? ? ? ? ? ? ? ? top = GetTopLinkStack(ls);?
? ? ? ? ? ? ? ? if ('{' == top->c && NULL != top)?
? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? PopLinkStack(ls);?
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? else?
? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? if (NULL == top)?
? ? ? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? ? ? printf("sym:%c row:%d col%d\n", '}', row, col); // 注意此處誤寫為')'，應為'}'?
? ? ? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? ? ? else?
? ? ? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? ? ? printf(
? ? ? ? ? ? ? ? ? ? ? ? ? ? "top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n",?
? ? ? ? ? ? ? ? ? ? ? ? ? ? top->c, top->row, top->col, *tmp, row, col);?
? ? ? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? ? ? return 1;?
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? break;
? ? ? ? }

? ? ? ? col++; // 列號遞增?
? ? ? ? if ('\n' == *tmp) // 遇到換行符?
? ? ? ? {?
? ? ? ? ? ? col = 1; // 列號重置為1?
? ? ? ? ? ? row++; // 行號遞增?
? ? ? ? }?
? ? ? ? tmp++; // 移動到下一個字符?
? ? }

? ? // 遍歷結束后檢查棧是否為空（所有左括號是否匹配）
? ? if ('\0' == *tmp && IsEmptyLinkStack(ls))?
? ? {?
? ? ? ? printf("ok"); // 完全匹配，輸出"ok"?
? ? }?
? ? else?
? ? {?
? ? ? ? top = GetTopLinkStack(ls); // 獲取剩余未匹配的左括號?
? ? ? ? // 輸出未匹配的左括號及其位置?
? ? ? ? printf("top sym:%c row:%d col%d\n", top->c, top->row, top->col);?
? ? }

? ? DestroyLinkStack(ls); // 銷毀鏈棧，釋放內存?
? ? return 0;?
}

2、輸出結果：匹配成功輸出ok，匹配不成功輸出符號及其位置。

二、隊列

（一）隊列的基本概念

1、隊列的定義：

2、FIFO結構：隊列是一種先進先出(FirstInFirst0ut)的線性表。

? ? ?允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。

3、隊列示意圖

clen = （尾巴 - 頭 + 長度）

4、應用：計算機做緩沖用隊列；

5、循環隊列（圓環）：（求余就循環起來）

6、面試問題：滿隊判斷條件：尾巴+1==頭? ?(tail + 1 ) % tlen == head

? ? ? ? ? ? ? ? ? ? ? ?空隊：尾巴==頭? ?tail == head

（二）隊列的基本操作

1、創建順序隊列

SeqQueue* CreateSeqQue(int len)?
{?
? ? // 分配順序隊列結構體空間，強轉為 SeqQueue*?
? ? SeqQueue* sq = (SeqQueue*)malloc(sizeof(SeqQueue));?
? ? if(NULL == sq)?
? ? {?
? ? ? ? // 打印結構體內存分配失敗信息到標準錯誤流?
? ? ? ? fprintf(stderr,"CreateSeqQue malloc\n");?
? ? ? ? return NULL; // 失敗返回空?
? ? }?
? ? // 分配隊列數據存儲數組空間（容量為len）?
? ? sq->array = malloc(sizeof(DATATYPE)*len);?
? ? if(NULL == sq->array)?
? ? {?
? ? ? ? // 打印數組內存分配失敗信息?
? ? ? ? fprintf(stderr,"CreateSeqQue malloc\n");?
? ? ? ? free(sq); // 釋放已分配的結構體空間（避免內存泄漏）?
? ? ? ? return NULL;?
? ? }?
? ? sq->head = 0; // 初始化頭指針（指向隊頭元素前一個位置）?
? ? sq->tail = 0; // 初始化尾指針（指向隊尾元素位置）?
? ? sq->tlen = len; // 記錄隊列總長度（容量）?
? ? return sq; // 返回創建好的順序隊列指針?
}

2、判斷隊空

int IsEmptySeqQue(SeqQueue* sq)?
{?
? ? // 頭指針等于尾指針時隊列為空（返回1表示真，0表示假）?
? ? return sq->head == sq->tail;?
}

3、判斷隊滿

int IsFullSeqQue(SeqQueue* sq)?
{?
? ? // 尾指針下一個位置（循環取模）等于頭指針時隊滿?
? ? return (sq->tail + 1) % sq->tlen == sq->head;?
}

4、入隊

int EnterSeqQue(SeqQueue* sq, DATATYPE* data)?
{?
? ? if(IsFullSeqQue(sq))?
? ? {?
? ? ? ? // 打印隊滿錯誤信息?
? ? ? ? fprintf(stderr,"EnterSeqQue,SeqQueue full\n");?
? ? ? ? return 1; // 失敗返回錯誤碼1?
? ? }?
? ? // 將數據拷貝到尾指針當前位置的數組元素中?
? ? memcpy(&sq->array[sq->tail], data, sizeof(DATATYPE));?
? ? // 尾指針后移一位（循環隊列，取模實現環形）?
? ? sq->tail = (sq->tail + 1) % sq->tlen;?
? ? return 0; // 成功返回0?
}

5、出隊

int QuitSeqQue(SeqQueue* sq)?
{?
? ? if(IsEmptySeqQue(sq))?
? ? {?
? ? ? ? // 打印隊空錯誤信息?
? ? ? ? fprintf(stderr,"QuitSeqQue SeqQueue empty\n");?
? ? ? ? return 1; // 失敗返回錯誤碼1?
? ? }?
? ? // 頭指針后移一位（指向實際隊頭元素，取模實現環形）?
? ? sq->head = (sq->head + 1) % sq->tlen;?
? ? return 0; // 成功返回0?
}

6、獲取隊頭元素

DATATYPE* GetHeadSeqQue(SeqQueue* sq)?
{?
? ? if(IsEmptySeqQue(sq))?
? ? {?
? ? ? ? return NULL; // 隊空返回空指針?
? ? }?
? ? // 返回隊頭元素地址（頭指針當前指向的是隊頭元素的位置）?
? ? return &sq->array[sq->head];?
}