数据结构循环队列及应用（泛型编程）

循环队列

特点：

先进先出（FIFO）
队头队尾指针只向后移动
入队时队尾指针后移，出队时队头指针后移
当队头指针与队尾指针相等时即为队空
当(Q.rear + 1) % MAX_Q_SIZE == Q.front时即为队满

定义：

template<typename QElemType>
struct SqQueue
{ 
   
	QElemType qet[MAX_Q_SIZE];
	int front, rear;
};

基本操作：

template<typename QElemType>
Status initSqQueue(SqQueue<QElemType>& Q)//初始化
//队头队尾指针置0
{ 
   
	Q.rear = 0;
	Q.front = 0;
	return OK;
}

template<typename QElemType>
bool isSqQueueEmpty(SqQueue<QElemType>& Q)//判断队空
//队头指针于队尾指针相等
{ 
   
	return Q.rear == Q.front;
}

template<typename QElemType>
bool isSqQueueFull(SqQueue<QElemType>& Q)//判断队满
{ 
   
	return (Q.rear + 1) % MAX_Q_SIZE == Q.front;
}

template<typename QElemType>
Status enSqQueue(SqQueue<QElemType>& Q, QElemType qe)//入队 qe为要入队的数据
//将e赋值给队尾指针位置的元素，队尾指针后移，要注意循环队列后移都需要进行加1取余操作
{ 
   
	if (isSqQueueFull(Q))//队满
	{ 
   
		cout << "队满" << endl;
		return ERROR;
	}//未满
	Q.qet[Q.rear] = qe;
	Q.rear = (Q.rear + 1) % MAX_Q_SIZE;
	return OK;
}

template<typename QElemType>
Status deSqQueue(SqQueue<QElemType>& Q, QElemType& qe)//出队 qe用来接受出队的元素
//将队头指针位置的元素赋值给qe，队头指针后移，此时qe必须时引用才能正确接收到数据
{ 
   
	if (isSqQueueEmpty(Q))//队空
	{ 
   
		cout << "队空" << endl;
		return ERROR;
	}//不空
	qe = Q.qet[Q.front];
	Q.front = (Q.front + 1) % MAX_Q_SIZE;
	return OK;
}

template<typename QElemType>
int getSqQueueLength(SqQueue<QElemType>& Q)//获取队列实际长度
{ 
   
	return ((Q.rear - Q.front) + MAX_Q_SIZE) % MAX_Q_SIZE;
}

template<typename QElemType>
Status getSqQueueFront(SqQueue<QElemType>& Q, QElemType& qe)//获取队头元素 qe用于接收队头元素
//将队头指针位置的元素赋值给qe，qe必须时引用
{ 
   
	if (isSqQueueEmpty(Q))//队空
	{ 
   
		cout << "队空" << endl;
		return ERROR;
	}//不空
	qe = Q.qet[Q.front];
	return OK;
}

template<typename QElemType>
Status clearSqQueue(SqQueue<QElemType>& Q)//清空队列
//队头队尾指针置0
{ 
   
	Q.rear = 0;
	Q.front = 0;
	return OK;
}

template<typename QElemType>
ostream& operator<<(ostream& os, SqQueue<QElemType>& Q)//运算符重载 按线性表格式输出
//按线性表格式输出元素，即 (a1, a2, a3, ……, an) 的格式
{ 
   
	if (isSqQueueEmpty(Q))//队空
	{ 
   
		os << "队空";
		return os;
	}
	os << "(";
	for (int i = Q.front; i != Q.rear; i = (i + 1) % MAX_Q_SIZE)//注意i的变化与指针相同，需要进行取余操作
	{ 
   
		os << Q.qet[i] << ", ";
	}
	os << "\b\b)";//注意删除最后一个元素的逗号
	return os;
}

测试：

void testSqQueue()//测试队列功能
{ 
   
	int i;
	typedef int QElemType;
	QElemType qe;
	SqQueue<QElemType> Q;
	initSqQueue(Q);
	cout << "测试开始……" << endl;
	cout << "初始化完成……" << endl;
	cout << "当前队列为：" << Q << " 队列长度为：" << getSqQueueLength(Q) << endl;
	
	cout << endl << "0~4入队……" << endl;
	for (i = 0; i < 5; i++)
	{ 
   
		enSqQueue(Q, i);
	}
	cout << "当前队列为：" << Q << " 队列长度为：" << getSqQueueLength(Q);
	getSqQueueFront(Q, qe);
	cout << " 队头元素为：" << qe << endl;

	cout << endl << "出队3个元素……" << endl;
	for (int j = 0; j < 3; j++)
	{ 
   
		deSqQueue(Q, qe);
	}
	cout << "当前队列为：" << Q << " 队列长度为：" << getSqQueueLength(Q);
	getSqQueueFront(Q, qe);
	cout << " 队头元素为：" << qe << endl;

	cout << endl << "5~9入队……" << endl;
	for (; i < 10; i++)
	{ 
   
		enSqQueue(Q, i);
	}
	cout << "当前队列为：" << Q << " 队列长度为：" << getSqQueueLength(Q);
	getSqQueueFront(Q, qe);
	cout << " 队头元素为：" << qe << endl;

	cout << endl << "10~14入队……" << endl;
	for (; i < 15; i++)
	{ 
   
		enSqQueue(Q, i);
	}
	cout << "当前队列为：" << Q << " 队列长度为：" << getSqQueueLength(Q);
	getSqQueueFront(Q, qe);
	cout << " 队头元素为：" << qe << endl;
	cout << "测试结束……" << endl;

	system("pause");
}

