【作者主頁】siy2333
【專欄介紹】?c語言日寄?：這是一個專注于C語言刷題的專欄，精選題目，搭配詳細題解、拓展算法。從基礎語法到復雜算法，題目涉及的知識點全面覆蓋，助力你系統提升。無論你是初學者，還是進階開發者，這里都能滿足你的需求！
【食用方法】1.根據題目自行嘗試 2.查看基礎思路完善題解 3.學習拓展算法
【Gitee鏈接】資源保存在我的Gitee倉庫：https://gitee.com/siy2333/study

---

---

前言：

在計算機科學中，數據結構是組織和存儲數據的方式，而棧（Stack）是其中一種非常基礎且重要的數據結構。它遵循后進先出（Last In First Out，LIFO）的原則，就像一疊盤子，你只能在最上面添加或移除盤子。本文將深入探討棧的原理、實現方式以及應用場景，幫助讀者更好地理解和運用這一數據結構。

文末附帶完整的帶有標準注釋的c語言頭文件以及源文件。

---

棧的基本概念

棧是一種線性數據結構，它只允許在表的一端進行插入和刪除操作。這一端被稱為棧頂（Top），而另一端被稱為棧底（Bottom）。棧的基本操作包括：

1. 入棧（Push）：將一個元素添加到棧頂。
2. 出棧（Pop）：移除棧頂的元素。
3. 查看棧頂元素（Top）：獲取棧頂元素的值，但不移除它。
4. 檢查棧是否為空（Empty）：判斷棧中是否還有元素。
5. 獲取棧的大小（Size）：返回棧中元素的數量。

這些操作的實現方式會因具體的編程語言和數據結構設計而有所不同，但基本原理是一致的。

棧的實現

棧可以通過數組或鏈表來實現。在本文中，我們將重點介紹基于數組的棧實現，因為它更簡單且易于理解。以下是基于數組的棧實現的關鍵點：

初始化

在使用棧之前，需要對其進行初始化。這通常包括分配內存空間、設置棧頂指針和棧的容量。在我們的代碼示例中，棧的初始化函數STInit會為棧分配初始容量為4的內存空間，并將棧頂指針設置為0。

void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0; // The next position of the current stack top elementreturn;
}

入棧

當向棧中添加元素時，需要檢查棧是否已滿。如果棧已滿，則需要擴容。擴容通常是通過分配更大的內存空間來實現的。在我們的代碼中，當棧滿時，會將棧的容量加倍。

void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){STDataType* point = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (point == NULL){perror("realloc fail");return;}ps->a = point;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;return;
}

出棧

出棧操作相對簡單，只需要將棧頂指針減1即可。但在出棧之前，需要檢查棧是否為空，以避免出現錯誤。

void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;return;
}

查看棧頂元素

查看棧頂元素的操作也很簡單，只需要返回棧頂指針所指向的元素即可。同樣，在執行此操作之前，需要檢查棧是否為空。

STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

檢查棧是否為空

檢查棧是否為空的操作可以通過比較棧頂指針是否為0來實現。

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

獲取棧的大小

獲取棧的大小的操作可以通過返回棧頂指針的值來實現。

int STSize(ST* ps)
{assert(ps);return ps->top;
}

銷毀棧

在使用完棧后，需要對其進行銷毀，以釋放分配的內存空間。銷毀棧的操作包括釋放內存空間、將棧頂指針和容量設置為0。

void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;return;
}

棧的應用場景

棧在計算機科學中有著廣泛的應用，以下是一些常見的應用場景：

函數調用

在編程語言中，函數調用是通過棧來實現的。當一個函數被調用時，它的參數、返回地址和局部變量等信息會被壓入調用棧中。當函數執行完畢后，這些信息會被彈出棧，程序會返回到調用函數的位置繼續執行。

表達式求值

棧可以用于表達式的求值。例如，在計算后綴表達式時，可以使用一個棧來存儲操作數。當遇到一個操作符時，從棧中彈出兩個操作數，進行相應的運算，然后將結果壓入棧中。當表達式計算完畢時，棧頂的元素就是表達式的值。

括號匹配

棧可以用于檢查括號是否匹配。當遇到一個左括號時，將其壓入棧中；當遇到一個右括號時，從棧中彈出一個左括號。如果在彈出左括號時棧為空，或者彈出的左括號與右括號不匹配，則說明括號不匹配。

瀏覽器的前進和后退功能

瀏覽器的前進和后退功能也可以通過棧來實現。當用戶訪問一個網頁時，將該網頁的地址壓入一個棧中；當用戶點擊后退按鈕時，從棧中彈出一個網頁地址并跳轉到該網頁；當用戶點擊前進按鈕時，將彈出的網頁地址壓入另一個棧中。

棧的優缺點

棧的優點包括：

1. 簡單易用：棧的實現相對簡單，操作也容易理解。
2. 高效：棧的基本操作（如入棧、出棧、查看棧頂元素等）的時間復雜度為O(1)。
3. 適用范圍廣：棧在計算機科學中有著廣泛的應用，如函數調用、表達式求值、回溯算法等。

然而，棧也有一些缺點：

