前言
本章主要詳解了棧和隊列以及特殊矩陣的壓縮知識，其中包括棧的順序存儲和鍊式存儲，隊列的順序存儲以及鍊式存儲，循環隊列的順序實作以及優化改進-雙端隊列，最後介紹了三種特殊矩陣的存儲結構壓縮算法。
文章目錄
- 前言
-
-
- 總覽：
- ①棧的邏輯結構
-
- 棧的概念：
- 棧的基本操作：
- ②棧的順序存儲結構
-
- 順序棧的結構：
- 順序棧的基本操作：
-
- 棧的初始化
- 判斷棧空
- 進棧
- 出棧
- 讀出棧頂元素
- 棧的非連續輸入和輸出問題：
-
- 合法出棧序列的個數：
- 共享棧
-
- 共享棧的概念
- ③棧的鍊式存儲結構
- ④隊列的邏輯結構
-
- 隊列的概念：
- 隊列的基本操作：
- ⑤隊列的順序存儲
-
-
- 順序隊列的概念：
- 鍊隊的實作：
-
- 鍊隊的結構體：
- 鍊隊的初始化操作：
- 鍊隊的入隊操作：
-
- ⑥循環隊列的存儲結構
-
- 循環隊列的概念：
- 循環隊列的基本操作：
-
- 循環隊列的初始化：
- 循環隊列的入隊：
- 循環隊列的出隊：
- 循環隊列的隊頭查找：
- 解決循環隊列的隊滿和隊空條件相同問題：
-
- 方法一：犧牲一個存儲單元
- 方法二：增加一個變量代表元素的個數
- 方法三：增加tag辨別
- ⑦雙端隊列的存儲結構
-
- 雙端隊列的概念：
- ⑧棧和隊列的應用
-
- 括号比對：
-
- 括号比對的算法實作：
- 表達式求值：
- ⑨特殊矩陣的壓縮存儲
-
- 特殊矩陣和壓縮存儲的概念：
-
- 對稱矩陣的壓縮計算：
- 三角矩陣的壓縮計算：
- 三對角矩陣的壓縮計算：
-
總覽：
①棧的邏輯結構
棧的概念：
棧（stack）隻允許在一端進行插入或者删除的線性表。
棧的基本操作：
Initstack(&S)：初始化一個空棧S。
StackEmpty(S)：判斷一個棧是否為空，若棧為空則傳回true，否則傳回false。
Push(&s,x)：進棧，若棧S未滿，則将x加入使之成為新棧頂。
Pop(&s，&x)：出棧，若棧非空，則彈出棧頂元素，并用×傳回。
GetTop(s，&x)：讀棧頂元素，若棧非空則用x傳回棧頂元素。
ClearStack(&S)：銷毀棧，并釋放S占用的記憶體空間。
②棧的順序存儲結構
順序棧的結構：
#define maxsize 10
typedef struct {
ElemType data[maxsize];//靜态數組存放棧中元素
int top;//棧頂指針
}Sqstack;
順序棧的基本操作：
棧的初始化
void InitStack(Sqstack &S){
S.top == -1;//s.top=0位置在初始化時并沒有值
}
void test_stack(){
Sqstack s;
InitStack(s);
}
判斷棧空
bool StackEmpty(Sqstack S){
if(S.top == -1)
return true;//棧空
else
return false;//棧不空
}
進棧
bool Push(Sqstack &S,ElemType x){
if(S.top==Maxsize-1){//棧滿
return false;
}
S.data[++S.top]=x;
return true;
}
出棧
bool Pop(Sqstack &S,ElemType x){
if(S.top==-1){//棧空
return false;
}
x = S.data[S.top--];
return true;
}
讀出棧頂元素
bool GetTop(Sqstack S,ElemType &x){
if(S.Top==-1){
return false;
}
else{
x=S.data[S.top];
return true;
}
}
棧的非連續輸入和輸出問題：
進棧序列：1,2,3…，n
（*）出棧序列中每一個元素後面所有比他小的元素組成一個遞減序列。
合法出棧序列的個數：
合法出棧序列個數的公式如下：
f ( n ) = C 2 n n n + 1 \mathbf{f}\left( \mathbf{n} \right) =\frac{\mathbf{C}_{2\mathbf{n}}^{\mathbf{n}}}{\mathbf{n}+1} f(n)=n+1C2nn
共享棧
共享棧的概念
将兩個棧底設定在共享空間的兩端，棧頂向空間中間延伸。（
兩個棧共享同一片空間。
）
判空：
0号棧top == -1
1号棧top == MaxSize
棧滿：
top1-top0 == 1
優點：
存取時間複雜度仍為O（1），但空間利用更加有效。
③棧的鍊式存儲結構
typedef struct linknode{
Elemtype data;
struct linkinode *next;
}*linstack;
//所有的操作都在表頭進行；
鍊棧：所有的操作都在表頭進行。
④隊列的邏輯結構
隊列的概念：
隊列（ Queue）：隻允許在表的一端進行插入，表的另一端進行删除操作的線性表。
隊列的基本操作：
InitQueue（&Q）：初始化隊列，構造一個空隊列Q。
QueueEmpty（Q）：判隊列空，若隊列Q為空傳回true，否則傳回 False。
EnQueue（&Q, x）：入隊，若隊列Q末滿，則将x加入使之成為新的隊尾。
DeQueue（&Q, &x）：出隊，若隊列Q非空，則删除隊頭元素，并用x傳回。
GetHead（&x）：讀隊頭元素，若隊列Q非空則用回隊頭元素。
ClearQueue（&Q）：锴毀隊列，并釋放隊列Q占用的記憶體空間。
⑤隊列的順序存儲
順序隊列的概念：
采用順序存儲結構的隊列。
#define Maxsize 50
typedef struct{
ElemType data[Maxsize];
int rear,front;
}SqQueue;
注意：
front指向隊頭元素，rear指向隊尾元素的下一位元素
（或 front指向隊頭元素的前一位置，rear指向隊尾元素）。
初始時，
front == rear == 0
。
對空的條件：
Q.rear == Q.front
。
隊長的計算：
Q.rear-Q.front
。
隊滿的條件：
Q.rear-Q.front+1==Q.Maxsize
。//該條件可以判斷隊滿，但不可以提高隊列的空間使用率！
注意：順序隊列中的rear和front下标隻可以往後走，不可以回頭，是以當rear達到棧尾的Maxsize時，隻要有元素出棧（front++），實際的隊列存儲空間就在減少。
鍊隊的實作：
鍊隊的結構體：
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
鍊隊的初始化操作：
//初始化隊列(帶頭結點)
void InitQueue(LinkQueue &Q){
//初始時front, rear都指向頭結點
Q.front=Q.rear=(LinkNode*)malloc(sizeof (LinkNode));
Q.front->next=NULL;
}
void testLinkQueue(){
LinkQueue Q;//聲明一個隊列
InitQueue(Q); //初始化隊列
}
鍊隊的入隊操作：
//新元素入隊(帶頭結點)
void EnQueue(LinkQueue &Q, ElemType x){
LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear-next=s; //新結點插入到rear之後
Q.rear=s;//修改表尾指針
}
⑥循環隊列的存儲結構
循環隊列的概念：
把存儲隊列的順序隊列在邏輯上視為一個環。
front指針移動：Q.front =（Q.front+1）% MaxSize
rear指針移動：Q.rear =（Q.rear+1）% MaxSize
隊列長度：
（Q.rear+MaxSize-Q.front）% MaxSize
循環隊列的基本操作：
循環隊列的初始化：
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0;
}
循環隊列的入隊：
bool Enqueue(SqQueue &Q,Elemtype x){
if(Q.rear+1)%MaxSize==Q.front{
return false;//采用方法一進行判定隊滿
}
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize;
return 0;
}
循環隊列的出隊：
bool Dequeue(SqQueue &Q,Elemtype &x){
if(Q.rear==Q.front){
return false;
}
x=Q.data[Q.front];
Q.front=( Q.front+1)%MaxSize;//指針後移
return true;
}
循環隊列的隊頭查找：
bool Dequeue(SqQueue &Q,Elemtype &x){
if(Q.rear==Q.front){
return false;
}
x=Q.data[Q.front];
return true;
}
解決循環隊列的隊滿和隊空條件相同問題：
隊空的條件：Q.rear==Q.front
隊滿的條件：Q.rear==Q.front
方法一：犧牲一個存儲單元
隊空條件：Q.front== Q.rear
隊滿條件：
Q.front==(Q.rear + 1)%MaxSize
方法二：增加一個變量代表元素的個數
初始化：
Q.size = 0//用于元素的計數
隊空條件：Q.size==0
隊滿條件：Q.size==MaxSize
方法三：增加tag辨別
每次删除操作成功時，都令tag=0；每次插入操作成功時，都令tag=1。
初始化：tag=0
隊空條件：
Q.front=Q.rear&& tag==0
隊滿條件：
Q.front=Q.rear&& tag==1
⑦雙端隊列的存儲結構
雙端隊列的概念：
雙端隊列允許兩端都可以進行入隊以及出隊操作的隊列。
⑧棧和隊列的應用
括号比對：
算法思想：
1）初始一個空棧，順序讀入括号。
2）
若是右括号，則與棧頂元素進行比對:
若比對，則彈出棧頂元素并進行下一個元素；
若不比對，則該序列不合法。
3）若是左括号，則壓入棧中。
4）
若全部元素周遊完畢，棧中非空則序列不合法。
括号比對的算法實作：
#define MaxSize 10//定義棧中元素的最大個數
typedef struct{
char data[Maxsize];//靜态數組存放棧中元素
int top;//棧頂指針
}SqStack;
bool bracketCheck(char str1, int length) {
Sqtack S;
InitStack(S); //初始化一個棧
for (int i=0; iclength; i++){
if (str[i]=s'('||str[i]='['||str[i]=='{'){
Push(S, str([i]);} //掃描到左括号,入棧}
else{
if (StackEmpty(S)) //掃描到右括号,且目前棧空
return false; //比對失敗
char topElem;
Pop(S, topElem); //棧頂元素出棧
if(str[i]==')' && topElem!='(')
return false;
if(str[i]==']' && topElem!='[')
return false;
if(str[i]=='}'&& topElem!='{')
return false;
}
}
表達式求值：
中綴運算符轉字尾的算法思想：
若為數字：
直接加入字尾表達式。
若為運算符：
a.若為’(’，入棧。
b.若為)’，則依次把棧中的運算符加入字尾表達式，直到出現（，并從棧中删除（’。
c.若為’+’,’-’,’/’,’*’,
*棧空，入棧；
*棧頂元素為’（，入棧；
*高于棧頂元素優先級，入棧；
*否則，依次彈出棧頂運算符，直到優先級比它低的運算符或’)'為止。
d.周遊完成，若棧非空則依次彈出所有元素。
⑨特殊矩陣的壓縮存儲
特殊矩陣和壓縮存儲的概念：
壓縮存儲：
指多個值相同的元素隻配置設定一個存儲空間，對零元素不配置設定存儲空間
。
特殊矩陣：
指具有許多相同矩陣元素或零元素，并且這些相同矩陣元素或零元素的分布有一定規律性的矩陣
。
特殊矩陣的壓縮存儲：找岀特殊矩陣中值相同的矩陣元素的分布規律，把
那些呈現規律性分布、值相同的多個矩陣元素壓縮存儲到一個存儲空間上
。
對稱矩陣的壓縮計算：
對稱矩陣：若對一個n階方陣A中的任意元素ai,j有ai,j=aj,i(1≤i,j≤n)，則稱其為對稱矩陣。
按行優先：
由數組下标：k=1+2+…+（-1）+j-1，得如下坐标計算公式：
數組下标 k = { i ( i − 1 ) / 2 + j − 1 , i ⩾ j j ( j − 1 ) / 2 + i − 1 , i < j \text{數組下标}\mathbf{k}=\begin{cases} \mathbf{i}\left( \mathbf{i}-1 \right) /2+\mathbf{j}-1,\mathbf{i}\geqslant \mathbf{j}\\ \mathbf{j}\left( \mathbf{j}-1 \right) /2+\mathbf{i}-1,\mathbf{i}<\mathbf{j}\\ \end{cases} 數組下标k={i(i−1)/2+j−1,i⩾jj(j−1)/2+i−1,i<j
三角矩陣的壓縮計算：
三角矩陣：
若
對一個n階方陣Anxn中上（下）對角區元素均為同一常量
，則稱為下（上）三角矩陣。
下三角矩陣的下标計算公式：
數組下标 k = { i ( i − 1 ) / 2 + j − 1 , i ⩾ j n ( n + 1 ) / 2 , i < j \text{數組下标}\mathbf{k}=\begin{cases} \mathbf{i}\left( \mathbf{i}-1 \right) /2+\mathbf{j}-1,\mathbf{i}\geqslant \mathbf{j}\\ \mathbf{n}\left( \mathbf{n}+1 \right) /2,\mathbf{i}<\mathbf{j}\\ \end{cases} 數組下标k={i(i−1)/2+j−1,i⩾jn(n+1)/2,i<j
上三角矩陣的計算公式，同理。
三對角矩陣的壓縮計算：
三對角矩陣：
若對個n階方陣A中的任意元ai,j，當|i-j|>1有ai,j=0（1≤i,j≤n），則稱為三對角矩陣
。
數組下标 k = 3 ∗ ( i − 1 ) − 1 + j − i + 1 + 1 − 1 = 2 i + j − 3 \text{數組下标}\mathbf{k}=3*\left( \mathbf{i}-1 \right) -1+\mathbf{j}-\mathbf{i}+1+1-1=2\mathbf{i}+\mathbf{j}-3 數組下标k=3∗(i−1)−1+j−i+1+1−1=2i+j−3