1.本周學(xué)習(xí)總結(jié)

    棧和隊(duì)列的學(xué)習(xí)還是比較好理解的，就是實(shí)際寫起代碼來困難。通過老師上課展示的源代碼，在做pta時照著葫蘆畫瓢，稍微能有一些理解。這周收獲最大的就是知道刪除棧和隊(duì)列元素之后需要返回棧頂和對頭元素，不然會出現(xiàn)異常訪問的情況。在利用隊(duì)列進(jìn)行操作的過程中，注意入隊(duì)的時候判斷有沒有空來決定要不要修改頭指針，出隊(duì)時則增設(shè)一個條件判斷是否為最后一個節(jié)點(diǎn)，然后單獨(dú)處理。利用循環(huán)鏈隊(duì)列的時候，則特別要注意最后要將頭指針和尾指針的關(guān)系用next建立起來，循序循環(huán)隊(duì)列則要注意在進(jìn)行出入隊(duì)操作時，首尾指針做相應(yīng)的加減運(yùn)算后應(yīng)當(dāng)對MaxSize取余，保證不出現(xiàn)**假溢出**的情況。
    棧在符號配對問題上學(xué)會了用容器和string來做，可以直接調(diào)用庫函數(shù)pop,push,top來進(jìn)行出棧，進(jìn)棧，返回棧頂操作，調(diào)用empty函數(shù)判斷棧有沒有為空，為空則返回true，相當(dāng)方便，就是還不太熟練。
    隊(duì)列的容器操作則和棧的有些不同，在做銀行隊(duì)列模擬的時候，最大的收獲就是知道隊(duì)列的容器front和pop的區(qū)別，front函數(shù)返回的是隊(duì)頭元素，pop函數(shù)只是將隊(duì)頭元素彈出，不返回任何值。還有一個附加功能就是函數(shù)back() 返回最后被壓入的元素(隊(duì)尾元素)，如果需要逆序輸出隊(duì)列元素的時候可以用到。
    本次上機(jī)考一開始是比較開心的，循環(huán)隊(duì)列，另類堆棧還有符號配對都是原題，過了第一題另類堆棧后就不順利了，另外兩題一直改不出錯誤，直到出了考場才發(fā)現(xiàn)原來是一些細(xì)節(jié)問題。可能考前太過于自信吧，覺得自己只要知道思路就好了，其他不用管，但偏偏細(xì)節(jié)決定成敗。而且，我總覺得自己學(xué)習(xí)方法出了問題，努力和結(jié)果不成正比，應(yīng)該是沒理解到題目或?qū)ψ约禾^相信了吧。。。

2.PTA實(shí)驗(yàn)作業(yè)

2.1.題目1：在一個數(shù)組中實(shí)現(xiàn)兩個堆棧

2.1.1代碼截圖

2.1.2本題PTA提交列表說明。

• Q1：一開始提交就出現(xiàn)了輸出超限這個錯誤
• A1：經(jīng)同學(xué)指點(diǎn)才明白過來共享?xiàng)Ｊ遣豢梢詫蓚€棧頂都置為-1的，另一個應(yīng)該為Maxsize，然后依次向中間靠近
• Q2：當(dāng)時在vs上運(yùn)行正確后交上去仍是答案錯誤，表示非常不解
  vs運(yùn)行結(jié)果
  
  pta測試結(jié)果
  
• A2：在pop函數(shù)中，應(yīng)該先返回棧頂元素再S->Top做相應(yīng)的加減，此處可能是vs測試不夠嚴(yán)格導(dǎo)致沒有發(fā)現(xiàn)錯誤

2.2 題目2：舞伴問題

假設(shè)在周末舞會上，男士和女士們分別進(jìn)入舞廳，各自排成一隊(duì)。跳舞開始，依次從男隊(duì)和女隊(duì)隊(duì)頭各出一人配成舞伴，若兩隊(duì)初始人數(shù)不同，則較長那一隊(duì)未配對者等待下一輪舞曲。現(xiàn)要求寫一算法模擬上述舞伴配對問題。 你需要用隊(duì)列操作實(shí)現(xiàn)上述算法。請完成下面5個函數(shù)的操作。

