C語言的棧和隊列的基本操作

這篇文章主要介紹“C語言的棧和隊列的基本操作”，在日常操作中，相信很多人在C語言的棧和隊列的基本操作問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”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中的元素并輸出，結果的逆序即為中綴表達式對應的后綴表達式（轉換為前綴表達式時不用逆序）

特殊矩陣的壓縮存儲

對稱矩陣

三角矩陣

三對角矩陣：又稱帶狀矩陣

稀疏矩陣：三元組既可以用數組存儲，也可以用十字鏈表法

到此，關于“C語言的棧和隊列的基本操作”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！