前言

本文均基于C語言實作，
以下是本篇文章正文內容，下面案例可供參考

一、堆疊的概念與結構

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為 堆疊頂，另一端稱為 堆疊底，堆疊中的資料元素遵守 后進先出 LIFO（Last In First Out）的原則，

入堆疊 ：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊 ：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂，

二、C語言-堆疊的基本操作與實作

堆疊的基本操作主要有以下幾點：初始化、入堆疊、出堆疊、獲取堆疊頂元素、獲取堆疊中有效元素個數、判空、銷毀堆疊

1.堆疊的創建

堆疊和線性表類似，也有兩種存盤表示方法:定長的 靜態堆疊 和支持動態增長的 鏈堆疊，鏈堆疊的操作是線性表操作的特例，操作比較容易實作，靜態堆疊，即堆疊的順序存盤結構是利用一組地址連續的存盤單元依次存放自堆疊底到堆疊頂的資料元素，同時附設指標 top 指示堆疊頂元素在順序堆疊中的位置， top = 0 表示空堆疊,因此， 非空堆疊中，top 表示堆疊頂元素的下一個位置，由于其在實際中并不實用，故下面所實作均為 動態增長的堆疊

另附靜態堆疊：

#define N 10
typedef struct Stack
{
 STDataType arr[N];
 int top; // 堆疊頂
}Stack;

支持動態增長的堆疊 ：

// 支持動態增長的堆疊
typedef int STDataType;   //方便修改不同堆疊資料型別
typedef struct Stack
{
	STDataType* a;
	int top;		// 堆疊頂
	int capacity;  // 容量 
}Stack;

2.堆疊的初始化

此處 top = 0 表示空堆疊，方便后期判斷堆疊是否為滿， 非空堆疊中，top 表示堆疊頂元素的下一個位置，

代碼如下：

// 初始化堆疊 
void StackInint(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

3.入堆疊

判斷堆疊是否為滿，若滿，則使用 realloc() 函式另外開辟空間，若有小伙伴忘記該函式，記得下去復習！

代碼如下：

void StackPush(Stack* ps, STDataType data)
{
	if (ps->top == ps->capacity)  //判斷是否需要擴容
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	ps->top++；
}

4.出堆疊

此處須判斷堆疊是否為 空 ，倘若為空，出堆疊后 top = -1 ,入堆疊時會導致非法訪問記憶體，

代碼如下：

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StachEmpty(ps));  //判斷不為空
	ps->top--;
}

5.獲取堆疊頂元素

此處判斷堆疊是否為 空 ，倘若為空，即空堆疊，無資料，

代碼如下：

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StachEmpty(ps));
	return ps->a[ps->top - 1];
}

6.獲取堆疊中有效元素個數

代碼如下：

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

7.檢測堆疊是否為空

若慷訓傳非0結果，否則回傳0

代碼如下：

bool StachEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)
		return true;
	return false;
}

8.銷毀堆疊

釋放 realloc() 所開辟的空間，將 a 置為 NULL ，保持良好習慣

代碼如下：

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

三、堆疊的經典使用

1.問題敘述

附上鏈接 : 括號匹配問題
題目描述如下:

2.解題方法

解題思路：本題可以使用 堆疊 這一資料結構來解決，
我們遍歷給定的字串 s，當我們遇到一個左括號時，我們會期望在后續的遍歷中，有一個相同型別的右括號將其閉合，因此結合示例可以看出，每每遇到 左括號，進行 入堆疊操作，遇到 右括號，進行 出堆疊操作，與之匹配,若不匹配，回傳 false.當字串遍歷完，且堆疊為空，即回傳 true
復雜度分析：
時間復雜度：O(N) 即遍歷了一遍字串，
空間復雜度：O(N) 假如輸入是 [[[[[[[[[ ，堆疊的大小將是輸入字串的長度，

3.代碼實作

由于上面已經創建好 堆疊 ，代碼直接拿來使用（是的，ctrl + c 和 ctrl + v 是一個“合格程式員”的“基本修養”）

bool isValid(char * s){
//堆疊的實作
typedef struct Stack
{
	char* a;
	int top;
	int capacity;
}Stack;
void StackInint(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
bool StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)
		return true;
	return false;
}
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->a)
		free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackPush(Stack* ps, char data)
{
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		char* tmp = (char*)realloc(ps->a, sizeof(char) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
			ps->a = tmp;
			ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}

char StackTop(Stack* ps)
{
	assert(ps);
    if(ps->top)
	return ps->a[ps->top - 1];
    return 'a';
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//free(ps->a + ps->top - 1);
	ps->top--;
}

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

Stack ST;
StackInint(&ST);
//進行括號匹配
while(*s)
{
	//為左括號，入堆疊
    if((*s == '(')||(*s == '[')||(*s == '{'))
    StackPush(&ST, *s);
    else
    {	
    	//右括號，與堆疊頂元素匹配，匹配成功則出堆疊，反之回傳 false
        if((*s==')'&&StackTop(&ST)!='(')
        ||(*s==']'&&StackTop(&ST)!='[')||
        (*s=='}'&&StackTop(&ST)!='{'))
        return false;
        StackPop(&ST);
    }
    s++;
}
if(StackEmpty(&ST)!=0)
	return true;
return false;
}

附上運行圖 ：

以上就是本次用c語言所帶來的內容，如為你帶來幫助，點贊支持一波吧