第三章

【3.1】

03、

• 假設(shè)以I和O分別表示入棧和出操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，可以操作的序列稱為合法序列，否則稱為非法序列。

  如IOIIOIOO 和IIIOOIOO是合法的，而IOOIOIIO和IIIOIOIO是不合法的。

  通過分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回 false(假定被判定的操作序列已存入一維數(shù)組中)

個(gè)人理解：

就構(gòu)造一個(gè)棧S，然后將這個(gè)序列進(jìn)行處理，其中I表示入棧、O表示出棧，直接對棧S進(jìn)行Push和Pop操作，有錯(cuò)誤就報(bào)錯(cuò)，沒錯(cuò)誤就表示該序列合法，即可。

答案好像并沒有創(chuàng)建棧，也沒有執(zhí)行Push、Pop的操作。而是直接對序列進(jìn)行分析，只作了數(shù)學(xué)上的判定。

算法思想：

??掃描該序列，每掃描至任意一個(gè)位置均需檢查出棧次數(shù)（即“O”的個(gè)數(shù)）是否小于等于入棧次數(shù)（“I”的個(gè)數(shù)），若大于則為非法序列。掃描結(jié)束后，再判斷入棧和出棧次數(shù)是否相等，若不相等則也不合法。

bool Judge(char A[]) {int i=0;int j=0;	//j表示字母I的個(gè)數(shù)int k=0;	//k表示字母O的個(gè)數(shù)while(A[i]!='\0') {	//對字符串的遍歷操作if(A[i]=='I')j++;if(A[i]=='O')k++;if(k>j) {printf("序列非法\n");return false;}}if(j!=k) {printf("序列非法\n");return false;}else {printf("序列合法\n");return true;}}

另一種算法思想：

??入棧后，棧內(nèi)元素個(gè)數(shù)增加1個(gè)；出棧后，棧內(nèi)元素個(gè)數(shù)減少1個(gè)。因此可將判定一組出入棧序列是否合法轉(zhuǎn)化為一組由+1和-1組成的序列，它的任意前綴子序列的累加和不能小于0（每執(zhí)行一次出?；蛉霔２僮骱罅⒓磁袛?#xff09;則合法，否則非法。此外，整個(gè)序列的累加和必須等于0。

思考：

??這個(gè)問題是否和括號匹配問題一樣？——感覺好像是沒啥區(qū)別。

04、

• 設(shè)單鏈表的表頭指針為L，結(jié)點(diǎn)結(jié)構(gòu)由data和next兩個(gè)域構(gòu)成，其中data域?yàn)樽址?。試設(shè)計(jì)算法判斷該鏈表的全部n個(gè)字符是否中心對稱。

  例如xyx、xyyx都是中心對稱。

個(gè)人理解：

第二章單鏈表部分的算法應(yīng)該已經(jīng)解決過這個(gè)問題了。

我大概有三種思路：

1）將單鏈表的后半段原地逆置，之后使用兩個(gè)間距為k（k為表長的一半）的指針同步遍歷比較。

分析：原地逆置但鏈表需要$O(n)$，兩指針同步遍歷需要$O(n)$。因此時(shí)間復(fù)雜度為$O(n)$，空間復(fù)雜度為$O(1)$。

2）把單鏈表中的元素復(fù)制到數(shù)組里，然后用數(shù)組直接判斷中心對稱。

分析：復(fù)制需要$O(n)$，數(shù)組判斷中心對稱需要$O(n)$。時(shí)間復(fù)雜度為$O(n)$，空間復(fù)雜度為$O(n)$。

3）從前往后把單鏈表中的各個(gè)結(jié)點(diǎn)元素依次入棧。之后將棧中元素一一出棧，并與單鏈表中從前往后元素進(jìn)行比較。（如果知道鏈表的表長，只入棧前半個(gè)表的元素即可，一一出棧并與后半個(gè)表的元素比較）

分析：單鏈表元素一一入棧需要$O(n)$，一一出棧再進(jìn)行比較需要$O(n)$。時(shí)間復(fù)雜度為$O(n)$，空間復(fù)雜度為$O(n)$。

05、

• 設(shè)有兩個(gè)棧s1、s2都采用順序棧方式，并共享一個(gè)存儲區(qū)[0,...,maxsize-1]，為了盡量利用空間，減少溢出的可能，可采用棧頂相向、迎面增長的存儲方式。試設(shè)計(jì)s1、s2有關(guān)入棧和出棧的操作算法。

