資料結構學習筆記（特殊的線性表：棧與隊列）

　　　　　　　　　　　　　　　　　　　　　棧與隊列

棧是限定僅在表尾（棧頂）進行插入和删除操作的線性表（後進先出）。

隊列是隻允許在一端進行插入操作，而在另一端進行删除操作的線性表（先進先出）。

棧（Stack）：

1.下标為0的一端作為棧底比較好，因為首元素都存在棧底，變化最小，是以讓它作為棧底。

定義一個top變量來訓示棧頂元素在數組中的位置。棧頂位置top必須小于存儲棧長度StackSize，把空棧的判定條件定位top等于-1。

2.進棧與出棧操作（順序存儲結構）：

進棧操作push：

/*插入元素e為新的棧頂元素*/

Status Push(SqStack *S, SElemType e)

{

if (S->top == MAXSIZE - 1) /*棧滿*/

return ERROR;

S->top++; /*棧頂指針增加一*/

S->data[S->top] = e; /*将新插入元素指派給棧頂空間*/

return OK;

}

出棧操作pop：

/*若棧不空，則删除S的棧頂元素，用e傳回其值，并傳回OK；否則傳回ERROR*/

Status Pop(SqStack *S, SElemType *e)

if (S->top == -1)

return ERROR;

*e = S->data[S->top]; /*将要删除的棧頂元素指派給e*/

S->top--; /*棧頂指針減一*/

*進棧與出棧兩者的時間複雜度均是O(1)。

3.兩棧共享空間：

數組有兩個端點，兩個棧有兩個棧底，讓一個棧的棧底為數組的始端，即下标為0處，另一個棧為棧的末端，即下标為數組長度n-1處。這樣，兩個棧如果增加元素，就是兩端點向中間延伸。

棧1為空時，就是top1等于-1時；而當top2等于n時，即是棧2為空時。

兩個棧見面知識，也就是兩個指針之間相差1時，即top1 + 1 == top2 為棧滿。

4.棧的鍊式存儲結構：

棧頂放在單連結清單的頭部。

對于鍊棧來說，是不需要頭結點的。

對于鍊棧來說，基本不存在棧滿的情況。

鍊棧的空其實就是top=NULL。

5.進棧與出棧操作（鍊式存儲結構）：

進棧操作：

Status Push(LinkStack *S, SElemType e)

LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));

s->data=e;

s->next=S->top; /*把目前的棧頂元素指派給新結點的直接後繼*/

S->top=s; /*将新的結點s指派給棧頂指針*/

S->count++;

出棧操作：

/*若棧不空，則删除S的棧頂元素，用e傳回其值，并傳回OK;否則傳回ERROR*/

Status Pop(LinkStack *S, SElemType *e)

LinkStackPtr P;

if (StackEmpty(*S))

*e=S->top->data;

p=S->top; /*将棧頂結點指派給p*/

S->top=S->top->next; /*使得棧頂指針下移一位，指向後一結點*/

free(p); /*釋放結點p*/

S->count--;

*鍊棧的出棧push和出棧pop操作沒有任何循環操作，時間負責度均為O(1)。

*順序棧和鍊棧，它們在時間複雜度上是一樣的，均為O(1)。

*如果棧的使用過程中元素變化不可預料，有時很小，有時非常大，那麼最好是用鍊棧；反之，如果它的變化在可控範圍内，建議使用順序棧會更好一些。

6.棧的應用：遞歸

遞歸定義：把一個直接調用自己或者通過一系列的調用語句間接地調用自己的函數，稱作遞歸函數。

每個遞歸定義必須至少有一個條件，滿足時遞歸不再進行，即不再引用自身二十傳回值退出。

*疊代和遞歸的差別是：疊代使用的是循環結構，遞歸使用的是選擇結構。遞歸能使程式的結構更清晰，更簡潔，更容易讓人了解，進而減少讀懂代碼的時間。但是大量的遞歸調用會建立函數的副本，會耗費大量的時間和記憶體。疊代則不需要反複調用函數和占用額外的記憶體。

遞歸過程退回的順序是它前行順序的逆襲。

7.棧的應用：四則運算表達式求值

字尾表達式：所有的符号都是在要運算數字的後面出現。

中綴表達式：标準四則運算表達式。

*字尾表達式運算規則：從左到右周遊表達式的每個數字和符号，遇到數字就進棧，遇到是符号，就将處于棧頂兩個數字出棧，進行運算（後出棧的那個數字是“被”的，比如“被減數”，前面那個比如“減數”，運算結果出棧，一直到最終獲得結果。

*中綴表達式轉字尾表達式：

規則：從左到右周遊中綴表達式的每個數字和符号，若是數字就輸出，即成為字尾表達式的一部分；若是符号，則判斷其與棧頂符号的優先級，是右括号或優先級低于棧頂符号（乘除優先加減）則棧頂元素依次出棧并輸出，并将目前符号出棧，一直到最終輸出字尾表達式為止。

隊列（Queue）：

1.隊列定義：隊列是隻允許在一端進行插入操作，而在另一端進行删除操作的線性表。