2.2.1代碼截圖

2.2.2PTA提交列表說明

• Q1:一開始的編譯錯誤是忘記該題為函數(shù)題，直接將整個代碼粘貼上去了

• A1：去掉原有代碼即可

• Q2:答案錯誤，程序出現(xiàn)亂碼
  

• A2:一開始以為亂碼是因?yàn)檩敵龅臅r候類型錯了導(dǎo)致，就一直在檢查，直到對比同學(xué)代碼，才發(fā)現(xiàn)應(yīng)該在出隊(duì)列DeQueue這個函數(shù)中將front指針將自增再返回結(jié)果，因?yàn)楹竺婧瘮?shù)要返回?cái)?shù)給X，所以應(yīng)該放在前面。

• 此題的話代碼難點(diǎn)不多，就是函數(shù)之間的包含關(guān)系，舞伴配對那個函數(shù)包含了所有函數(shù)的調(diào)用，只要弄清楚他們之間的關(guān)系，還是比較好做。一開始以為隊(duì)列Q是先存所有的dancer然后再根據(jù)性別分別放入隊(duì)列。后面發(fā)現(xiàn)可以不用這么復(fù)雜，直接進(jìn)隊(duì)就好，Q只是一個函數(shù)定義需要用到的變量

2.3 題目3：判斷字符串是否對稱

編寫一個算法利用順序棧判斷一個字符串是否是對稱串。所謂對稱串是指從左向右讀和從右向左讀的序列相同。

2.3.1設(shè)計(jì)思路

• 利用棧來存儲字符串
• 計(jì)算字符串長度
• 利用循環(huán)遍歷到長度的1/2
  • 將字符串前半部分入棧
• 判斷字符串長度是奇數(shù)的話，就除2加一，存到變量 j 里面，以便循環(huán)一半
• 循環(huán)從上一步的 j 到最后length為止
  • if碰到棧頂元素和字符串后半部分不相等，就輸出no并返回
  • 否則棧頂指針下移，繼續(xù)找
• 最后循環(huán)未輸出no，則字符串是對稱的
• 這題利用棧先進(jìn)后出的特點(diǎn)來判斷字符串是否對稱

2.3.2代碼截圖

2.3.3PTA提交列表說明

• A1：一開始的編譯錯誤是在輸入#include的時候不小心多輸了一個空格，導(dǎo)致編譯錯誤，錯誤提示如下
  
  -Q2：在編譯器上調(diào)試的時候，計(jì)算字符串line長度發(fā)生錯誤
  -A2：將sizeof改為strlen就可以了

2.4 題目4：銀行業(yè)務(wù)隊(duì)列簡單模擬

設(shè)某銀行有A、B兩個業(yè)務(wù)窗口，且處理業(yè)務(wù)的速度不一樣，其中A窗口處理速度是B窗口的2倍 —— 即當(dāng)A窗口每處理完2個顧客時，B窗口處理完1個顧客。給定到達(dá)銀行的顧客序列，請按業(yè)務(wù)完成的順序輸出顧客序列。假定不考慮顧客先后到達(dá)的時間間隔，并且當(dāng)不同窗口同時處理完2個顧客時，A窗口顧客優(yōu)先輸出。

2.4.1設(shè)計(jì)思路

• 利用容器來存儲隊(duì)列元素，函數(shù)調(diào)用什么的更加方便好用
• 先循環(huán)輸入號碼，對2取余，如果是奇數(shù)就進(jìn)A隊(duì)，否則進(jìn)B隊(duì)，此處調(diào)用函數(shù)push（注意：push里面要有內(nèi)容，否則會發(fā)生錯誤）
• 先判斷A隊(duì)是否為空隊(duì)，是就要讓B隊(duì)進(jìn)行循環(huán)輸出
  • 設(shè)置temp變量，讓B隊(duì)第一個出隊(duì)元素前面不帶空格
  • 輸出B隊(duì)的一個元素，用到front()函數(shù)，此時返回的是隊(duì)頭元素特別注意：后面還要加上pop()函數(shù)讓隊(duì)頭元素出隊(duì)，否會進(jìn)入死循環(huán)
  • 最后return 0，不再進(jìn)行后面語句
