🌕寫在前面

🍊博客主頁：kikoking的江湖背景
🎉歡迎關注🔎點贊👍收藏??留言📝
🌟本文由 kikokingzz 原創，CSDN首發！
📆首發時間：🌹2021年12月06日🌹
🆕最新更新時間：🎄2021年12月06日🎄
??堅持和努力一定能換來詩與遠方！
🙏作者水平很有限，如果發現錯誤，請留言轟炸哦！萬分感謝感謝感謝！

前文簡介：
第一話·徹底搞清資料結構中的·邏輯結構&存盤結構
第二話·徹底搞懂資料結構之·演算法復雜度
第三話·408必看順序表之·人生不是“順序表”
第四話·資料結構必看之·單鏈表就這？

🔥1.堆疊的邏輯結構

🍊1.1 線性表

🍊1.2 堆疊的數學性質

?例題1·卡特蘭數

🔥2.堆疊的物理結構

🍊2.1 堆疊的順序存盤結構

🍓順序堆疊的優點

🍊2.2共享堆疊

🍓共享堆疊的優點

🍊2.3 堆疊的鏈式存盤結構

🍓鏈堆疊的優點

🔥3.用單鏈表實作鏈堆疊的一系列操作

🍊3.1鏈堆疊的定義

🍊3.2初始化

🍓選擇帶哨兵位頭結點的單鏈表

🍊3.3判空操作

🍊3.4銷毀

🍊3.5進堆疊

🍊3.6出堆疊

🍊3.7讀堆疊頂元素

🔥4.用動態陣列實作順序堆疊的一系列操作

🍊4.1順序堆疊的定義

🍊4.2初始化

🍊4.3判空操作

🍊4.4銷毀

🍊4.5進堆疊

🍊4.6出堆疊

🍊4.7讀堆疊頂元素

🔥堆疊的應用1·括號匹配

?思路

🖥演算法演示

🍓代碼實作

🔥堆疊的應用2·中綴運算式求值

🍊中綴運算式轉后綴運算式方法

🍊后綴運算式求值的計算機實作

🍊中綴運算式轉后綴運算式的機器計算

🌟中綴運算式求值

?普通法——將上述兩種方法按次序進行

?深度結合法

🍊中綴運算式轉前綴運算式方法?

🍓前綴運算式的機器計算

🐉：老樣子，學習一種資料結構要按照怎么樣的順序學習呀？

L：要從它的邏輯結構-->物理結構（存盤結構）-->執行的操作來進行分析

???我是分割線???

🔥1.堆疊的邏輯結構

🍊1.1 線性表

堆疊(Stack)是只允許一端進行插入或洗掉操作的線性表

🍊1.2 堆疊的數學性質

常常以選擇題形式考察，出堆疊順序是否合法

?例題1·卡特蘭數

列舉檢驗：

???我是分割線???

🔥2.堆疊的物理結構

🍊2.1 堆疊的順序存盤結構

采用順序存盤的堆疊稱為順序堆疊，它利用一組地址連續的存盤單元存放自堆疊底到堆疊頂的資料元素，同時附設一個指標（top）指示當前堆疊頂元素的位置，

🍓順序堆疊的優點

1.偶爾增容，偶爾增一下，而鏈堆疊每次都要申請結點

2.插入資料相比鏈堆疊更高效

🍊2.2共享堆疊

🍓共享堆疊的優點

1.節省存盤空間

2.降低發生上溢的可能

🍊2.3 堆疊的鏈式存盤結構

·采用鏈式存盤的堆疊稱為鏈堆疊

🍓鏈堆疊的優點

1.便于多個堆疊共享共享存盤空間和提高效率

2.不存在堆疊滿上溢的情況

3.和順序堆疊相比，它可以動態地分配存盤空間，方便擴容

???我是分割線???

🔥3.用單鏈表實作鏈堆疊的一系列操作

🍊3.1鏈堆疊的定義

typedef int ElemType;

typedef struct LStackNode //定義一個結構體型別的結點
{
	ElemType x; //資料域
	struct LStackNode* next; //指標域
}LS; //用LS代替LStackNode結點

🍊3.2初始化

🍓選擇帶哨兵位頭結點的單鏈表

·原因：可見，用單鏈表實作入堆疊、出堆疊基本上都是對應于頭插和頭刪，為了方便起見，采用帶哨兵位的頭結點的單鏈表！

void LStackInit()
{
	LS* phead = (LS*)malloc(sizeof(LS));//申請一個哨兵位的頭結點
	phead->next = NULL; //初始化時，哨兵位頭結點指向NULL
	phead->data = 0;//哨兵位頭結點的資料域為0
}

🍊3.3判空操作

int LStackEmpty(LS* phead)//判空
{
	assert(phead);
	return phead->next == NULL ? 1 : 0; 
	//如果phead指向空，則說明鏈堆疊為空
}

🍊3.4銷毀

void LStackDestroy(LS* phead)//銷毀
{
	assert(phead);
	LS* cur = phead->next;
	while (cur)
	{
		LS* next = cur->next;
		free(cur);
		cur = next;
	}
	phead->next = NULL;
}

🍊3.5進堆疊

void LStackPush(LS* phead ,ElemType x)
{
    assert(phead);
	LS* newnode= (LS*)malloc(sizeof(LS));//動態申請一個新結點
	newnode->data = x;//新結點的資料域放x
	newnode->next = phead->next;
	phead->next = newnode;
}

