1.1 堆疊的概念及結構

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

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

出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂，

1.2 堆疊的實作

堆疊的實作一般可以使用陣列或者鏈表實作，相對而言陣列的結構實作堆疊更優一些，因為陣列在尾上插入資料的代價比較小，

使用陣列來實作堆疊，你可以認為最開始的時候堆疊底和堆疊頂在同一個位置處，但是堆疊頂更像是形容入堆疊的方向，表示著入堆疊資料的走向，

1.2.1順序表和鏈表實作堆疊不同及優缺點

那么為什么使用陣列會比使用鏈表更加的優呢？
對于陣列結構來表示堆疊，是不能夠進行頭插和中間插入的，因為會破壞堆疊的后進先出的特點，那么你可能就會想：使用順序表需要增容，或者會造成空間的浪費等…事實上對于一個順序表來說并不是你每次插入資料都需要進行增容的操作，而且對于計算機來說記憶體是相當大的，你就算浪費了幾百幾千個位元組的空間大小對于他來說也是微不足道的，除非你從事的是嵌入式的行業，對于記憶體非常看重，那么就另當別論了，最主要的就是順序表容易實作，如果是雙向鏈表，那一邊是堆疊頂那一邊是堆疊底其實都是可以的，但是如果是單鏈表，你的頭處應該設定為堆疊頂的方向，

如果你所定義的是單鏈表實作堆疊的結果是這樣子，你就會發現，你在堆疊頂插入資料，但是當你想要Pop的時候，他的前一個地址你是不知道的，

什么時候會使用到堆疊呢？
比如說后入先出的場景，對于一個迷宮來說，有時候我可能會走到死胡同，此時我希望它能夠退回到原來的位置，我就可以用這個來實作，

1.3 陣列實作堆疊的完整代碼

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int STDateType;

typedef struct Stack
{
	STDateType* _a;
	int _top; //堆疊頂下標
	int _capacity;
}Stack;

//初始化和銷毀
void StackInit(Stack* pst);
void StackDestory(Stack* pst);

//入堆疊
void StackPush(Stack* pst, STDateType x);
//出堆疊
void StackPop(Stack* pst);
//獲取資料個數
int StackSize(Stack* pst);

//回傳1是空，回傳0是非空
int StackEmpty(Stack* pst);
//獲取堆疊頂的資料
STDateType StackTop(Stack* pst);

#include"Stack.h"
//初始化
void StackInit(Stack* pst)
{
	assert(pst);
	//這種方式是有不好的地方的，因為但當你需要增容的時候，你就會發現，他的capacity初始化是0，那么你乘2依舊是0，所以建議一開始就給一個固定值
	//pst->_a = NULL;
	//pst->_top = 0;
	//pst->_capacity = 0;
	pst->_a = (STDateType*)malloc(sizeof(STDateType)*4);
	pst->_top = 0;
	pst->_capacity = 4;
}

//銷毀
void StackDestory(Stack* pst)
{
	assert(pst);
	free(pst->_a);
	pst->_a = NULL;
	pst->_top = pst->_capacity = 0;
}

//入堆疊
//只要入堆疊就要考慮到空間是否滿的情況，對其進行判斷
void StackPush(Stack* pst, STDateType x)
{
	assert(pst);
	//空間不夠則增容
	if (pst->_top == pst->_capacity)
	{
		pst->_capacity *= 2;
		STDateType* tmp = (STDateType*)realloc(pst->_a, sizeof(STDateType)*pst->_capacity);
		if (tmp == NULL)
		{
			printf("記憶體不足\n");
			exit(-1);
		}
		else
		{
			pst->_a = tmp;
		}
	}
	pst->_a[pst->_top] = x;//你所定義的堆疊頂總是在你放入資料的下一個位置
	pst->_top++;
}

//出堆疊
void StackPop(Stack* pst)
{
	assert(pst);
	assert(pst->_top > 0);//得確保堆疊里面是有資料的，你才能去刪
	--pst->_top;
}

//獲取資料個數
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->_top;
}


//回傳1是空，回傳0是非空
int StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->_top == 0 ? 1 : 0;
}


//獲取堆疊頂的資料
STDateType StackTop(Stack* pst)
{
	assert(pst);
	assert(pst->_top > 0);
	return pst->_a[pst->_top - 1];//你所定義的堆疊頂總是在你放入資料的下一個位置
}

#include"Stack.h"
void TsetStack()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4)；
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
	StackDestory(&st);
	
}
int main()
{
	TsetStack();
	return 0;
}

堆疊并沒有規定要求一次性入堆疊或者出堆疊，你可以選擇邊入邊出，所以一個入堆疊的順序可能對應著多個出堆疊的順序，

1.4 堆疊的相關選擇題

1.一個堆疊的初始狀態為空，現將元素1、2、3、4、5、A、B、C、D、E依次入堆疊，然后再依次出堆疊，則元素出堆疊的順序是（ B），
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA

這些答案都是如果題目沒有出現“依次”這個詞的情況下的結果，但是當出現“依次”的時候結果只可能是B，一次全部入堆疊，然后在全部出堆疊
A：對于A選項就是入堆疊一個出堆疊一個，是可能出現的結果
B：一次性全部入堆疊，然后在全部出堆疊，是有可能出現的結果
C：不可能
D:先入12345然后出堆疊，然后載入ABCDE然后出堆疊，是有可能出現的結果

2.若進堆疊序列為 1,2,3,4 ，進堆疊程序中可以出堆疊，則下列不可能的一個出堆疊序列是（C）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
答案：
A:先入1，出1，然后入2,3,4在出堆疊，是可能出現的結果，
B：先入1,2然后出堆疊2，然后在入3，出3，入4出4，最后出1，是可能的結果，
C：不可能，
D入1,2,3出3，然后入4，出4，再出2,1是可能出現的結果，

1.5 LeetCode第20題—有效的括號

對于C++來說自己就有堆疊，但是對于c語言來說是沒有堆疊的，還需要自己來實作一個堆疊才行

typedef char STDateType;

typedef struct Stack
{
	STDateType* _a;
	int _top; //堆疊頂下標
	int _capacity;
}Stack;

//初始化和銷毀
void StackInit(Stack* pst);
void StackDestory(Stack* pst);

//入堆疊
void StackPush(Stack* pst, STDateType x);
//出堆疊
void StackPop(Stack* pst);
//獲取資料個數
int StackSize(Stack* pst);

//回傳1是空，回傳0是非空
int StackEmpty(Stack* pst);
//獲取堆疊頂的資料
STDateType StackTop(Stack* pst);

//初始化
void StackInit(Stack* pst)
{
	assert(pst);
	pst->_a = (STDateType*)malloc(sizeof(STDateType)*4);
	pst->_top = 0;
	pst->_capacity = 4;
}

//銷毀
void StackDestory(Stack* pst)
{
	assert(pst);
	free(pst->_a);
	pst->_a = NULL;
	pst->_top = pst->_capacity = 0;
}

//入堆疊
void StackPush(Stack* pst, STDateType x)
{
	assert(pst);
	//空間不夠則增容
	if (pst->_top == pst->_capacity)
	{
		pst->_capacity *= 2;
		STDateType* tmp = (STDateType*)realloc(pst->_a, sizeof(STDateType)*pst->_capacity);
		if (tmp == NULL)
		{
			printf("記憶體不足\n");
			exit(-1);
		}
		else
		{
			pst->_a = tmp;
		}
	}
	pst->_a[pst->_top] = x;//你所定義的堆疊頂總是在你放入資料的下一個位置
	pst->_top++;
}

//出堆疊
void StackPop(Stack* pst)
{
	assert(pst);
	assert(pst->_top > 0);
	--pst->_top;
}

//獲取資料個數
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->_top;
}


//回傳1是空，回傳0是非空
int StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->_top == 0 ? 1 : 0;
}


//獲取堆疊頂的資料
STDateType StackTop(Stack* pst)
{
	assert(pst);
	assert(pst->_top > 0);
	return pst->_a[pst->_top - 1];//你所定義的堆疊頂總是在你放入資料的下一個位置
}




bool isValid(char * s){
    Stack  st;
    StackInit(&st);
    while(*s != '\0')
    {
        //如果是前括號那就入堆疊，如果是后括號那就拿堆疊頂的值和此時相比較（這樣他們兩個才是相鄰的）
        if(*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            //表示此時前括號堆疊里沒有了，但是]還有  []]]
            if(StackEmpty(&st))
               return false; 

            
            //取堆疊頂
            char top = StackTop(&st);
            if(*s == ']' && top != '[')
                return false;
            if(*s == ')' && top != '(')
                return false;
            if(*s == '}' && top != '{')
                return false;
            StackPop(&st);
            s++;
        }
    }  
    //這里的while回圈結束有兩種情況：一種就是你的s遍歷完了， 這種情況[[[]   [在堆疊里面還有，還有一種就是都匹配上了，里面不再有任何東西了
    //這里判斷的是[[[] 在堆疊里面還有，但是你的s已經遇見了'\0'遍歷完了
    int ret = StackEmpty(&st);
    // ret如果為1表示空，此時所有的括號都匹配上了，1就代表true，但是ret加上下面這個ret==0這個判斷條件更加容易理解，如果他是0表示[在堆疊里面還有，但是此時s已經遍歷完了，所以他不為空，那么也是一種錯誤的情況
    if(ret == 0)
      return false;
    //在你把堆疊使用完了以后一定要對其進行釋放，否則就會造成記憶體的泄漏
    StackDestory(&st);
    return ret;
}