1. 容量限制：如果棧的容量有限，可能會出現棧溢出的情況。雖然可以通過動態擴容來解決這個問題，但動態擴容會增加時間和空間的開銷。
2. 只能在一端操作：棧只能在棧頂進行插入和刪除操作，不能在其他位置進行操作。

棧的優化

雖然棧的基本操作已經非常高效，但在某些情況下，我們仍然可以通過一些優化手段來提高棧的性能。以下是一些常見的優化方法：

預分配內存

在初始化棧時，可以預分配一定量的內存空間，以減少動態擴容的次數。這可以提高棧的性能，但會增加內存的使用量。

使用循環緩沖區

循環緩沖區是一種特殊的數組結構，它可以循環使用內存空間。通過使用循環緩沖區，可以減少內存的分配和釋放次數，從而提高棧的性能。

棧的測試

為了驗證棧的正確性和性能，我們需要對其進行測試。以下是一個簡單的測試程序，用于測試棧的基本操作：

#include"Stack.h"void Test1()
{ST head;STInit(&head);STPush(&head, 1);STPush(&head, 2);STPush(&head, 3);STPush(&head, 4);STPush(&head, 5);while (!STEmpty(&head)){printf("%d ", STTop(&head));STPop(&head);}printf("\n");return;
}int main()
{Test1();return 0;
}

在這個測試程序中，我們首先初始化了一個棧，然后依次向棧中添加了5個元素。接著，我們依次從棧中彈出元素，并打印出每個元素的值。最后，我們銷毀了棧。

完整代碼

頭文件

#pragma once/**
* @file Stack.h
* @brief The header file of the Stack.
* @author siy2333
* @date 2025.5.11
*
* This header file defines the data structure and related operation functions of a Stack.
* Stack is a Last-In-First-Out (LIFO) data structure used for storing and managing data elements, supporting operations to add (push) and remove (pop) elements at the top, and is widely applied in program calling, expression evaluation, and other scenarios.
* Provides basic operations for adding, deleting, querying, and modifying.
*///Standard library header files included.
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>/**
* @brief The data types stored in the Stack.
*/
typedef int STDataType;/**
* @typedef struct Stack.
* @brief Structure definition of Stack.
*/
typedef struct Stack
{STDataType* a;		///< The pointer to the memory for the Stack.int top;			///< The next position of the current Stack top element.int capacity;		///< The size of capacity.
}ST;/**
* @brief Initialize Stack.
*/
void STInit(ST* ps);/**
* @brief Destory the Stack.
*/
void STDestory(ST* ps);/**
* @brief Store x in the top of the Stack.
*/
void STPush(ST* ps, STDataType x);/**
* @brief Delete x at the top of the Stack.
*/
void STPop(ST* ps);/**
* @brief return the capacity size of the Stack.
*/
int STSize(ST* ps);/**
* @brief Check whether the Stack is empty.
* @return If the Stack is empty, return 1; Otherwise, return 0.
*/
bool STEmpty(ST* ps);/**
* @brief Return the data at the top of the Stack.
* @return the data at the top of the Stack.
*/
STDataType STTop(ST* ps);

源文件

#include"Stack.h"/**
* @detailsThe faction use malloc to apply for 4 copies of memory for the Stack.The 0 will be store int the ps->top, it mean the next position of the current stack top element.The capacity will be set to 4.
* @warning ps mustn't be NULL.
*/
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;		//The next position of the current stack top elementreturn;
}/**
* @details The faction will free the memory for the Stack;The top will be set to 0;The capacity will be set to 0.
* @warning ps mustn't be NULL.
*/
void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;return;
}/**
* @details The faction will check whether the Stack is full;If the Stack is full, it will use realloc() to double the capacity, and refresh the ps->capacity.It will store the x in the ps->a[top], and refresh the ps->top.
* @warning ps mustn't be NULL.
*/
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){STDataType* point = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);if (point == NULL){perror("realloc fail");return;}ps->a = point;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;return;
}/**
* @details The function will refresh the ps->top.
* @warning ps musn't be NULL;
* @warning The Stack mustn't be empty.
*/
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;return;
}/**
* @warning ps mustn't be NULL;
*/
int STSize(ST* ps)
{assert(ps);return ps->top;
}/**
* @warning ps mustn't be NULL;
*/
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}/**
* @warning ps musn't be NULL;
* @warning The Stack mustn't be empty.
*/
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

棧的總結

棧是一種非常基礎且重要的數據結構，它遵循后進先出的原則。棧的基本操作包括入棧、出棧、查看棧頂元素、檢查棧是否為空和獲取棧的大小等。棧可以通過數組或鏈表來實現，其中基于數組的棧實現相對簡單且易于理解。棧在計算機科學中有著廣泛的應用，如函數調用、表達式求值、回溯算法等。雖然棧有一些缺點，但它的優點使其在許多場景下都非常有用。通過一些優化手段，我們可以進一步提高棧的性能。總之，棧是一種非常重要的數據結構，值得我們深入學習和研究。

希望本文對您理解棧有所幫助。如果您有任何問題或建議，歡迎在評論區留言討論。

[專欄鏈接QwQ] :?c語言日寄?CSDN
[關注博主ava]：siy2333
感謝觀看~ 我們下次再見!!