🍊3.6出堆疊

void LStackPop(LS* phead)
{
    assert(phead);
	LS* cur = phead->next;
	if (cur)//如果哨兵位頭結點后面有結點
	{
		LS* next = cur->next;
		free(cur);
		phead->next = next;
	}
	return;
}

🍊3.7讀堆疊頂元素

ElemType LStack(LS* phead)
{
	assert(phead);
	assert(!LStackEmpty(phead));//堆疊非空才可以向下進行
	return (phead->next)->data;
}

???我是分割線???

🔥4.用動態陣列實作順序堆疊的一系列操作

🍊4.1順序堆疊的定義

typedef int STDataType;
typedef struct Stack //這是一個動態陣列Stack
{
	STDataType* a;//指標a指向陣列的首元素地址
	int top;//堆疊頂
	int capacity;//堆疊的容量
}ST;//用ST來簡便代替struct Stack

🍊4.2初始化

void StackInit(ST* pst)
{
	assert(pst);//斷言結構體不為空
	pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    //動態申請存放4個元素的空間
	//好處是之后擴容可以直接擴容
	pst->top = 0;//指向堆疊頂元素的top指向0
	pst->capacity = 4;//堆疊的容量為4
}

🍊4.3判空操作

🍊4.4銷毀

void StackDestroy(ST* pst)//銷毀堆疊
{
	assert(pst);//結構體不為空才往下進行
	free(pst->a);//銷毀堆疊
	pst->a = NULL;//將原本指向堆疊底的指標置空
	pst->capacity = pst->top = 0;//堆疊的容量和top的值都置0
}

🍊4.5進堆疊

void StackPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)//判斷是否需要增容
	{
		STDataType* tmp = (STDataType*)realloc(pst->a,sizeof(STDataType) * pst->capacity * 2);//用tmp指向新申請的一片空間
		if (tmp == NULL)
		{
			printf("realloc fail\n");//增容失敗
			exit(-1);//結束整個程式
		}
		pst->a = tmp;//堆疊底指標a指向新空間
		pst->capacity *= 2;//堆疊的容量擴增兩倍
	}
	pst->a[pst->top] = x;//在top指向的位置插入元素
	pst->top++;//top指向下一個可以插入的位置
}

🍊4.6出堆疊

void StackPop(ST* pst)//出堆疊操作
{
	assert(pst);
	assert(!StackEmpty(pst));//如果堆疊為空就不進行下去了
	pst->top--;//將指向堆疊頂的top減1
}

🍊4.7讀堆疊頂元素

STDataType StackTop(ST* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//如果為空就不進行下去了
	return pst->a[pst->top - 1];//回傳一個堆疊頂元素
    //因為top一直指向下一個元素插入的位置，所以當前堆疊頂元素的位置應當是top-1
}

???我是分割線???

🔥堆疊的應用1·括號匹配

20. 有效的括號https://leetcode-cn.com/problems/valid-parentheses/

?思路

1.每出現一個右括號，就消耗一個左括號

2.遇到左括號就入堆疊

3.遇到右括號，就“消耗”一個左括號

🖥演算法演示

?正常模式：

?錯誤模式：

由于C語言的庫不夠完整，因此下面所使用到的堆疊，呼叫了上面預先建立的順序堆疊的程式

🍓代碼實作

bool isValid(char * s){
    ST st;
    StackInit(&st);//記得要初始化它
    while(*s)
    {
        //左括號入堆疊
        //右括號找最近的左括號匹配
        if(*s=='['||*s=='('||*s=='{')
        {
            StackPush(&st,*s);
            ++s;//繼續判斷下一個題目給的括號
        }
        else
        {
            if(StackEmpty(&st))//堆疊為空，說明沒有前括號
            {
                StackDestroy(&st);//記得要先銷毀再return
                return false;
            }
            char top=StackTop(&st);//讀取堆疊頂元素
            //如果不匹配就return false
            if((top=='['&&*s!=']')
            ||(top=='('&&*s!=')')
            ||(top=='{'&&*s!='}'))
            {
                StackDestroy(&st);//記得要先銷毀
                return false; 
            }
            else
            {
                StackPop(&st);//將堆疊頂元素出堆疊
                ++s;//繼續判斷下一個題目給的括號
            }
        }
    }

    bool ret = StackEmpty(&st);//判斷此時堆疊是否空
    //如果堆疊不空，說明有多余的左括號沒有得到匹配
    StackDestroy(&st);//記得要銷毀

    return ret;//最后堆疊慷訓傳true，不慷訓傳false
}

???我是分割線???

🔥堆疊的應用2·中綴運算式求值

前情須知：

上述中括號就是界限符，界限符同時也限制的運算的先后次序，計算機如何識別界限符是很難的，這時候，一個波蘭數學家提出：可以不同界限符也能無歧義地表達

🍊中綴運算式轉后綴運算式方法

🍊后綴運算式求值的計算機實作

🍊中綴運算式轉后綴運算式的機器計算

🌟中綴運算式求值

?普通法——將上述兩種方法按次序進行

Step1.將中綴運算式轉換為后綴運算式

Step2.使用后綴運算式計算

?深度結合法

·使用兩個堆疊來進行

🍊中綴運算式轉前綴運算式方法

🍓前綴運算式的機器計算