順序隊列各種基本運算算法的實現
順序隊列是較為普遍的一種隊列實現方式，采用環狀數組來存放隊列元素，并用兩個變量分別指向隊列的前端(front)和尾端(rear)，往隊列中加進或取出元素時分別改變這兩個變量的計數(count)。
隊列中用環狀數組存儲數據（合理利用空間、減少操作），通過基本的append（）將元素加入隊列，serve（）將元素移出隊列，先進入的先移出，retieve得到最先加入隊列的元素。此外在繼承的Extended_queue（）中我增加了empty（）和serve_and_retrieve（）的功能。
【實驗說明】
我選擇的題目：課本中Programming Projects 3.3 P1
問題描述：Write a function that will read one line of input from the terminal. The input is supposed to consist of two parts separated by a colon ':'. As its results, your function should produce a single character as follows:
N No colon on the line.
L The left part(before the colon) is longer than the right.
R The right part(after the colon) is longer than the left.
D The left and right parts have the same length but are different.
S The left and right are exactly the same.
Examples:
Use either a queue or an extended queue to keep track of the left part of the line while reading the right part.
1.分析隊列要實現的基本功能以及繼承的類要拓展的功能從而確定基本成員函數——append（），serve（）,retireve（），拓展隊列中：empty（），serve_and_retrieve（），確定隊列中以環形數組存儲數據從而確定成員函數——Queue_entry entry[],count(記錄隊列中數據數量)
2.編寫隊列的頭文件及實現
3.分析題目中結束程序并輸出幾種字母的條件，簡略畫出功能實現的流程圖，編寫程序。（具體思路見源代碼注釋）
4.簡單測試程序的幾種情況，分析需要改進的地方
【相關代碼】
queue.h
#ifndef QUEUE_H
#define QUEUE_H
const int maxqueue=10;
enum Error_code {success,overflow,underflow};
typedef char Queue_entry ;
class Queue{
public:
Queue();
bool empty() const;
Error_code append(const Queue_entry &item);
Error_code serve();
Error_code retrieve(Queue_entry &item)const;
protected:
int count;
int front,rear;
Queue_entry entry[maxqueue];
};
class Extended_queue:public Queue{
public:
bool full()const;
int size()const;
void clear();
Error_code serve_and_retrieve(Queue_entry &item);
};
#endif
#include"queue.h"
Queue::Queue()
{
count=0;
rear=maxqueue-1;
front=0;
}
bool Queue::empty() const
{
return count==0;
}
Error_code Queue::append(const Queue_entry &item)
{
if(count>=maxqueue)return overflow;
count++;
rear=((rear+1)==maxqueue)?0:(rear+1);
entry[rear]=item;
return success;
}
Error_code Queue::serve()
{
if(count<=0)return underflow;
count--;
front=((front+1)==maxqueue)?0:(front+1);
return success;
}
Error_code Queue::retrieve(Queue_entry &item) const
{
if(count<=0)return underflow;
item=entry[front];
return success;
}
bool Extended_queue::full() const{
return count==maxqueue;
}
int Extended_queue::size()const{
return count;
}
void Extended_queue::clear(){
count=0;
rear=front;
}
Error_code Extended_queue::serve_and_retrieve(Queue_entry &item){
if(count==0)return underflow;
count--;
item=entry[front];
front=((front+1)==maxqueue)?0:(front+1);
return success;
}
【過程記錄】
實驗截圖：
【結果分析】
1.實驗中我以課本后面的練習題為例，實現并驗證了順序隊列的更種功能。
2.隊列與棧一樣是在類中以數組存儲數據，但由于隊列先進先出的特點在實現存儲形式上與棧有一定的不同。因為如果與棧一樣對數據操作，隊列會無限向后擴大，而前面取出過數據的地方將不會再被利用，十分浪費，也很容易溢出。所以我們采用循環數組來存儲，這樣合理利用了資源。但在類的實現要要極為時刻考慮周全rear和front的各種可能，要判斷是不是循環到了前面，count在此時的功能也極為突出。
3.書中的程序看似簡單，但實際判斷各種輸出情況的時候卻極難考慮周全。我首先做出了簡易的流程圖，然后才寫函數，具體分析及思路可見我源碼的注釋。另外本題還有另外一種實現思路：即將左右輸入分別存放在兩個隊列中，邊取去邊比較，那樣在邏輯上容易理解一些。但鑒于題目的要求，我還是用邊從左邊隊列中取出邊比較右邊輸入的方法。
4.我在實驗中遇到的問題：
（1）自己一開始在循環判斷用的是cin.get()=='\n'即遇到回車就停止輸入，但卻無法如料想中結束循環……最終采用cin>>a && waiting（用以標志‘：’的輸入）來作為循環終止的條件，這樣雖然可以運行，但用戶必須輸入Ctrl+‘Z’以結束輸入?？磥碜约簩斎肓鞯睦斫馀c掌握還沒有到位。
（2）另外在檢驗的時候，我發現輸入‘：’之前是否輸入回車情況是有區別的。如
輸入“sam:sam”(無空格)，結果為“R”
輸入“sam : sam”(有空格)，結構為“S”
顯然后者是我希望得到的結果，我分析可能是前面情況‘：’被列入了right的判斷，從而使結構右邊比左邊長。還沒有想到如何改進。