• A隊(duì)不為空的話，則先設(shè)置一個flag變量控制第一個元素前不帶空格
  • 第一個元素出隊(duì)后還要判斷此時A隊(duì)有沒有空才可以繼續(xù)，不空第二個元素出隊(duì)才合法
  • 然后if判斷B不為空就可以出隊(duì)
  • 此時讓flag=0，使下次循環(huán)輸出的第一個A隊(duì)元素前面帶空格
• 出現(xiàn)B隊(duì)比A隊(duì)長的情況，此時B隊(duì)就未空，還要一個循環(huán)逐個讓B中元素出隊(duì)

2.4.2代碼截圖

2.4.3PTA提交列表說明

• Q1：一開始輸出的元素是9個，而且亂碼
• A1：在一開始A中第一個元素出隊(duì)時沒有加上pop函數(shù)，導(dǎo)致多輸出一個
• Q2：前4個號碼正確，后面4個亂碼
• A2：這個時候我一直檢查后面的邏輯問題，卻發(fā)現(xiàn)是在一開始將數(shù)字用數(shù)組存儲時，for循環(huán)本身i++了，我循環(huán)里面又讓i++導(dǎo)致第四到第八個數(shù)組位置沒有存入數(shù)字，刪掉即可
• A3：后面發(fā)現(xiàn)可以不用數(shù)組，直接邊輸入邊判斷是奇數(shù)還是偶數(shù)，然后入隊(duì)，這樣降低了空間復(fù)雜度

3、棧和隊(duì)列上機(jī)考試

錯題1：另類循環(huán)隊(duì)列

如果用一個循環(huán)數(shù)組表示隊(duì)列，并且只設(shè)隊(duì)列頭指針Front，不設(shè)尾指針Rear，而是另設(shè)Count記錄隊(duì)列中元素個數(shù)。請編寫算法實(shí)現(xiàn)隊(duì)列的入隊(duì)和出隊(duì)操作。

錯誤代碼：

正確代碼：

解決辦法：

• Q1：一開始沒有認(rèn)真審題，以為是順序隊(duì)列，然后寫的代碼就錯誤

• A1：改為循環(huán)隊(duì)列，首尾指針加減后對MaxSize取余

• Q2：上訴交上去仍是答案錯誤，無限循環(huán)

• A2：把Q->Count當(dāng)成了尾指針，導(dǎo)致后面的while(Q->Count)循環(huán)出不來，經(jīng)修改后即可（此處特別注意循環(huán)隊(duì)列隊(duì)頭隊(duì)尾以及Maxsize的關(guān)系）

• 在審題的時候還是要仔細(xì)，這題在考前沒有做，是臨場發(fā)揮，比較不熟悉。對循環(huán)隊(duì)列的首尾指針移動時需要對MaxSize取余不是很理解

錯題2：符號配對

假設(shè)表達(dá)式中允許包含3種括號：圓括號、方括號和大括號。即(,[,'{'。編寫一個算法判斷表達(dá)式中的括號是否正確配對， 要求利用棧的結(jié)構(gòu)實(shí)現(xiàn)。

錯誤代碼：

正確代碼：

解決辦法

• Q :測試點(diǎn)都不正確，([1+2])輸出的是no

• A1:find函數(shù)未找到返回的是-1，所以if判斷條件應(yīng)該為！=-1，當(dāng)時忘記了這個知識點(diǎn)

• A2:棧不為空沒有右符號與之配對的情況下應(yīng)該要輸出棧頂元素并換行輸出no，加上換行符即可

• A3:符號匹配時，應(yīng)該
  將 改為
  匹配是找左符號中對應(yīng)右符號的位置下的符號和棧頂元素是不是相同，而不是直接在左符號中找符號

• 這題在考前是做過的，按照老師的方法用容器存儲符號，調(diào)用find,empty等庫函數(shù)來寫非常方便，就是在考試的時候，可能也是時間比較緊，寫的代碼在判斷條件時像未找到符號應(yīng)該返回的是-1忘記了，一時間又急于找自己的邏輯錯誤，導(dǎo)致這題失分嚴(yán)重，終歸還是自己沒有理解透這個題目，多練習(xí)幾次就好了