棧是計算機科學中最基礎且重要的數據結構之一，它遵循"后進先出"（LIFO）的原則。想象一下一疊盤子，你只能從最上面取放，這就是棧的直觀體現。本文將用C語言帶你一步步實現一個順序棧，即使你是編程小白也能輕松理解！

什么是順序棧？

順序棧是使用數組實現的棧結構，具有以下特點：

• 元素在內存中連續存儲

• 有一個指針(top)始終指向棧頂位置

• 支持基本的入棧(push)和出棧(pop)操作

代碼實現詳解

1. 頭文件定義(Stack.h)

首先我們需要定義棧的結構和聲明相關操作函數：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>// 定義棧中元素的數據類型
typedef int STDataType;// 棧的結構定義
typedef struct Stack
{STDataType* _a;    // 指向動態數組的指針int _top;          // 棧頂位置int _capacity;     // 當前容量
}Stack;// 函數聲明
void StackInit(Stack* ps);                 // 初始化棧
void StackPush(Stack* ps, STDataType data);// 入棧
void StackPop(Stack* ps);                  // 出棧
STDataType StackTop(Stack* ps);            // 獲取棧頂元素
int StackSize(Stack* ps);                  // 獲取元素個數
int StackEmpty(Stack* ps);                 // 檢查棧是否為空
void StackDestroy(Stack* ps);              // 銷毀棧

2. 棧的實現(Stack.c)

初始化棧

void StackInit(Stack* ps) {assert(ps);  // 確保指針有效ps->_a = NULL;ps->_top = 0;      // 棧頂指向下一個空閑位置ps->_capacity = 0; // 初始容量為0
}

初始化時，我們將數組指針設為NULL，棧頂位置和容量都設為0。

入棧操作

void StackPush(Stack* ps, STDataType data) {assert(ps);// 檢查棧是否已滿，需要擴容if (ps->_capacity == ps->_top) {// 如果容量為0，初始分配4個元素空間，否則容量翻倍int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;// 重新分配內存STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * newcapacity);if (tmp == NULL) {perror("malloc error");return;}ps->_capacity = newcapacity;ps->_a = tmp;}// 將數據放入棧頂并更新棧頂位置ps->_a[ps->_top++] = data;
}

這里使用了動態內存分配，當棧滿時自動擴容，這是實現可變大小棧的關鍵。

出棧操作

void StackPop(Stack* ps) {assert(ps);assert(ps->_top > 0); // 確保棧不為空ps->_top--; // 簡單地將棧頂指針下移
}

出棧操作實際上只是移動棧頂指針，并不真正刪除數據。

其他輔助函數

// 獲取棧頂元素
STDataType StackTop(Stack* ps) {assert(ps);assert(ps->_top > 0); // 確保棧不為空return ps->_a[ps->_top - 1]; // 返回棧頂元素
}// 獲取棧中元素個數
int StackSize(Stack* ps) {assert(ps);return ps->_top; // 棧頂位置就是元素個數
}// 檢查棧是否為空
int StackEmpty(Stack* ps) {assert(ps);return ps->_top == 0; // 如果棧頂為0，棧為空
}// 銷毀棧，釋放內存
void StackDestroy(Stack* ps) {free(ps->_a);        // 釋放數組內存ps->_a = NULL;       // 指針置空防止野指針ps->_top = 0;        // 重置棧頂ps->_capacity = 0;   // 重置容量
}

3. 測試代碼(test.c)

#include "Stack.h"void TestStack(Stack* p) {// 測試初始化StackInit(p);// 測試入棧 - 添加6個元素StackPush(p, 1);StackPush(p, 2);StackPush(p, 3);StackPush(p, 4);StackPush(p, 5);StackPush(p, 6);// 測試棧是否為空且查看棧頂元素if (!StackEmpty(p))printf("棧頂元素: %d \n", StackTop(p));else printf("棧為空\n");// 測試出棧 - 彈出5個元素StackPop(p);StackPop(p);StackPop(p);StackPop(p);StackPop(p);// 測試棧元素個數printf("棧中元素個數: %d \n", StackSize(p));// 銷毀棧StackDestroy(p);
}int main() {Stack p;TestStack(&p);return 0;
}

運行結果分析

運行測試代碼，你會看到以下輸出：

棧頂元素: 6
棧中元素個數: 1

這是因為我們依次壓入了1-6六個數字，然后彈出了五個，最后只剩下一個元素。

關鍵點解析

1. 動態擴容：當棧滿時，我們通過realloc函數將容量翻倍，這是常見的擴容策略

2. 棧頂指針：_top指向的是下一個空閑位置，而不是當前棧頂元素的位置

3. 斷言使用：使用assert確保函數參數的有效性，提高代碼健壯性

4. 內存管理：記得在不再使用棧時調用StackDestroy釋放內存，防止內存泄漏

常見問題

1. Q: 為什么出棧操作不真正刪除數據？
   A: 只需要移動棧頂指針，下次入棧時會覆蓋該位置，提高效率

2. Q: 初始容量為什么設為4？
   A: 這是一個經驗值，太小會導致頻繁擴容，太大浪費內存

3. Q: 如何修改棧中存儲的數據類型？
   A: 只需修改Stack.h中的STDataType定義即可