隊列是一種先進先出的線性表。允許插入的一端稱為隊尾，允許删除的一端稱為隊頭。

2.把隊列的這種頭尾相接的順序存儲結構稱為循環對列。

3.判斷隊列究竟是空還是滿？

*辦法一是設定一個标志變量flag，當front == rear，且flag = 0 時為隊列空，當front == rear，且 flag = 1時為隊列滿。

*辦法二是當隊列空時，條件就是front = rear，當隊列滿時，我們修改其條件，保留一個元素空間：

設隊列的最大尺寸為QueueSize，隊列滿的條件是（rear+1）% QueueSize == front（取模“%”的目的就是為了整合rear與front大小為一個問題）。

通用的計算隊列長度公式為：

（rear - front + QueueSize) % QueueSize

4.循環隊列操作（隊列的順序存儲結構）：

循環隊列的順序存儲結構代碼如下：

typedef int QElemType; /*QElemType類型根據實際情況而定，這裡假設為int*/

/*循環隊列的順序存儲結構*/

typedef struct

QElemType data[MAXSIZE];

int front; /*頭指針*/

int rear; /*尾指針，若隊列不空，指向隊列尾元素的下一位置*/

}SqQueue;

循環隊列的初始化代碼如下：

/*初始化一個空隊列Q*/

Status InitQueue(SqQueue *Q)

Q->front = 0;

Q->rear = 0;

循環隊列求隊列長度代碼如下：

/*傳回Q的元素個數，也就是隊列的目前長度*/

int QueueLength(SqQueue Q)

return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;

循環隊列的入隊列操作代碼如下：

/*若隊列未滿，則插入元素e為Q新的隊尾元素*/

Status EnQueue(SqQueue *Q, QElemType e)

if((Q->rear+1)%MAXSIZE == Q->front) /*隊列滿的判斷*/

Q->data[Q->rear]=e; /*将元素e指派給隊尾*/

Q->rear=(Q->rear+1)%MAXSIZE; /*rear指針後移一位置*/

return OK;

循環隊列的出隊列操作代碼如下：

/*若隊列不空，則删除Q中隊頭元素，用e傳回其值*/

Status DeQueue(SqQueue *Q, QElemType *e)

if (Q->front == Q->rear) /*隊列空的判斷*/

*e = Q->data[Q->front]; /*将隊頭元素指派給e*/

Q->front = (Q->front + 1) % MAXSIZE; /*front指針向後移一位置*/

/*若到最後則轉到數組頭部*/

5.隊列的鍊式存儲結構—-尾進頭出。

隊頭指針指向鍊隊列的頭結點。隊尾指針指向終端結點。空隊列時，front和rear都指向頭結點。

鍊隊列的結構為：

typedef struct QNode; /*結點結構*/

QElemType data;

struct QNode *next;

}QNode, *QueuePtr;

typedef struct /*隊列的連結清單結構*/

QueuePtr front, rear; /*隊頭，隊尾指針*/

}LinkQueue;

6.隊列的鍊式存儲結構—-入隊與出隊操作：

入隊操作：其實就是在連結清單尾部插入結點。

/*插入元素e為Q的新的隊尾元素*/

Status EnQueue(LinkQueue *Q, QElemType e)

QueuePtr s=(QueuePtr)malloc(sizeof(QNode));

if(!s) /*存儲配置設定失敗*/

exit(OVERFLOW);

s->next=NULL;

Q->rear->next=e; /*把擁有元素e的新結點s指派給原隊尾結點的後繼，*/

Q->rear=s; /*把目前s設定為隊尾結點，rear指向s*/

出隊操作：就是頭結點的後繼結點出隊，将頭結點的後繼改為它後面的結點，若連結清單除頭結點外隻剩一個元素時，則需将rear指向頭結點。

/*若隊列不空，删除Q的隊頭元素，用e傳回其值，并傳回OK，否則傳回ERROR*/

Status DeQueue(LinkQueue *Q, QElemType *e)

QueuePtr p;

if(Q->front==Q->rear)

p=Q->front->next; /*将欲删除的隊頭結點暫存給p*/

*e=p->data; /*将欲删除的隊頭結點的值指派給e*/

Q->front->next=p->next; /*将原隊頭結點後繼p->next指派給頭結點後繼*/

if(Q->rear==p) /*若隊頭是隊尾，則删除後将rear指向頭結點*/

Q->rear=Q->front;

free(p);

*循環隊列與鍊隊列比較：

時間上：時間複雜度都為O（1）；

空間上：循環隊列需要事先申請好空間，使用期間不釋放，在空間上，鍊隊列更加靈活。

*建議：在可以确定隊列長度最大值的情況下，建議用循環隊列，如果無法預估隊列的長度時，則用鍊隊列。

#總結：棧分為順序棧和鍊棧，其中順序棧可以通過使用“兩棧共享空間”的方法解決順序棧的弊端；

           隊列分為順序隊列和鍊隊列，其中順序隊列可以通過使用“循環隊列”的方法解決順序隊列的弊端。