目錄

一、棧的概念及結構

二、棧的頭文件及基本框架

三、接口實現

1、對棧的初始化

?2、棧的銷毀

3、入棧操作

4、出棧操作

?5、判斷棧是否為空

6、返回棧頂元素

7、遍歷棧

四、有效的括號 - 力扣（LeetCode）

題目描述：

?思路：

代碼：

---

一、棧的概念及結構

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

如同子彈夾，我們進行添子彈和出子彈，很形象。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

?接下來，我們以數組棧的形式去模擬。

二、棧的頭文件及基本框架

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int STDataType;typedef struct Stack
{STDataType* a;//就是以a開頭的一段連續的空間int top;//定義棧頂位置int capacity;
}ST;void SLInit(ST* ps);
void SLDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);//獲取棧頂元素

三、接口實現

1、對棧的初始化

void SLInit(ST* ps)
{ST* ret = (ST*)malloc(4 * sizeof(ST));if (ret == NULL){perror(malloc);exit(-1);}ps->a = ret;ps->capacity = 4;ps->top = 0;
}

?2、棧的銷毀

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

3、入棧操作

void STPush(ST* ps, STDataType x)
{assert(ps != NULL);//檢查需不需要擴容if (ps->top == ps->capacity){ps->capacity += 4;ST* ret = (ST*)realloc( ps->a, sizeof(ST) * ps->capacity);if (ret == NULL){perror(realloc);exit(-1);}ps->a = ret;}ps->a[ps->top] = x;ps->top++;
}

4、出棧操作

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

?5、判斷棧是否為空

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;如果右邊等式成立返回true，反之返回false
}

6、返回棧頂元素

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

7、遍歷棧

不同于其他數據結構，遍歷棧不用print

//遍歷棧的特殊方式while (!STEmpty(&ps)){printf("%d ", STTop(&ps));STPop(&ps);}

四、有效的括號 - 力扣（LeetCode）

題目描述：

給定一個只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右括號都有一個對應的相同類型的左括號。

?思路：

如果是左括號就入棧，如果是右括號就與棧頂元素進行比較。這樣就正好匹配題目的要求，但博主目前沒有學過STL庫，所以只能將上面的手撕棧CV一下啦，下面的代碼為了避免冗余去除掉這一部分~

代碼：

bool isValid(char * s)
{char* ret = s;int num = 0;//利用奇數偶數判斷數量是否匹配while(*ret){num++;ret++;}if(num%2 != 0){return false;}ST ps;SLInit(&ps);while(*s){switch(*s){case '{':case '[':case '(':STPush(&ps,*s);break;case ')':case ']':case '}':if(STSize(&ps) == 0)return false;if(*s == ']' && STTop(&ps) != '['||*s == ')' && STTop(&ps) != '('||*s == '}' && STTop(&ps) != '{'){SLDestroy(&ps);return false;}STPop(&ps);break;}s++;}//防止((出現if(!STEmpty(&ps))return false;return true;
}