(2011.10.30)3_a3.cpp —— 循環隊列結構的定義

源代碼：

// 3_a3.cpp —— 循環隊列結構的定義

/* 
 * -> 程式要求：
 * 1. 完成對循環隊列結構的定義，以及對循環隊列的各種基本運算的實作（每種基本運算用一個函數來實作）。
 * 2. 基本運算包括：初始化Init_sqqueue運算、判隊空Empty_sqqueue運算、入隊En_sqqueue運算、出隊De_sqqueue運算、取隊頭元素Gethead_sqqueue運算。
 * 3. 并且在main函數中分别調用以上各種基本運算的函數來使用，以驗證其功能已實作。
 * 4. 此題的源程式儲存為 3_a3.cpp
 */

/*
 * -> 程式分析
 * 1. 寫循環隊列最需要解決的一個問題是：如何知道它是滿是空？
 * 2. 如課件所說：有三種方法
 *　　1）另設長度計數器n,此時多耗費了空間去儲存變量，多耗費了一點計算時間。
 *　　2）另設标志位以區分隊空、隊滿，多耗費了空間去儲存變量。
 *　　3）入隊前預測試，隊滿條件：front=(rear+1)%maxsize,此時少用一個存儲單元，且front所指處總為空，此時多耗費了計算時間。
 *    每種方法都有利弊，這裡，我也跟很多書本與經典例題一樣，采用第三種方法。
 * 3. 寫循環隊列，因為它不斷地進出，必然會使下标值不斷改變，這裡，進出都需各用一個變量，這樣會比較友善。
 * 4. 循環隊列中，還是如上幾題所說的那樣，有那幾種成員函數[構造，判斷空滿，進，取，出，銷毀].
 * 5. 元素進出如果将資料結構中的棧和隊列相比，不同點是，一個是從頭部出的，一個是從尾部出的，也就是說，棧是LIFO，隊列是FIFO.
 **/

#include <iostream>
#include <cstdlib>
using std::cin;
using std::cout;
using std::endl;

template <typename elem>
class cirqueue
{
private:
	enum { defaultmaxsize = 10};	// 定義預設最大的隊列size
	int lastindex;			// 現在的隊列尾部
	int headindex;			// 現在的隊列頭
	int maxsize;			// 隊列的實際最大size
	elem *arr;				// 現存資料

public:
// 構造，析構函數
	cirqueue(int mz = defaultmaxsize):maxsize(mz), lastindex(0), headindex(0){arr = new elem[maxsize];}
	~cirqueue() { delete [] arr; maxsize = lastindex = headindex = 0;}

// 判空，判滿
	bool isempty();
	bool isfull();

// 入隊，取隊，出隊
	void enqueue(const elem &enelem);
	void gethead(elem & gelem);
	void dequeue();
};

// 判空，判滿
template <typename elem>
bool cirqueue<elem>::isempty()
{
	if ( lastindex == headindex )
		return true;
	else
		return false;
}

template <typename elem>
bool cirqueue<elem>::isfull()
{
	if ( headindex == (lastindex + 1) % maxsize)
		return true;
	else
		return false;
}

// 入隊
template <typename elem>
void cirqueue<elem>::enqueue(const elem &enelem)
{
	if(isfull())
	{
		cout << "隊列已滿，插入失敗。";
		return;
	}
	// 先将元素放入隊列，再将隊列尾下标自增。
	// 這裡可以自行安排，隻是這裡的安排會與删除，提取元素這些函數相關。
	arr[lastindex] = enelem;
	lastindex = (lastindex + 1) % maxsize;
	return;
}

// 取隊
template <typename elem>
void cirqueue<elem>::gethead(elem & gelem)
{
	if ( isempty())
	{
		cout << "隊列為空，不能從隊列中取出頂部元素.";
		return;
	}
	gelem = arr[(lastindex - 1) % maxsize];
	return;
}

// 出隊
template <typename elem>
void cirqueue<elem>::dequeue()
{
	if (isempty())
	{
		cout << "隊列為空，不能從隊列中出隊。";
		return;
	}
	headindex = (headindex + 1) % maxsize;
	return;
}

int main()
{
	// 開始測試循環隊列   
    cout << "\n ----------------------- 現在開始對循環隊列程式進行測試 -----------------------\n\n";  
    cirqueue<int> test;  
    cout << "\n\n -> 入隊測試開始（使用循環語句向棧中插入11個元素）\n\n";  // 棧中一共隻有10個元素，測試最後一次是否會提取失敗 
    for (int i = 0; i != 11; ++i)  
    {  
        cout << "第 " << i + 1 << "次插入";  
        test.enqueue(i);  
		cout << " 操作完成。\n";
    }  
  
    int temp;  
    cout << "\n\n -> 擷取棧頂元素測試\n\n";  
    test.gethead(temp);  
    cout << "    獲得的棧頂元素是：" << temp << endl;  
  
    cout << "\n\n -> 出棧測試開始（使用循環語句向棧中提取11個元素）\n\n"; // 棧中一共隻有10個元素，測試最後一次是否會提取失敗   
    for (int i = 0; i != 11; ++i)  
    {  
        cout << "第 " << i + 1 << "次: ";  
        test.dequeue();  
		cout << " 操作完成。\n";
    }  
    cout << endl;  

	system("pause");
	return 0;
}
           

結果：

----------------------- 現在開始對循環隊列程式進行測試 -----------------------



 -> 入隊測試開始（使用循環語句向棧中插入11個元素）

第 1次插入 操作完成。
第 2次插入 操作完成。
第 3次插入 操作完成。
第 4次插入 操作完成。
第 5次插入 操作完成。
第 6次插入 操作完成。
第 7次插入 操作完成。
第 8次插入 操作完成。
第 9次插入 操作完成。
第 10次插入隊列已滿，插入失敗。 操作完成。
第 11次插入隊列已滿，插入失敗。 操作完成。


 -> 擷取棧頂元素測試

    獲得的棧頂元素是：8


 -> 出棧測試開始（使用循環語句向棧中提取11個元素）

第 1次:  操作完成。
第 2次:  操作完成。
第 3次:  操作完成。
第 4次:  操作完成。
第 5次:  操作完成。
第 6次:  操作完成。
第 7次:  操作完成。
第 8次:  操作完成。
第 9次:  操作完成。
第 10次: 隊列為空，不能從隊列中出隊。 操作完成。
第 11次: 隊列為空，不能從隊列中出隊。 操作完成。

請按任意鍵繼續. . .