題型一（棧與隊列的基本概念）

1、棧和隊列都是（）。
A、順序存儲的線性結構
B、鏈式存儲的非線性結構
C、限制存取點的線性結構
D、限制存取點的非線性結構

解析：（C）
棧是一種只允許在一端進行插入或刪除操作的線性表，它是一種特殊的線性表，它與隊列具有相同的邏輯結構，都屬于線性結構，區別在于對其中元素的處理不同，棧遵循的原則是先進后出（FILO），即后進的元素先被取出來，它是被限制存取點的線性結構。

隊列與棧一樣，也是一種特殊的線性表，其操作受限，它與棧具有相同的邏輯結構，都屬于線性結構，區別在于其中元素的處理不同，隊列只允許在一端進行插入，且只允許在另一端進行刪除，隊列遵循的原則是先進先出（FIFO），即先入隊列的元素最先離開，它也是被限制存取點的線性結構，與日常生活中的排隊是一樣的。

2、棧和隊列的共同點是（）。
A、都是先進先出
B、都是先進后出
C、只允許在端點處插入和刪除元素
D、沒有共同點

解析：（C）
棧和隊列的共同點是都只允許在一端進行插入或刪除操作的特殊線性表。

題型二（棧與隊列的綜合）

1、設棧S和隊列Q的初始狀態為空，元素a，b，c，d，e，f依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是a，c，f，e，d，b，則棧S的容量至少應該是（）。
A、3
B、4
C、5
D、6

解析：（B）
棧是先進后出，隊列是先進先出。
若容量為3，若要滿足條件，首先元素a通過棧S后，然后進入隊列Q，
得到出隊為{a}；b、c通過棧S后，c首先出棧通過隊列，得到出隊為
{a、c}；此時若要第三個出隊元素為f，則棧中由下至上應該為{b、d、e、f}，所以棧S的容量至少應該是4。

題型三（循環隊列的判空與判滿）

1、假設循環隊列的最大容量為m，隊頭指針是front，隊尾指針是rear，則隊列為滿的條件是（）。
A、(rear+1)%m == front
B、rear == front
C、rear+1 == front
D、(rear-1)%m == front

解析：（A）
設MaxSize為循環隊列的最大容量，(Q.rear+1)%MaxSize == Q.front即隊尾指針進1與MaxSize取余的值等于頭指針時，此時隊列已滿，如下：

當前隊頭指針Q.front=1，Q.rear=0，即(Q.rear+1)%MaxSize=(0+1)%7=1%7=1，等于Q.front=1，所以此時隊列為滿隊，此時隊頭指針在隊尾指針的下一個位置。

題型四（循環鏈表表示隊列）

1、用循環單鏈表來表示隊列，設隊列的長度為n，若只設尾指針，則出隊和入隊的時間復雜度分別為（）。
A、O(1),O(1)
B、O(1),O(n)
C、O(n),O(1)
D、O(n),O(n)

解析：（A）
循環單鏈表表示隊列相當于一個環，由于只設尾指針，出隊時直接出隊，出隊的時間復雜度為O(1)；因為隊頭隊尾相連，尾指針的下一個結點即是隊頭，則入隊的時間復雜度也為O(1)。

2、用循環單鏈表來表示隊列，設隊列的長度為n，若只設頭指針，則出隊和入隊的時間復雜度分別為（）。
A、O(1),O(1)
B、O(n),O(n)
C、O(1),O(n)
D、O(n),O(1)

解析：（D）
循環單鏈表表示隊列相當于一個環，由于只設頭指針，出隊時指針需要從隊頭到隊尾，經過n個結點到達隊尾，所以出隊的時間復雜度為O(n)；入隊時由于有頭指針，可直接入隊，出隊的時間復雜度為O(1)。

題型五（循環隊列的存儲）

1、已知存儲循環隊列的數組長度為21，若當前隊列的頭指針和尾指針的值分別為9和3，則該隊列的當前長度為（）。
A、6
B、12
C、15
D、18

解析：（C）
通過隊尾指針減隊頭指針加上MaxSize的值與MaxSize取余，可得到數據元素個數，即(Q.rear-Q.front+MaxSize)%MaxSize，代碼如下：

//循環隊列的數據元素個數
bool NumQueue(SqQueue Q){if(Q.front==Q.rear)	//若隊列為空，則報錯 return false;int num=(Q.rear-Q.front+MaxSize)%MaxSize;printf("當前循環隊列的數據元素個數為：%d\n",num);
}

題中，Q.front=9，Q.rear=3，MaxSize=21，所以(Q.rear-Q.front+MaxSize)%MaxSize=(3-9+21)%21=15%21=15。

題型六（循環隊列的入隊和出隊）

1、循環隊列存儲在數組A[0,…,m]中，用front和rear分別表示隊頭和隊尾，則入隊時的操作為（）。
A、rear=rear+1
B、rear=(rear+1) mod (m-1)
C、rear=(rear+1) mod m
D、rear=(rear+1) mod (m+1)

解析：（D）
入隊操作針對Q.rear，入隊的代碼通過取余運算實現，隊尾指針加1，即Q.rear=(Q.rear+1)%MaxSize，不管前面(Q.rear+1)為多少，它與MaxSize（例如，MaxSize=5）取余的結果只可能是0、1、2、3、4，也就是隊尾指針Q.rear的每次移動加1。

所以題中，入隊時的操作為rear=(rear+1) mod (m+1)。

1、
A、
B、
C、
D、

解析：（）

1、
A、
B、
C、
D、

解析：（）

1、
A、
B、
C、
D、

解析：（）

1、
A、
B、
C、
D、

解析：（）