队列的应用——凯撒加密：
输入明文和密钥，分别依次读取一个明文和密钥，将明文的字母按字母表顺序向后移动密钥在字母表中的位置，若超出字母表，则继续从头开始后移，将当前密钥出队再重新入队，便于密钥重复利用

//头文件
#pragma once
#include<iostream>
#include"SqQueue.h"
using namespace std;

const int maxKeyLength = 9;
const int maxArrayLength = 1000;

void enterKey(char* key, int& keyLength);//输入密钥 key用于保存密钥，keyLength用于保存密钥长度
void enterMessage(char* message, int& messageLength);//输入消息 message用于保存消息，messageLength用于保存消息长度
void keyEnSqQueue(SqQueue<char>& keyQ, char* key, int keyLength);//将密钥入队 便于多次使用，提高简洁性
void cesarEncode(SqQueue<char> keyQ, char* message, int messageLength, char* ciphertext);//加密 密钥队列，消息，消息长度，存放密文
void cesarDecode(SqQueue<char> keyQ, char* ciphertext, int ciphertextLength, char* cleartext);//解密 密钥队列，密文，密文长度，存放解密结果
void cesar();

//实现
#include<iostream>
#include"SqQueue.h"
#include"Cesar.h"
using namespace std;

void enterKey(char* key, int& keyLength)//输入密钥 key用于保存密钥，keyLength用于保存密钥长度
{ 
   
	char c;
	keyLength = 0;
	cout << "输入密钥：" << endl;
	c = getchar();//吃掉上一个操作的回车
	c = getchar();
	while (c != '\n')
	{ 
   
		if (c <= 'z' && c >= 'a')
		{ 
   
			c = c - 'a' + 'A';//将所有字母转换为大写
		}
		key[keyLength++] = c;
		c = getchar();
	}
	key[keyLength] = '\0';
}

void enterMessage(char* message, int& messageLength)//输入消息 message用于保存消息，messageLength用于保存消息长度
{ 
   
	char c;
	messageLength = 0;
	cout << "输入消息：" << endl;
	c = getchar();
	while (c != '\n')
	{ 
   
		if (c <= 'z' && c >= 'a')
		{ 
   
			c = c - 'a' + 'A';//将所有字母转换为大写
		}
		message[messageLength++] = c;
		c = getchar();
	}
	message[messageLength] = '\0';
}

void keyEnSqQueue(SqQueue<char>& keyQ, char* key, int keyLength)//将密钥入队 便于多次使用，提高简洁性
{ 
   
	for (int i = 0; i < keyLength; i++)
		enSqQueue(keyQ, key[i]);
}

void cesarEncode(SqQueue<char> keyQ, char* message, int messageLength, char* ciphertext)//加密 密钥队列，消息，消息长度，存放密文
{ 
   
	for (int i = 0; i < messageLength; i++)
	{ 
   
		if (message[i] > 'Z' || message[i] < 'A')
		{ 
   
			ciphertext[i] = message[i];//非字母不加密
		}
		else
		{ 
   
			char keychar;
			deSqQueue(keyQ, keychar);
			ciphertext[i] = ((message[i] - 'A') + (keychar - 'A')) % 26 + 'A';//取余操作使超出Z后重新从A开始循环，并提高简洁性
			enSqQueue(keyQ, keychar);//入队使密钥可以复用
		}
	}
	ciphertext[messageLength] = '\0';
}

void cesarDecode(SqQueue<char> keyQ, char* ciphertext, int ciphertextLength, char* cleartext)//解密 密钥队列，密文，密文长度，存放解密结果
{ 
   
	for (int i = 0; i < ciphertextLength; i++)
	{ 
   
		if (ciphertext[i] > 'Z' || ciphertext[i] < 'A')
		{ 
   
			cleartext[i] = ciphertext[i];//非字母无需解密
		}
		else
		{ 
   
			char keychar;
			deSqQueue(keyQ, keychar);
			cleartext[i] = (((ciphertext[i] - 'A') - (keychar - 'A')) + 26) % 26 + 'A';//取余操作使小于A后重新从Z开始循环，并提高简洁性
			enSqQueue(keyQ, keychar);//入队使密钥可以复用
		}
	}
	cleartext[ciphertextLength] = '\0';
}

void cesar()
{ 
   
	char key[maxKeyLength];
	char message[maxArrayLength];
	char ciphertext[maxArrayLength];
	char cleartext[maxArrayLength];
	int keyLength;
	int messageLength;
	SqQueue<char> keyQ;
	initSqQueue(keyQ);

	enterKey(key, keyLength);
	keyEnSqQueue(keyQ, key, keyLength);
	enterMessage(message, messageLength);
	cesarEncode(keyQ, message, messageLength, ciphertext);
	cesarDecode(keyQ, ciphertext, messageLength, cleartext);//ciphertextLength == messageLength
	cout << "明文：" << endl;
	cout << message << endl;
	cout << "密文：" << endl;
	cout << ciphertext << endl;
	cout << "解密：" << endl;
	cout << cleartext << endl;
	system("pause");
}

测试：

今天的文章数据结构循环队列及应用（泛型编程）分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/61860.html

数据结构 循环队列及应用（泛型编程）

循环队列

相关推荐

发表回复

数据结构循环队列及应用（泛型编程）