隊列的應用：雙端隊列

雙端隊列(Deque:double ended queue)就是一個兩端都是結尾的隊列。隊列的每一端都可以插入數據項和移除數據項。相對於普通隊列，雙端隊列的入隊和出隊操作在兩端都可進行。

雙端隊列的示意圖：

left：左端 right：右端

這裡我們使用最常用的順序結構來存儲雙端隊列，為了節省空間，把它首尾相連，構成循環隊列。並且規定left指向左端的第一個元素，right指向右端的下一個位置。那麼隊空的判斷則是left==right，隊滿是(left-1+MAX)%MAX==right或者(right-left+MAX)%MAX==MAX。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+z+rPuM+4vdq/tLT6wuujujwvcD4KPHA+wOC2qNLlus3A4Mq1z9Y8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#include #include using namespace std; //隊列的最大存儲空間為MAX const int MAX = 10; typedef int ElemType; //雙端隊列類 class Deque //double ended queue { private: int size; //隊列中元素個數 ElemType *base; int left, right; //0代表左端left，1代表右端right public: //構造函數 Deque(); //析構 ~Deque() { delete[]base; } //獲取大小 int getSize() { return size; } //隊空判斷 bool empty() { return left == right; } //或者size==0 //隊滿判斷 bool full() { return (left - 1 + MAX) % MAX == right; } //獲取指定端的頭元素 bool topAt(ElemType&, int); //在指定端插入(入隊) bool pushAt(ElemType, int); //在指定端刪除(出隊) bool popAt(int); //從指定端打印隊列 void print(int); //請空隊列 void clear(); }; Deque::Deque() { base = new ElemType[MAX]; left = right = 0; size = 0; } bool Deque::topAt(ElemType& data, int end) { if (empty()) return false; if (end == 0) data = base[left]; else data = base[(right - 1 + MAX) % MAX]; return true; } bool Deque::pushAt(ElemType data, int end) { if (full()) return false; if (end == 0) { left = (left - 1 + MAX) % MAX; base[left] = data; } else { base[right] = data; right = (right + 1) % MAX; } return true; } bool Deque::popAt(int end) { if (empty()) return false; if (end == 0) left = (left + 1) % MAX; else right = (right - 1 + MAX) % MAX; return true; } void Deque::print(int end) { if (empty()) { cout << "空隊列，無法遍歷！" << endl; return; } if (end == 0) { int i = left; while (i != right) { cout << setw(4) << base[i]; i = (i + 1) % MAX; } } else { int i = right; while (i != left) { i = (i - 1 + MAX) % MAX; cout << setw(4) << base[i]; } } cout << endl; } void Deque::clear() { left = right = 0; size = 0; }主函數和相關方法：

void check(int& end)  //對端號進行檢查
{
	while (cin >> end && !(end == 0 || end == 1))
	{
		cout << "端號不對，重新輸入：";
	}
}
void input(Deque& deque)  //輸入函數
{
	int end;
	cout << "在指定端入隊，0左端，1右端：";
	check(end);
	ElemType data;
	cout << "輸入數據，輸入0結束" << endl;
	while (cin >> data && data)
	{
		deque.pushAt(data, end);
	}
}
void traverse(Deque& deque)   //從指定端遍歷
{
	int end;
	cout << "從指定端遍歷：";
	check(end);
	deque.print(end);
}
int main()
{
	cout << "******雙端隊列演練******" << endl;
	Deque deque;
	cout << "新建雙端隊列" << endl;
	cout << "隊列是否為空：";
	deque.empty() ? cout << "Yes!" << endl : cout << "No!" << endl;
	input(deque);
	traverse(deque);
	input(deque);
	traverse(deque);
	ElemType data;
	int end;
	cout << "獲取指定定端的頭元素：";
	check(end);
	deque.topAt(data, end) ? cout << data << endl : cout << "隊空！" << endl;
	cout << "刪除指定定端的頭元素：";
	check(end);
	deque.popAt(end) ? cout << "刪除成功" << endl : cout << "隊空！" << endl;
	traverse(deque);
	cout << "清空隊列，隊列是否為空：";
	deque.clear();
	deque.empty() ? cout << "Yes!" << endl : cout << "No!" << endl;
	system("pause");
	return 0;
}

若是有所幫助，頂一個哦！

專欄目錄：數據結構與算法目錄