【数据结构周周练】005顺序队列与链队 -扑克牌的筛选

浅浅的花香味﹌ 2021-06-11 15:12 355阅读 0赞

没有找到有关于队列的经典题目，想到以前一个游戏，觉得改编一下可以当作一道队列的编程题来做。把这道题与自己的算法分享给大家，如果大家有更好的算法，欢迎大家一起交流讨论。

由于普通队列在实现时，采用顺序存储，会浪费掉大量的空间，所以一般在循环队列采用顺序存储，普通队列采用链式存储。

--------------------

一、题目

二、顺序循环队列实现

1、代码

2、执行结果

三、链队实现

1、代码

2、执行结果

--------------------

# 一、题目 #

将扑克牌一个花色按A，2，3，4，5，6，7，8，9，10，J，Q，K排成一叠，A在最上面，先将一张牌放在最下面，再将一张牌弃掉，重复这两个操作，问最后筛选出的是哪个牌。

如果我们自己用扑克牌玩一下，很简单，最后筛选的是J，用队列怎么实现呢，请往下看：

# 二、顺序循环队列实现 #

### 1、代码 ###

#define MAXQSIZE 20
    
    #include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct {
    	char *base;
    	int front;//队头
    	int rear;//队尾
    }SqQueue;
    
    int InitQueue(SqQueue &Q) {
    	Q.base = (char*)malloc(MAXQSIZE * sizeof(SqQueue));
    	if (!Q.base)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	Q.front = Q.rear = 0;
    	return 1;
    }
    
    int EnQueue(SqQueue &Q,char e) {
    	if ((Q.rear+1)%MAXQSIZE == Q.front)//队尾的后一个是队头，说明队列已满，无法入队。
    	{
    		cout << "队列已满" << endl;
    		exit(OVERFLOW);
    	}
    	Q.base[Q.rear] = e;
    	Q.rear = (Q.rear + 1) % MAXQSIZE;
    	return 1;
    }
    
    int DeQueue(SqQueue &Q, char &e) {
    	if (Q.rear == Q.front)//队尾和队头相遇，说明队列已空，无法出队。
    	{
    		cout << "队列已空" << endl;
    		return 0;
    	}
    	e = Q.base[Q.front];
    	Q.front = (Q.front + 1) % MAXQSIZE;
    	return 1;
    }
    
    int main(){
    	char Card[] = { 'A','2','3','4','5','6','7','8','9','10','J','Q','K' };
    	char e;
    	SqQueue Q;
    	InitQueue(Q);
    	for (int i = 0; i < 13; i++)
    	{
    		EnQueue(Q, Card[i]);
    	}
    	while (Q.rear != Q.front)
    	{
    		DeQueue(Q, e);
    		EnQueue(Q, e);
    		DeQueue(Q, e);
    	}
    	cout << "最后筛选出的是：" << e << endl;
    	return 0;
    }

### 2、执行结果 ###

![70][]

## 三、链队实现 ##

### 1、代码 ###

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct QNode {
    	char data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct LinkQueue {
    	QueuePtr front;
    	QueuePtr rear;
    }LinkQueue;
    
    int InitQueue(LinkQueue &Q) {
    
    	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    	if (!Q.front)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	Q.front->next = NULL;
    	return 1;
    }
    
    int EnQueue(LinkQueue &Q, char e) {
    	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    	if (!p)
    	{
    		cout << "结点分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	p->data = e;
    	p->next = NULL;
    	Q.rear->next = p;
    	Q.rear = p;
    	return 1;
    }
    
    int DeQueue(LinkQueue &Q, char &e) {
    	if (Q.front == Q.rear)
    	{
    		cout << "队列已空" << endl;
    		return 0;
    	}
    	QueuePtr p = Q.front->next;
    	e = p->data;
    	Q.front->next = p->next;
    	if (Q.rear == p)
    		Q.rear = Q.front;
    	free(p);
    	return 1;
    }
    
    int main() {
    	char Card[] = { 'A','2','3','4','5','6','7','8','9','10','J','Q','K' };
    	char e;
    	LinkQueue Q;
    	InitQueue(Q);
    	for (int i = 0; i < 13; i++)
    	{
    		EnQueue(Q, Card[i]);
    	}
    	while (Q.rear != Q.front)
    	{
    		DeQueue(Q, e);
    		EnQueue(Q, e);
    		DeQueue(Q, e);
    	}
    	cout << "最后筛选出的是：" << e << endl;
    	return 0;
    }

### 2、执行结果 ###

![70 1][]

[70]: /images/20210516/41c1509d3efe4b559035feacc3d94427.png
[70 1]: /images/20210516/960dfc5b90c64181b95a5006633250e3.png