個(gè)人理解：

就是考察共享?xiàng)５娜霔?、出棧具體操作上的細(xì)節(jié)。（不難，但是比較重要，各方面都要想清楚）

那就是棧s1初始棧頂指針為-1，棧s2初始棧頂指針為maxsize，對于兩個(gè)棧而言，入棧操作都是先將指針移動(dòng)一位（s1是往大了加1，s2是往小了減1的區(qū)別），然后再賦值。出棧操作反之，先取出當(dāng)前棧頂指針的元素，然后棧頂指針移動(dòng)一位（與入棧相反）。此外還有判斷?？?、棧滿的問題，?？盏膯栴}好說，棧滿的問題就是根據(jù)s2的棧頂指針是否和s1的棧頂指針相鄰即可。

分析：

??兩個(gè)棧共享向量空間，將兩個(gè)棧的棧底設(shè)在向量兩端。初始時(shí)，s1棧頂指針為-1，s2棧頂指針為maxsize。當(dāng)兩個(gè)棧頂指針相鄰時(shí)判定為棧滿。兩個(gè)棧頂相向、迎面增長，棧頂指針指向棧頂元素。

【注意】

1）主要就是注意一下兩個(gè)棧各自在入棧、出棧時(shí)，棧頂指針是如何變化的。對于s1而言，它是一個(gè)傳統(tǒng)意義上的棧，而對于s2而言，它的操作大約是要反過來一下的。

2）對于所有入棧、出棧操作，都要時(shí)刻牢記**“入棧判滿？出棧判空？”**的檢查。

（0）如下定義共享?xiàng)５臄?shù)據(jù)結(jié)構(gòu)：

（當(dāng)然，不這樣定義，也無所謂。直接定義一個(gè)數(shù)組，然后定義兩個(gè)變量指向棧頂位置也一樣）

/* 共享?xiàng)５慕Y(jié)構(gòu)定義 */
#define maxsize 100
typedef struct {int stack[maxsize];		//?？臻gint top[2];				//存放兩個(gè)棧頂指針
}stk;stk s;					//定義棧s為上述結(jié)構(gòu)類型的變量，而且為全局變量
s.top[0] = -1;
s.top[1] = maxsize;		//初始化兩個(gè)棧頂指針的值

（1）入棧操作

int push(int i, int x) {//入棧操作，i為棧號，當(dāng)i=0時(shí)表示是s1執(zhí)行入棧，當(dāng)i=1時(shí)表示s2執(zhí)行入棧//x是入棧元素//入棧成功返回1，失敗返回0if(i<0 || i>1) {printf("棧號輸入不對");exit(0);}if(s.top[1]-s.top[0] == 1) {printf("棧已滿\n");return 0;}if(i==0) {s.stack[++s.top[0]] = x;return 1;}if(i==1) {s.stack[--s.top[1]] = x;return 1;}
}

（2）出棧操作

int pop(int i) {//出棧操作，i為棧號，當(dāng)i=0時(shí)表示是s1執(zhí)行出棧，當(dāng)i=1時(shí)表示s2執(zhí)行出棧//出棧成功，函數(shù)返回值為出棧的元素值；失敗則返回-1if(i<0 || i>1) {printf("棧號輸入錯(cuò)誤");exit(0);}if(i==0) {if(s.top[0] == -1) {printf("棧s1已為空，無法出棧");return -1;} elsereturn s.stack[s.top[0]--];}if(i==1) {if(s.top[1] == maxsize) {printf("棧s2已為空，無法出棧");return -1;} else return s.stack[s.top[1]++];}
}

【3.2】

01、

• 若希望循環(huán)隊(duì)列中的元素都能得到利用，則需設(shè)置一個(gè)標(biāo)志域 tag，并以 tag 的值為0或1來區(qū)分隊(duì)頭指針 front 和隊(duì)尾指針 rear 相同時(shí)的隊(duì)列狀態(tài)是“空”還是“滿”試編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)和出隊(duì)算法。

個(gè)人理解：

既然隊(duì)空、隊(duì)滿的依據(jù)都是front==rear，只不過隊(duì)空時(shí)tag==0，隊(duì)滿時(shí)tag==1。

那么，首先，隊(duì)列為空時(shí)，初始化為tag=0，之后不斷入隊(duì)、出隊(duì)操作。若最后一次操作執(zhí)行入隊(duì)，并使得隊(duì)滿，則tag=1；若最后一次操作執(zhí)行出隊(duì)，并使得隊(duì)空，則tag=0。

