前言

????????無論你是計算機科學專業的學生、程序設計的愛好者，還是正在準備面試的求職者，本文將為你提供一份全面而深入的棧和隊列指南。讓我們一起探索棧和隊列的雙重魅力，為你的編程之路增添新的色彩。

---

1. 棧

1.1棧的概念及結構

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。

棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。

• 壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
• 出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

?

?1.2 棧的實現

????????棧的實現方法有兩種，一種是順序表的棧，另外一種就是鏈表實現的棧。相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小，所以這里我們使用順序表來實現棧。

?????????如果熟練順序表和鏈表操作，那棧就會相當輕松，棧的入棧出棧就相當于是尾插尾刪，順序表尾插尾刪的效率高，這也是使用順序表實現的原因。

1.2.1 棧的定義

首先我們需要先定義一個棧：

typedef int Datatype;
typedef struct Stack
{Datatype* a;int top;int capacity;
}Stack;

?棧中有棧頂（top），有棧的容量（size），還有存儲的數據（a）；

?1.2.2? 棧的初始化

?

void InItStack(Stack* ps)
{assert(ps);ps->top = 0;ps->a = NULL;ps->capacity = 0;
}

?????????這里對棧進行初始化時棧頂（top）可以置為-1，也可以置為0，置為0為了便于使用top作為數組下標插入數據。

1.2.3 入棧

????????棧已經定義完成并且進行了初始化，接下來就是入棧操作。這里與順序表的尾插略微有些不同。

void StackPush(Stack* ps, Datatype x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);Datatype* tmp = (Datatype*)realloc(ps->a, sizeof(Datatype) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;//top初始化為0，可以直接作為數組下標ps->top++;//入棧后top++，便于統計元素個數和下次入棧
}

????????由于我們初始化時將棧的容量置為0，在這里我們在入棧操作時就需要進行開辟空間，但這里如果我們使用malloc開辟空間，就還需要進行擴容操作，所以我們直接使用realloc進行開辟空間。

?realloc在擴容時，如果原始區域空間為0，那么它的作用就類似于malloc。

?????????此外我們還需要有新開辟空間的大小，這里我們直接使用一個判斷語句：newsize = (ps->size == 0 ? 4 : ps->size * 2);? 如果size等于0就開辟4個存儲數據的空間，如果不等于0就直接擴容為2倍。

1.2.4 出棧

?出棧操作就很簡單了，也不需要銷毀，直接進行top--：

void StackPop(Stack* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}

????????但我們需要注意棧為空的情況，所有使用assert強制檢查，如果為空直接報錯終止程序，簡單粗暴。

1.2.5? 棧的元素個數

統計棧的元素個數接口也很簡單，top就是棧中元素的個數

int Stacksize(Stack* ps)
{assert(ps);return ps->top;
}

1.2.6 棧頂數據

Datatype TopData(Stack* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}

這個也非常簡單，需要注意棧為空的情況。

1.2.7 棧的判空

bool IsEmpty(Stack* ps)
{assert(ps);return (ps->top == 0);
}

?2.棧的應用

?????????這些棧的基本操作我們已經實現了，接下來我們來實際應用一下。雖然棧的基本操作更為簡單，但是棧在應用時數據的結構更加復雜，前邊的順序表和鏈表是棧和隊列的基礎。

?2.1 題目一：括號匹配

????????這道題目我們可以使用數組實現并解決，但我們已經了解了棧，這道題目我們就使用順序表棧來實現。我們可以直接復制上述棧基本操作的代碼。將?typedef? int? Datatype;

?改為：typedef? char? Datatype;

題目描述：

?示例：

?題目鏈接：

有效括號

2.1.1 思路

?????????這道題目的思路很明確，入棧左括號，遇到匹配的右括號就出棧。如果最終棧為空就匹配成功。但匹配失敗的情況有很多，接下來我們進行逐個分析。

?2.1.2 分析

