匯總代碼見：登錄 - Gitee.com

上一篇文章：數據結構：雙向鏈表-CSDN博客

與本文相關的結構體傳參：自定義類型：結構體-CSDN博客

1.棧

1.1概念和結構

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（LastInFirstOut）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

棧底層結構選型：

棧的實現一般可以使用數組或者鏈表實現，相對而言，數組的結構實現更優一些。

原因：在入棧和出棧的時間復雜度均為O(1)的前提條件下，數組的內存利用率遠高于鏈表，尤其是在存儲小數據類型時。

1.2棧的實現

依舊建立三個文件：

1.2.1定義棧的結構

//定義棧的結構
typedef int STDataType;
typedef struct Stack {STDataType* arr;int top;//指向當前棧頂元素的索引--正好為棧中有效的數據個數int capacity;//棧的空間大小
}ST;

1.2.2初始化

//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}

調用調試：

1.2.3銷毀

//銷毀
void STDesTroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

1.2.4入棧

// ?棧
void STPush(ST* ps, STDataType x)
{assert(ps);//判斷空間是否足夠if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空間足夠ps->arr[ps->top++] = x;
}

調用測試：

STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
STPush(&st, 5);

1.2.5判空

//棧是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

1.2.6出棧

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

調用測試：

1.2.7取棧頂元素

top為指向當前棧頂元素的索引，所以需要-1。

//取棧頂元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}

調用測試：

while (!STEmpty(&st))
{//取棧頂STDataType top = STTop(&st);printf("%d ", top);//出棧STPop(&st);
}
printf("\n");

1.2.8獲取棧中有效元素個數

//獲取棧中有效元素個數
int STSize(ST* ps)
{assert(ps);return ps->top;
}

調用測試：

printf("size:%d\n",STSize(&st));

1.3解釋assert(ps)與assert(!STEmpty)

assert(ps)：保證傳入的為有效的棧結構體變量。限制參數不能為空。

assert(!STEmpty)：保證棧中的有效個數不能為空。

2.力扣算法題：有效的括號

20. 有效的括號 - 力扣（LeetCode）

理解題意：

思路：借助棧，遍歷字符串，如果遇到左括號，就將字符串入棧，如果遇到右括號，就取棧頂，將其與右括號相比較，相同則出棧。

編程中遇到的問題：有空字符串或者遇到一開始就是右括號的，需要判斷棧是否為空以及對于條件表達式的使用錯誤。

代碼如下：

// 需要借助棧
// 定義棧的結構
typedef char STDataType;
typedef struct Stack {STDataType* arr;int top;      // 指向當前棧頂元素的索引--正好為棧中有效的數據個數int capacity; // 棧的空間大小
} ST;
// 初始化
void STInit(ST* ps) {ps->arr = NULL;ps->capacity = ps->top = 0;
}// 銷毀
void STDesTroy(ST* ps) {if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}// ?棧
void STPush(ST* ps, STDataType x) {assert(ps);// 判斷空間是否足夠if (ps->top == ps->capacity) {// 增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp =(STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}// 空間足夠ps->arr[ps->top++] = x;
}// 棧是否為空
bool STEmpty(ST* ps) {assert(ps);return ps->top == 0;
}// 出棧
void STPop(ST* ps) {assert(!STEmpty(ps));ps->top--;
}// 取棧頂元素
STDataType STTop(ST* ps) {assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}// 獲取棧中有效元素個數
int STSize(ST* ps) {assert(ps);return ps->top;
}
// 以上為棧結構的定義與常見方法
bool isValid(char* s) {ST st;STInit(&st);char* i = s;while (*i != '\0') {// 左括號入棧if (*i == '(' || *i == '[' || *i == '{') {STPush(&st, *i);} else {// 右括號取棧頂，出棧或返回false// 若第一個為右括號，為空棧if (STEmpty(&st)) {STDesTroy(&st);return false;}char top = STTop(&st);if((top == '[' && *i != ']') || (top == '{' && *i != '}')|| (top == '(' && *i != ')')){STDesTroy(&st);return false;} //匹配-出棧STPop(&st);}i++;}// 棧是否為空//  if(STEmpty(&st))//  {//      STDesTroy(&st);//      return true;//  }// STDesTroy(&st);// return false;bool ret = STEmpty(&st) ? true : false;STDesTroy(&st);return ret;
}

最終通過測試。

本章完。