本文共 5694 字，大约阅读时间需要 18 分钟。

基本代码实现

#include
   
    using namespace std;enum error_code{
   	success, underflow};struct node{
   	int data;	node* next;};class linkQueue{
   	public:		linkQueue();		~linkQueue();		bool empty()const; // 判断是否为空 		int getCount()const; // 得到队列长度 		error_code get_front(int& x)const; // 获取队头元素		error_code append(const int x); // 入队 		error_code serve(); // 出队		error_code clear(); // 清空队列 		error_code display(); // 显示队列内容 	private:		int count;		node *front, *rear;};linkQueue::linkQueue(){
   	front = new node;	front->next = NULL;	rear = front;	count = 0;}linkQueue::~linkQueue(){
   	while(!empty()) serve();}bool linkQueue::empty()const{
   	return count == 0;	// 或者： return front = rear;	// 或者： return front->next = NULL; }int linkQueue::getCount()const{
   	return count;}error_code linkQueue::get_front(int& x)const{
   	if(empty()) return underflow;	x = front->next->data;	return success;}error_code linkQueue::append(const int x){
   	node* q = new node;	q->data = x;	q->next = NULL;	rear->next = q;	rear = q;	count++;	return success;}error_code linkQueue::serve(){
   	if(empty()) return underflow;	node *q=front->next;	front->next=q->next;	delete q; 	count--;	if(front->next==NULL)	{
   		rear = front;		return success;	}	return success;}error_code linkQueue::clear(){
   	if(empty()) return underflow;	while(getCount() != 0) serve();}error_code linkQueue::display(){
   	if(empty()) return underflow;	node* q = new node;	node* t = new node;	q = front;	while(q->next != NULL)	{
   		cout << q->next->data << " ";		t = q->next;		q = t;	}	cout << endl;}bool ReferenceError(error_code a){
   	if(a == underflow)	{
   		cout << "underflow!" << endl;		return false;	}	return true;}int main(){
   	linkQueue q;	int front;		for(int i = 0; i < 10; i++) // 出队 	    ReferenceError(q.append(i));	for(int i = 0; i < 3; i++) // 入队 	    ReferenceError(q.serve());	ReferenceError(q.get_front(front)); // 取对头 	cout << front << endl;	ReferenceError(q.display()); // 展示队列	cout << q.getCount() << endl; // 获得队列元素数量 	error_code(q.clear()); // 清空队列 	cout << q.getCount() << endl;		return 0;}
   

链队列案例

• 案例一(周末舞会)：周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的对头上各出一人配成舞伴，规定每个舞曲只能有一对跳舞者，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲，现用程序模拟舞伴配对问题。
• 案例二(杨辉三角)：用队列计算并打印杨辉三角前n行。
• 案例三（酒桌文化）：n个人围成一个圆桌，按照顺时针的顺序1， 2，…， n进行编号，某一个人开始报一个数字，然后顺时针的下一个人会报数+1，当某个人报的数字含有一或是七的倍数时，这个人退出游戏，其他人接着报数，直到剩下一个人。输入n, m, t,其中m代表开始报数的人的编号，t表示开始报数的人报出的数字是t，然后接下来有n行，是这n个人的名字，求最后一个人的名字。

#include
   
    using namespace std;enum error_code{
   	success, underflow};struct node{
   	int data;	node* next;};class linkQueue{
   	public:		linkQueue();		~linkQueue();		bool empty()const; 		int getCount()const; 		error_code get_front(int& x)const; 		error_code append(const int x);		error_code serve(); 	private:		int count;		node *front, *rear;};linkQueue::linkQueue(){
   	front = new node;	front->next = NULL;	rear = front;	count = 0;}linkQueue::~linkQueue(){
   	while(!empty()) serve();}bool linkQueue::empty()const{
   	return count == 0;}int linkQueue::getCount()const{
   	return count;}error_code linkQueue::get_front(int& x)const{
   	if(empty()) return underflow;	x = front->next->data;	return success;}error_code linkQueue::append(const int x){
   	node* q = new node;	q->data = x;	q->next = NULL;	rear->next = q;	rear = q;	count++;	return success;}error_code linkQueue::serve(){
   	if(empty()) return underflow;	node *q=front->next;	front->next=q->next;	delete q; 	count--;	if(front->next==NULL)	{
   		rear = front;		return success;	}	return success;}bool ReferenceError(error_code a){
   	if(a == underflow)	{
   		cout << "underflow!" << endl;		return false;	}	return true;}// 周末舞会void danceInWeek(){
   	cout << "周末舞会问题！" << endl;		// 初始化题目条件(m: 男士人数 n：女士人数  k：舞曲数)	int m, n, k;	cin >> m >> n >> k;		// 初始化队列结构	linkQueue q1, q2;	int front1, front2;	for(int i = 0; i < m; i++)	    ReferenceError(q1.append(i));	for(int i = 0; i < n; i++)	    ReferenceError(q2.append(i));		// 开始计算 	while(k--)	{
   		ReferenceError(q1.get_front(front1));		ReferenceError(q2.get_front(front2));		cout << front1 << " 与 " << front2 << "一起跳舞" << endl;		ReferenceError(q1.serve());		ReferenceError(q2.serve());		ReferenceError(q1.append(front1));		ReferenceError(q2.append(front2));	}}// 杨辉三角void YHtriangle(){
   	cout << "杨辉三角问题!" << endl;		// 初始化题目条件	int n;	cin >> n;		// 初始化队列结构	linkQueue q;	int s1, front;	 	// 开始计算	cout << 1 << endl;	ReferenceError(q.append(1));	for(int i = 2; i <= n; i++)	{
   		s1 = 0;		for(int j = 1; j <= i - 1; j++)		{
   			ReferenceError(q.get_front(front));			ReferenceError(q.serve());			cout << s1 + front << "  ";			ReferenceError(q.append(s1 + front));			s1 = front;		}		cout << 1 << endl;		ReferenceError(q.append(1));	} }// 酒桌游戏bool isSeven(int n) // 判断是否含有 7 {
   	int k;	while(n != 0)	{
   		k = n % 10;		if(k == 7)		    return true;		n /= 10;	}	return false;}void drinkingGame(){
   	cout << "酒桌游戏问题!" << endl;		// 初始化题目条件	int n, m, t;	cin >> n >> m >> t;	// 初始化队列结构	linkQueue q;	int front;		// 开始计算	for(int i = 0; i < n; i++) // 给人添加编号 	    ReferenceError(q.append((m + i) % n));	for(int i = 0; q.getCount() != 1; i++)	{
   		ReferenceError(q.get_front(front));			cout << "本次报数人：" << front << "   " << "报数：" << t + i << "  ";			if((t + i) % 7 == 0 || isSeven(t + i))	    {
   	    	ReferenceError(q.serve());	    	cout << "出队！！" << "  " << "剩余人数：" << q.getCount() << endl;		}		else		{
   			ReferenceError(q.append(front));			ReferenceError(q.serve());			cout << "回队尾！！" << "  " << "剩余人数：" << q.getCount() << endl;		}	}	ReferenceError(q.get_front(front));	cout << "最后一个人是：" << front << endl; }int main(){
   	// 周末舞会	danceInWeek();		// 杨辉三角	YHtriangle();		// 酒桌游戏 	drinkingGame();		return 0;}
   

如果对以上案例的顺序队列解法感兴趣，可以看看我的另一篇博客：

转载地址：http://ztnqi.baihongyu.com/