一、棧(Stack)詳解

1. 棧的基本概念

棧的定義與特性

• 后進先出(LIFO)：最后入棧的元素最先出棧

• 操作限制：只能在棧頂進行插入(push)和刪除(pop)操作

• 存儲位置：我們實現的鏈棧位于堆區(malloc分配)，系統棧區存儲函數調用信息

棧的示意圖（top為棧頂指針）

2. 鏈棧的基本操作實現

(1) 創建鏈棧

c

LinkStack* CreateLinkStack()
{LinkStack* ls = (LinkStack*)malloc(sizeof(LinkStack));if(NULL == ls){fprintf(stderr,"CreateLinkStack malloc\n");return NULL;}ls->top = NULL;   // 初始化棧頂指針ls->clen = 0;     // 初始化棧長度return ls;
}

(2) 入棧操作

c

int PushLinkStack(LinkStack* ls, DATATYPE* data)
{LinkStackNode* newnode = malloc(sizeof(LinkStackNode));if(NULL == newnode){fprintf(stderr,"PushLinkStack malloc\n");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = ls->top;  // 新節點指向原棧頂ls->top = newnode;        // 更新棧頂指針ls->clen++;return 0;
}

(3) 出棧操作

c

int PopLinkStack(LinkStack* ls)
{if(IsEmptyLinkStack(ls)) return 1;LinkStackNode* tmp = ls->top;ls->top = ls->top->next;  // 棧頂指針下移free(tmp);                // 釋放原棧頂節點ls->clen--;return 0;
}

(4) 其他操作

c

// 判斷棧空
int IsEmptyLinkStack(LinkStack* ls)
{return 0 == ls->clen;
}// 獲取棧頂元素
DATATYPE* GetTopLinkStack(LinkStack* ls)
{if(IsEmptyLinkStack(ls)) return NULL;return &ls->top->data;
}// 獲取棧長度
int GetSizeLinkStack(LinkStack* ls)
{return ls->clen;
}

//摧毀鏈棧

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

3. 棧的應用實例：C語言符號匹配檢查器

實現原理

1. 遇到左括號(,?[,?{時入棧

2. 遇到右括號),?],?}時與棧頂元素匹配

3. 匹配成功則出棧，失敗則報錯

核心代碼段

c

while (*tmp)
{switch (*tmp){case '(': case '[': case '{':data.c = *tmp;data.row = row;data.col = col;PushLinkStack(ls, &data);break;case ')':top = GetTopLinkStack(ls);if (top && '(' == top->c) {PopLinkStack(ls);} else {// 錯誤處理...}break;// 其他右括號處理類似...}// 更新行列計數...
}

二、隊列(Queue)詳解

1. 隊列的基本概念

隊列的定義與特性

• 先進先出(FIFO)：最先入隊的元素最先出隊

• 操作限制：隊尾(rear)插入，隊頭(front)刪除

• 循環隊列：通過取模運算實現空間的循環利用

隊列示意圖

2. 順序隊列的基本操作實現

(1) 創建順序隊列

c

SeqQueue* CreateSeqQue(int len)
{SeqQueue* sq = (SeqQueue*)malloc(sizeof(SeqQueue));if(NULL == sq) return NULL;sq->array = malloc(sizeof(DATATYPE)*len);if(NULL == sq->array){free(sq);return NULL;}sq->head = 0;    // 初始化頭指針sq->tail = 0;    // 初始化尾指針sq->tlen = len;  // 記錄隊列容量return sq;
}

(2) 入隊操作

c

int EnterSeqQue(SeqQueue* sq, DATATYPE* data)
{if(IsFullSeqQue(sq)) return 1;memcpy(&sq->array[sq->tail], data, sizeof(DATATYPE));sq->tail = (sq->tail + 1) % sq->tlen;  // 循環隊列處理return 0;
}

(3) 出隊操作

c

int QuitSeqQue(SeqQueue* sq)
{if(IsEmptySeqQue(sq)) return 1;sq->head = (sq->head + 1) % sq->tlen;  // 頭指針后移return 0;
}

(4) 隊滿/隊空判斷

c

// 判斷隊空
int IsEmptySeqQue(SeqQueue* sq)
{return sq->head == sq->tail;
}// 判斷隊滿
int IsFullSeqQue(SeqQueue* sq)
{return (sq->tail + 1) % sq->tlen == sq->head;
}

三、棧與隊列對比

特性	棧(Stack)	隊列(Queue)
原則	后進先出(LIFO)	先進先出(FIFO)
操作端	僅棧頂操作	隊尾入隊，隊頭出隊
應用	函數調用、表達式求值	任務調度、緩沖處理
實現	鏈式/順序	多為循環順序隊列

四、嵌入式開發建議

1. 棧的應用場景：

   • 函數調用棧管理

   • 中斷處理時的上下文保存

   • 遞歸算法實現

2. 隊列的應用場景：

   • 串口數據接收緩沖

   • 任務消息隊列

   • 多線程間的數據傳遞

3. 內存管理技巧：

   • 靜態分配內存池避免碎片

   • 合理設置棧/隊列大小

   • 使用valgrind工具檢測內存泄漏