? ? ? ? ?首先是入棧，如果為左括號就入棧，為右括號就匹配出棧。這里使用if…else語句更為簡潔，入棧就需要我們調用入棧的函數接口。

? ? ? ? 其次就是匹配、出棧。但在匹配之前我們還需要考慮特殊情況，就是如果沒有出棧元素就直接匹配的情況，所以首先我們需要有一個判空操作，如果匹配時棧就為空就直接匹配失敗，并銷毀棧，這個屬于左括號與右括號數量匹配失敗。

? ? ? ? ?接著就是順序匹配失敗，這里就需要我們用到棧頂元素了，如果棧頂元素與匹配的括號不匹配就直接返回false，匹配失敗，銷毀棧。

? ? ? ? 最后，匹配結束，存放括號數組為空，棧也為空就匹配成功。

?2.1.3 題解

匹配括號接口：

bool isValid(char* s) {Stack st;InItStack(&st);char top;while (*s){if (*s == '(' || *s == '[' || *s == '{'){StackPush(&st, *s);}else{if(IsEmpty(&st)){DestoryStack(&st);return false;}top=TopData(&st);StackPop(&st);if((*s==']'&&top!='[')||(*s==')'&&top!='(')||(*s=='}'&&top!='{')){DestoryStack(&st);return false;}}s++;}bool ret = IsEmpty(&st);DestoryStack(&st);return ret;
}

整體代碼：

typedef char Datatype;
typedef struct Stack
{Datatype* a;int top;int size;
}Stack;void InItStack(Stack* ps);void DestoryStack(Stack* ps);void StackPush(Stack* ps, Datatype x);void StackPop(Stack* ps);int Stacksize(Stack* ps);Datatype TopData(Stack* ps);bool IsEmpty(Stack* ps);void InItStack(Stack* ps)
{assert(ps);ps->top = 0;ps->a = NULL;ps->size = 0;
}void DestoryStack(Stack* ps)
{assert(ps);ps->top = ps->size = 0;free(ps->a);ps->a = NULL;
}
void StackPush(Stack* ps, Datatype x)
{assert(ps);if (ps->top == ps->size){int newsize = (ps->size == 0 ? 4 : ps->size * 2);Datatype* tmp = (Datatype*)realloc(ps->a, sizeof(Datatype) * newsize);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->size = newsize;}ps->a[ps->top] = x;ps->top++;
}
void StackPop(Stack* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}
int Stacksize(Stack* ps)
{assert(ps);return ps->top;
}
Datatype TopData(Stack* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}
bool IsEmpty(Stack* ps)
{assert(ps);return (ps->top == 0);
}
bool isValid(char* s) {Stack st;InItStack(&st);char top;while (*s){if (*s == '(' || *s == '[' || *s == '{'){StackPush(&st, *s);}else{if(IsEmpty(&st)){DestoryStack(&st);return false;}top=TopData(&st);StackPop(&st);if((*s==']'&&top!='[')||(*s==')'&&top!='(')||(*s=='}'&&top!='{')){DestoryStack(&st);return false;}}s++;}bool ret = IsEmpty(&st);DestoryStack(&st);return ret;
}

?????????棧相對于鏈表和順序表沒有那么多的操作，更為簡單，但在實際應用時數據結構更加復雜，但是別擔心，后續學習C++后可以直接使用現成的庫函數，不需要再對棧的各個操作進行實現。

---

??

總結

????????棧是一種重要的數據結構，它以后進先出的方式操作數據。棧在遞歸算法、表達式求值、函數調用等場景中發揮著重要作用。通過學習棧，我們能夠更好地理解數據結構的本質和算法的設計思想。棧不僅僅是一種數據存儲的方式，更是一種思維方式和問題解決的工具。無論是計算機科學的學習者、程序設計的愛好者，還是正在準備面試的求職者，通過探索棧的原理和應用，我們能夠提升自己的編程能力和解決問題的能力。讓我們一起深入探索棧的魅力，為編程之路增添新的色彩。最后，感謝閱讀！