C語言基於考研的棧和隊列
棧
棧的基本操作
InitStack(&S):初始化
StackEmpty(S):判空，空則true，非空則false
Push(&S,x):入棧
Pop(&S,&x):出棧，並用x返回元素內容
GetTop(S,&x):讀棧頂元素
DestroyStack(&S):銷毀並釋放空間
棧是一種受限的線性表，隻允許在一端操作
棧若隻能在棧頂操作，則隻可能上溢
采用非遞歸方式重寫遞歸時，不一定要用棧，比如菲波那切數列隻要用循環即可
共享棧：
從兩頭往中間填充，有效的利用空間。
出棧序列的個數：1𝑛+1𝐶2𝑛𝑛
隊列
隊列也是受限的線性表，隻允許在一端插入，另一端刪除
FIFO（First in first out）
常見操作：
InitQueue（&Q）：初始化，構造一個空隊列Q
QueueEmpty（Q）：判空
EnQueue（&Q，x）：入隊
DeQueue（&Q，&x）：出隊並返回出隊的元素至x
GetHead（Q，&x）：獲取對頭元素
隊列的大題真題考的是，畫初始狀態，判空判滿的條件，入隊基本過程
So先看類似的概念，想法，思路，後期再看具體的代碼實現，畢竟沒考過具體代碼
順序存儲定義：
#define Maxsize 50
typedef struct{
Elemtype data[Maxsize];
int front,rear;
}SqQueue;
循環隊列：
初始化：Q.front=Q.rear=0
隊首指針+1\入隊：Q.front=(Q.front+1)%Maxsize
隊尾指針+1\出隊：Q.rear=(Q.rear+1)%Maxsize
隊列長度：(Q.rear+Maxsize-Q.front)%Maxsize
因為隊滿和隊空都是Q.front=Q.rear，所以無法判斷到底是隊空還是隊滿
有三個解決辦法
1）常用方法：犧牲一個單元來區分隊空和隊滿，入隊是少用一個單元
隊滿條件：（Q.rear+1）%MaxsizeQ.front
隊空條件：Q.frontQ.rear
隊列中元素個數：（Q.rear-Q.front+Maxsize）%Maxsize
2）類型中增設一個數據成員表示元素個數，這樣隊空：Q.size0,隊滿：Q.sizeMaxsize
3）增設tag，入隊時令tag=1，出隊時令tag=0，這樣能表示當Q.frontQ.rear時，如果tag1，則隊滿，tag==0則隊空
鏈式存儲：
typedef struct LinkNode{ //定義節點
Elemtype data;
struct LinkNode *next;
}LinkNode;
typedef struct{ //定義隊列的首尾節點
Node *front,*rear;
}LinkQueue;
棧和隊列的應用
括號匹配
表達式求值
後綴表達式：數據進棧，操作符則彈出2個數據進行操作再將結果進棧
同一個問題，遞歸算法和非遞歸算法一般來說，非遞歸效率比較低，因為有很多重復計算
圖的廣度優先算法要借助輔助隊列
將中綴表達式轉換為前綴表達式
轉換步驟如下:
初始化兩個棧:運算符棧s1，儲存中間結果的棧s2
從右至左掃描中綴表達式
遇到操作數時，將其壓入s2
遇到運算符時，比較其與s1棧頂運算符的優先級
如果s1為空，或棧頂運算符為右括號“)”，則直接將此運算符入棧
否則，若優先級比棧頂運算符的較高或相等，也將運算符壓入s1
否則，將s1棧頂的運算符彈出並壓入到s2中，再次轉到(4-1)與s1中新的棧頂運算符相比較
遇到括號時
如果是右括號“)”，則直接壓入s1
如果是左括號“(”，則依次彈出S1棧頂的運算符，並壓入S2，直到遇到右括號為止，此時將這一對括號丟棄
重復步驟2至5，直到表達式的最左邊
將s1中剩餘的運算符依次彈出並壓入s2
依次彈出s2中的元素並輸出，結果即為中綴表達式對應的前綴表達式
將中綴表達式轉換為後綴表達式
與轉換為前綴表達式相似，步驟如下：
初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；
從左至右掃描中綴表達式；
遇到操作數時，將其壓s2；
遇到運算符時，比較其與s1棧頂運算符的優先級：
如果s1為空，或棧頂運算符為左括號“(”，則直接將此運算符入棧；
否則，若優先級比棧頂運算符的高，也將運算符壓入s1（註意轉換為前綴表達式時是優先級較高或相同，而這裡則不包括相同的情況）；
否則，將s1棧頂的運算符彈出並壓入到s2中，再次轉到(4-1)與s1中新的棧頂運算符相比較；
遇到括號時：
如果是左括號“(”，則直接壓入s1；
如果是右括號“)”，則依次彈出s1棧頂的運算符，並壓入s2，直到遇到左括號為止，此時將這一對括號丟棄；
重復步驟2至5，直到表達式的最右邊；
將s1中剩餘的運算符依次彈出並壓入s2；
依次彈出s2中的元素並輸出，結果的逆序即為中綴表達式對應的後綴表達式（轉換為前綴表達式時不用逆序）
特殊矩陣的壓縮存儲
對稱矩陣
三角矩陣
三對角矩陣：又稱帶狀矩陣
稀疏矩陣：三元組既可以用數組存儲，也可以用十字鏈表法
總結
本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！