咋樣在隊(duì)滿的時(shí)候再檢查一下上次操作的性質(zhì)？——沒必要。我們每次執(zhí)行入隊(duì)，都設(shè)tag=1，每次執(zhí)行出隊(duì)，都同時(shí)設(shè)tag=0，這樣，如果發(fā)現(xiàn)front==rear了，同時(shí)就再去看看tag是幾就行了。沒那么復(fù)雜。

算法思想：

??在循環(huán)隊(duì)列的類型結(jié)構(gòu)中，增設(shè)一個(gè)tag的整型變量，進(jìn)隊(duì)時(shí)置tag為1，出隊(duì)時(shí)置tag為0（因?yàn)橹挥腥腙?duì)操作可能導(dǎo)致隊(duì)滿，也只有出隊(duì)操作可能導(dǎo)致隊(duì)空）。隊(duì)列Q初始時(shí)，置tag=0, front=rear=0。這樣，隊(duì)列的4要素如下：

隊(duì)空條件：Q.front==Q.rear && Q.tag==0

隊(duì)滿條件：Q.front==Q.rear && Q.tag==1

進(jìn)隊(duì)操作：Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%MaxSize; Q.tag=1

出隊(duì)操作：x=Q.data[Q.rear]; Q.front=(Q.front+1)%MaxSize; Q.tag=0

1）入隊(duì)算法

int EnQueue(SqQueue &Q, int x) {if(Q.front==Q.rear && Q.tag==1)return 0;		//隊(duì)滿Q.data[Q.rear] = x;Q.rear = (Q.rear+1)%MaxSize;Q.tag = 1;		//可能隊(duì)滿return 1;
}

2）出隊(duì)算法

int DeQueue(SqQueue &Q, int &x) {if(Q.front==Q.rear && Q.tag==0)return 0;		//隊(duì)空x = Q.data[Q.front];Q.front = (Q.front+1)%MaxSize;Q.tag = 0;		//可能隊(duì)空return 1;
}

02、

• Q 是一個(gè)隊(duì)列，S 是一個(gè)空棧，實(shí)現(xiàn)將隊(duì)列中的元素逆置的算法。

個(gè)人理解：

很簡單了。隊(duì)列元素依次出隊(duì)，并依次入棧。最后棧中元素依次全部出棧即可。不是光輸出元素值，那就再入回到隊(duì)列中去。

算法思想：

??這個(gè)問題主要考察對于隊(duì)列和棧的特性的理解。由于僅對隊(duì)列進(jìn)行一系列操作不可能將其中的元素逆置，而?？梢詫⑷霔５脑啬嫘蛱崛〕鰜?#xff0c;因此我們可以讓隊(duì)列中的元素逐個(gè)地出隊(duì)、入棧；全部入棧后再逐個(gè)出棧、入隊(duì)列。

void Inverser(Stack &S, Queue &Q) {//本算法實(shí)現(xiàn)將隊(duì)列中的元素逆置while(!QueueEmpty(Q)) {x = DeQueue(Q);		//隊(duì)列中全部元素依次出隊(duì)Push(S, x);			//元素依次入棧}while(!StackEmpty(S)) {Pop(S, x);		//棧中全部元素依次出棧EnQueue(Q, x);	//再入隊(duì)}
}

03、

• 利用兩個(gè)棧 S1 和 S2 來模擬一個(gè)隊(duì)列，已知棧的 4 個(gè)運(yùn)算定義如下：

Push(S, x);			//元素x入棧S
Pop(S, x);			//S出棧并將出棧的值賦給x
StackEmpty(S);		//判斷棧是否為空
StackOverflow(S);	//判斷棧是否滿

如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的 3 個(gè)運(yùn)算（形參由讀者根據(jù)要求自己設(shè)計(jì)）？

Enqueue;
Dequeue;
QueueEmpty;

有兩個(gè)棧，S1和S2。兩種棧的操作：入棧、出棧，此外還可以判棧空、判棧滿。

以此來完成：入隊(duì)、出隊(duì)、判隊(duì)空，的操作。

什么叫實(shí)現(xiàn)隊(duì)列的入隊(duì)、出隊(duì)，就是，必須得是先進(jìn)先出的運(yùn)算邏輯才叫隊(duì)列。

棧是后進(jìn)先出的邏輯，怎么達(dá)到先進(jìn)先出的效果？——兩個(gè)棧配合使用。

