從兩頭往中間填充，有效的利用空間。

出棧序列的個(gè)數(shù)：1𝑛+1𝐶2𝑛𝑛

隊(duì)列

隊(duì)列也是受限的線性表，只允許在一端插入，另一端刪除

FIFO（First in first out）

常見操作：

InitQueue（&Q）：初始化，構(gòu)造一個(gè)空隊(duì)列Q

QueueEmpty（Q）：判空

EnQueue（&Q，x）：入隊(duì)

DeQueue（&Q，&x）：出隊(duì)并返回出隊(duì)的元素至x

GetHead（Q，&x）：獲取對(duì)頭元素

隊(duì)列的大題真題考的是，畫初始狀態(tài)，判空判滿的條件，入隊(duì)基本過程

So先看類似的概念，想法，思路，后期再看具體的代碼實(shí)現(xiàn)，畢竟沒考過具體代碼

順序存儲(chǔ)定義：

#define Maxsize 50

typedef struct{
Elemtype data[Maxsize];

int front,rear;

}SqQueue;

循環(huán)隊(duì)列：

初始化：Q.front=Q.rear=0

隊(duì)首指針+1\入隊(duì)：Q.front=(Q.front+1)%Maxsize

隊(duì)尾指針+1\出隊(duì)：Q.rear=(Q.rear+1)%Maxsize

隊(duì)列長(zhǎng)度：(Q.rear+Maxsize-Q.front)%Maxsize

因?yàn)殛?duì)滿和隊(duì)空都是Q.front=Q.rear，所以無(wú)法判斷到底是隊(duì)空還是隊(duì)滿

有三個(gè)解決辦法

1）常用方法：犧牲一個(gè)單元來(lái)區(qū)分隊(duì)空和隊(duì)滿，入隊(duì)是少用一個(gè)單元

隊(duì)滿條件：（Q.rear+1）%MaxsizeQ.front

隊(duì)空條件：Q.frontQ.rear

隊(duì)列中元素個(gè)數(shù)：（Q.rear-Q.front+Maxsize）%Maxsize

2）類型中增設(shè)一個(gè)數(shù)據(jù)成員表示元素個(gè)數(shù)，這樣隊(duì)空：Q.size0,隊(duì)滿：Q.sizeMaxsize

3）增設(shè)tag，入隊(duì)時(shí)令tag=1，出隊(duì)時(shí)令tag=0，這樣能表示當(dāng)Q.frontQ.rear時(shí)，如果tag1，則隊(duì)滿，tag==0則隊(duì)空

鏈?zhǔn)酱鎯?chǔ)：

typedef struct LinkNode{ //定義節(jié)點(diǎn)

Elemtype data;

struct LinkNode *next;

}LinkNode;

typedef struct{ //定義隊(duì)列的首尾節(jié)點(diǎn)

Node *front,*rear;

}LinkQueue;

棧和隊(duì)列的應(yīng)用

括號(hào)匹配

表達(dá)式求值

后綴表達(dá)式：數(shù)據(jù)進(jìn)棧，操作符則彈出2個(gè)數(shù)據(jù)進(jìn)行操作再將結(jié)果進(jìn)棧

同一個(gè)問題，遞歸算法和非遞歸算法一般來(lái)說(shuō)，非遞歸效率比較低，因?yàn)橛泻芏嘀貜?fù)計(jì)算

圖的廣度優(yōu)先算法要借助輔助隊(duì)列

將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式

轉(zhuǎn)換步驟如下:

初始化兩個(gè)棧:運(yùn)算符棧s1，儲(chǔ)存中間結(jié)果的棧s2

從右至左掃描中綴表達(dá)式

遇到操作數(shù)時(shí)，將其壓入s2

遇到運(yùn)算符時(shí)，比較其與s1棧頂運(yùn)算符的優(yōu)先級(jí)

如果s1為空，或棧頂運(yùn)算符為右括號(hào)“)”，則直接將此運(yùn)算符入棧

否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的較高或相等，也將運(yùn)算符壓入s1

否則，將s1棧頂?shù)倪\(yùn)算符彈出并壓入到s2中，再次轉(zhuǎn)到(4-1)與s1中新的棧頂運(yùn)算符相比較

遇到括號(hào)時(shí)

如果是右括號(hào)“)”，則直接壓入s1

如果是左括號(hào)“(”，則依次彈出S1棧頂?shù)倪\(yùn)算符，并壓入S2，直到遇到右括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄

重復(fù)步驟2至5，直到表達(dá)式的最左邊

將s1中剩余的運(yùn)算符依次彈出并壓入s2

依次彈出s2中的元素并輸出，結(jié)果即為中綴表達(dá)式對(duì)應(yīng)的前綴表達(dá)式

將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

與轉(zhuǎn)換為前綴表達(dá)式相似，步驟如下：

初始化兩個(gè)棧：運(yùn)算符棧s1和儲(chǔ)存中間結(jié)果的棧s2；

從左至右掃描中綴表達(dá)式；

遇到操作數(shù)時(shí)，將其壓s2；

遇到運(yùn)算符時(shí)，比較其與s1棧頂運(yùn)算符的優(yōu)先級(jí)：

如果s1為空，或棧頂運(yùn)算符為左括號(hào)“(”，則直接將此運(yùn)算符入棧；

否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的高，也將運(yùn)算符壓入s1（注意轉(zhuǎn)換為前綴表達(dá)式時(shí)是優(yōu)先級(jí)較高或相同，而這里則不包括相同的情況）；

否則，將s1棧頂?shù)倪\(yùn)算符彈出并壓入到s2中，再次轉(zhuǎn)到(4-1)與s1中新的棧頂運(yùn)算符相比較；

遇到括號(hào)時(shí)：

如果是左括號(hào)“(”，則直接壓入s1；

如果是右括號(hào)“)”，則依次彈出s1棧頂?shù)倪\(yùn)算符，并壓入s2，直到遇到左括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄；

重復(fù)步驟2至5，直到表達(dá)式的最右邊；

將s1中剩余的運(yùn)算符依次彈出并壓入s2；

依次彈出s2中的元素并輸出，結(jié)果的逆序即為中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式（轉(zhuǎn)換為前綴表達(dá)式時(shí)不用逆序）

特殊矩陣的壓縮存儲(chǔ)

對(duì)稱矩陣

三角矩陣

三對(duì)角矩陣：又稱帶狀矩陣

稀疏矩陣：三元組既可以用數(shù)組存儲(chǔ)，也可以用十字鏈表法

總結(jié)

本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！