讓序列依次入棧到S1中，例如abcd進(jìn)入S1：[a b c d]

此時(shí)S1出棧，肯定是d c b a，這肯定達(dá)不到隊(duì)列的要求；但是可以把S1的出棧序列再次入棧到S2中，進(jìn)入S2：[d c b a]。之后S2再出棧，就能得到a b c d。從而達(dá)到隊(duì)列的效果。

但是好像有個(gè)問題：如果是一個(gè)元素、一個(gè)元素的這樣操作的話，例如把a入棧S1后，立馬出棧，再入棧到S2中，這樣，元素a和直接入棧沒區(qū)別，最后也不是隊(duì)列的效果。必須一次性把所需序列全部入棧S1、再出棧S1、再入棧到S2中，才有效果。但是對于單個(gè)元素、單個(gè)元素這種的，就不能這樣做。

看下答案怎么說。

算法思想：

??利用兩個(gè)棧 S1 和 S2 來模擬一個(gè)隊(duì)列，當(dāng)需要向隊(duì)列中插入一個(gè)元素時(shí)，用 S1 來存放已輸入的元素，即 S1 執(zhí)行入棧操作。當(dāng)需要出隊(duì)時(shí)，則對S2執(zhí)行出棧操作；注意，此時(shí)需要判斷S2是否為空，若為空，則需要將S1先出棧并入棧到S2；若S2不為空則直接執(zhí)行S2出棧即可?？偨Y(jié)如下兩點(diǎn)：

（主要要搞清楚到底啥叫出隊(duì)，啥叫入隊(duì)。不是說入隊(duì)就是abc進(jìn)入，出隊(duì)就是cba出來。入隊(duì)、出隊(duì)都只是一個(gè)元素的事。）

1）對S2的出棧操作，用作出隊(duì)。若S2為空，則先將S1中的所有元素送入S2。

2）對S1的入棧操作，用作入隊(duì)。若S1滿，必須先保證S2為空，才能將S1中的元素全部插入S2中。

入隊(duì)算法：

int EnQueue(Stack &S1, Stack &S2, int e) {if(!StackOverflow(S1)) {Push(S1, e);return 1;}if(StackOverflow(S1) && !StackEmpty(S2)) {printf("隊(duì)列滿");return 0;}if(StackOverflow(S1) && StackEmpty(S2)) {while(!StackEmpty(S1)) {Pop(S1, x);Push(S2, x);}}Push(S1, e);return 1;
}

出隊(duì)算法：

void DeQueue(Stack &S1, Stack &S2, int &x) {if(!StackEmpty(S2))Pop(S2, x);else if(StackEmpty(S1))printf("隊(duì)列為空");		//S2為空，此時(shí)去S1找，發(fā)現(xiàn)S1也為空else {while(!StackEmpty(S1)) {	//S2為空，如果S1里有，就先運(yùn)過來Pop(S1, x);Push(S2, x);}Pop(S2, x);		//都運(yùn)過來之后，S2出棧一下}
}

判斷隊(duì)列為空的算法：

int QueueEmpty(Stack S1, Stack S2) {if(StackEmpty(S1) && StackEmpty(S2))return 1;elsereturn 0;
}

04、

[2019 統(tǒng)考真題]

• 請?jiān)O(shè)計(jì)一個(gè)隊(duì)列，要求滿足：①初始時(shí)隊(duì)列為空；②入隊(duì)時(shí)，允許增加隊(duì)列占用空間；③出隊(duì)后，出隊(duì)元素所占用的空間可重復(fù)使用，即整個(gè)隊(duì)列所占用的空間只增不減；④入隊(duì)操作和出隊(duì)操作的時(shí)間復(fù)雜度始終保持為 0(1)。請回答下列問題：

  1）該隊(duì)列是應(yīng)選擇鏈?zhǔn)酱鎯Y(jié)構(gòu)，還是應(yīng)選擇順序存儲結(jié)構(gòu)？

  2）畫出隊(duì)列的初始狀態(tài)，并給出判斷隊(duì)空和隊(duì)滿的條件。

  3）畫出第一個(gè)元素入隊(duì)后的隊(duì)列狀態(tài)。

  4）給出入隊(duì)操作和出隊(duì)操作的基本過程。

根據(jù)題意，應(yīng)該是要使用鏈?zhǔn)疥?duì)列。主要是因?yàn)槿腙?duì)時(shí)允許增加隊(duì)列占用空間這一點(diǎn)。如果是順序存儲空間會比較難實(shí)現(xiàn)。鏈表若想增加空間，則插入一個(gè)新結(jié)點(diǎn)即可。

此外，由于出隊(duì)元素所占空間可以重復(fù)使用，因此應(yīng)該還是個(gè)循環(huán)隊(duì)列。

對于單鏈表存放隊(duì)列而言，通常單鏈表表頭對應(yīng)的是隊(duì)頭，單鏈表表尾對應(yīng)的是隊(duì)尾?？芍?#xff0c;出隊(duì)操作在隊(duì)頭完成，入隊(duì)操作在隊(duì)尾完成。

綜上，大概使用一個(gè)循環(huán)單鏈表（可以帶上一個(gè)頭結(jié)點(diǎn)，效果更好了），作為該循環(huán)隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)即可實(shí)現(xiàn)題目要求。

個(gè)人理解：

1）應(yīng)選擇鏈?zhǔn)酱鎯Y(jié)構(gòu)。而且選用帶頭、尾指針的循環(huán)單鏈表比較合適。

2）初始狀態(tài)為僅有一個(gè)頭結(jié)點(diǎn)L，此時(shí)Q->front=Q->rear=NULL。隊(duì)空判斷條件為Q->front == Q->rear；隊(duì)滿判斷條件為Q->rear->next = Q->front。

3）含有一個(gè)頭結(jié)點(diǎn)、一個(gè)成員結(jié)點(diǎn)的循環(huán)單鏈表。

4）入隊(duì)操作：若隊(duì)列未滿，則尾指針后移一位、元素賦值到尾指針?biāo)附Y(jié)點(diǎn)上；若隊(duì)列已滿，則建立一個(gè)新結(jié)點(diǎn)，將新結(jié)點(diǎn)插入到尾指針后面。

出隊(duì)操作：若隊(duì)列非空，則輸出頭指針?biāo)冈?#xff0c;并將頭指針后移一位。若隊(duì)列已經(jīng)為空，則無法出隊(duì)。

下面看下答案。

答案：

1）采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，循環(huán)單鏈表，即可滿足四點(diǎn)要求。而順序存儲結(jié)構(gòu)無法滿足要求②。

2）可以參考循環(huán)隊(duì)列的思維。不過此處由于是鏈?zhǔn)酱鎯?#xff0c;因此入隊(duì)時(shí)空間不夠還可以動(dòng)態(tài)增加。同樣地，循環(huán)鏈?zhǔn)疥?duì)列也要區(qū)分隊(duì)滿、隊(duì)空的情況，這里參考循環(huán)隊(duì)列犧牲一個(gè)存儲單元的思想來做分析。初始時(shí)，創(chuàng)建只有一個(gè)空閑結(jié)點(diǎn)的循環(huán)單鏈表，頭指針front和尾指針rear均指向空閑節(jié)點(diǎn)，如下圖所示。

隊(duì)空的判定條件：front == rear

隊(duì)滿的判定條件：front == rear->next

不要用死板的眼光看待問題?？催@里可能會覺得：現(xiàn)在不是“隊(duì)空”嗎，什么也沒有，而此時(shí)front == rear->next啊，這隊(duì)空和隊(duì)滿怎么判定條件一樣？

人家這就是隊(duì)滿。現(xiàn)在隊(duì)列的實(shí)際空間為0，若想要入隊(duì)一個(gè)元素，那就是隊(duì)滿的情形。同時(shí)，若想要出隊(duì)一個(gè)元素，那就是隊(duì)空的情形。

這個(gè)地方，鏈?zhǔn)疥?duì)列要和順序循環(huán)隊(duì)列區(qū)分清楚，不要混為一談。

3）插入第一個(gè)元素后的狀態(tài)如下圖所示：

個(gè)人認(rèn)為就在頭結(jié)點(diǎn)的后面做頭插即可。

4）操作的基本過程：

（他這個(gè)操作是根據(jù)他第（3）問畫的圖那樣來弄的；如果畫的圖不一樣，操作相應(yīng)也有區(qū)別）

1.入隊(duì)操作

若(front == rear->next)					//隊(duì)滿則 在rear后面插入一個(gè)新的空閑結(jié)點(diǎn);
入隊(duì)元素保存到rear所指結(jié)點(diǎn)中;
rear = rear->next;
return;

2.出隊(duì)操作

若(front == rear)			//隊(duì)空則 出隊(duì)失敗，返回;
取 front所指結(jié)點(diǎn)中的元素e;
front = front->next;
return e;