C++数据结构队列

一、提要

队列：一种受限制的线性表，它是一种运算受限制的线性表，先进先出。不能随意插入，只能在尾部插入，在头部删除。队列其实没什么好说的，但今天正好是第三天，必须写

二、使用顺序存储（数组）实现：

采用数组来保存队列的元素，设立一个队首变量 front ，一个队尾变量 rear，分别指向队首和队尾元素。

#include 
   
    using namespace std;#define MAX_SIZE 5 //数组最大长度typedef int DataType_t; //数据类型 DataType_t//队列用数组定义一个队列typedef struct {	DataType_t queue[MAX_SIZE];	int front;    //数组开始元素的下标(队头指针)	int rear;     //指向第一个可以插入的位置(队尾指针)}Queue_t;//判断队列是否为空bool isEmpty(Queue_t *Q) {	if (!Q) return false;	if (Q->front == Q->rear) {//如果队头指针和队尾指针相等就为空		cout << "queue is empty" << endl;		return true;	}	return false;}//判断队列是否为满bool isFull(Queue_t *Q) {	if (!Q) return false;	if (Q->rear == MAX_SIZE) {//如果队头指针和最大长度相等就为满		cout << "queue is fill" << endl;		return true;	}	return false;}//初始化队列bool queueInit(Queue_t *Q) {	if (!Q) return false;	Q->rear = Q->front = 0;	return true;}//入队bool queueEntry(Queue_t *Q, DataType_t  *data) {	if (!Q || !data) return false;	if (isFull(Q)) {		return false;	}	Q->queue[Q->rear] = *data;	Q->rear++;	return true;}//出队 把首个元素赋值给data//方式一: 出一个元素时:后面的所有元素往前移一步bool queueRemove(Queue_t *Q, DataType_t  *data) {	if (!Q || !data) return false;	if (isEmpty(Q)) {		return false;	}	*data = Q->queue[Q->front];	for (int i = Q->front + 1; i < Q->rear; i++) {		Q->queue[i - 1] = Q->queue[i];	}		Q->rear--;		return true;}// 方式二: 出一个元素时:对头指针(Q->front)往前一步bool queueRemove2(Queue_t *Q, DataType_t  *data) {	if (!Q || !data) return false;	if (isEmpty(Q)) {		return false;	}	*data = Q->queue[Q->front];	Q->front = Q->front + 1;	return true;}//查看队列中首个元素;bool queueLook(Queue_t *Q, DataType_t *data) {	if (!Q || !data) return false;	if (isEmpty(Q)) return false;	*data = Q->queue[Q->front];		return true;}//查看queue on  elements  count;bool queueLength(Queue_t *Q, int *length) {	if (!Q || !length) return false;	*length = Q->rear - Q->front;	return true;}//打印队列中的元素void queuePrint(Queue_t *Q) {	if (!Q)  return;	if (isEmpty(Q)) {		cout << "queue is empty!" << endl;		return;	}	int p = 0;	p = (Q->front);	for (; p < Q->rear; p++) {		cout << Q->queue[p] <<" ";	}	cout << endl;	}//销毁队列void  queueDelete(Queue_t *Q) {	if (!Q)return;	Q->rear = Q->front = 0;	delete Q;}int main(void) {	Queue_t *Queue = NULL;		Queue = new Queue_t;	DataType_t data = -1;	int length = -1;	if (queueInit(Queue)) {		cout << "init is a empty queue!" << endl;	}	else {		exit(1);	}	for (int i = 0; i < 10; i++) {		if (queueEntry(Queue, &i)) {			cout << "entry is succeend" << endl;		}		else {			cout << "entry is fail!" << endl;		}	}		if (queueLength(Queue, &length)) {		cout << "queue on elements is:" << length << endl;	}	if (queueLook(Queue, &data)) {		cout << "queue first  elements is:"<< data << endl;	}	else {		cout << "look fail" << endl;	}	queuePrint(Queue);	for (int i = 0; i < 10; i++) {		if (queueRemove2(Queue, &data)) {			cout << "remove first elements succeend, remove elements is:" << data << endl;		}		else {			cout << "remove first elements fail!" << endl;		}	}	queuePrint(Queue);	queueDelete(Queue);	return 0;}

我这蹩脚的英文怎么样😂😂 出队时,方式一:是牺牲了时间来换取空间,方式二:是用空间来换取时间。

三、用链式存储

队列的链式存储结构，就是线性表的单链表，只不过它只能使用尾插入，只能在头部删除我们把它简称为链队列。队头指针指向链队列的头结点，而队尾指针指向终端节点，length代表队列的元素个数

#include 
   
    using namespace std;#define MAX_SIZE 5//最大存储typedef int DataType_t;//队列中的数据类型typedef struct Node {//节点结构	DataType_t data;//数据域	struct Node *next;//指针域}node_t;typedef node_t* pNode_t;//pNode_t 代表节点的指针类型typedef struct {	int length; //队列长度	pNode_t front;//指向第一个队列的元素的指针	pNode_t rear;//指向队列尾部的指针}Queue_t;//初始化队列bool queueInit(Queue_t *Q) {	if (!Q) return false;	Q->rear = Q->front = NULL;	Q->length = 0;	return true;}//判断队列是否为空bool isEmpty(Queue_t *Q) {	if (!Q) return false;	if (!Q->front) {		cout << "queue is empty!" << endl;		return true;	}	return false;}//判断队列已满bool isFull(Queue_t *Q) {	if (!Q) return false;	if (Q->length == MAX_SIZE) {		cout << "queue is full" << endl;		return true;	}	return false;}//入队bool queueEntry(Queue_t *Q, DataType_t *data) {	if (!Q || !data) return false;	if (isFull(Q)) return false;	pNode_t tmp;	tmp = new node_t;	tmp->data = *data;	tmp->next = NULL;	if (isEmpty(Q)) { //如果队列为空时二个指针同时指向这个节点		Q->rear = Q->front = tmp;	}	else {//这个队尾的指针的下一个节点指向新的节点 		Q->rear->next = tmp;		Q->rear = tmp;//队尾的指针指向新的节点	}	Q->length++;	return true;}//出队bool queueRemove(Queue_t *Q, DataType_t *data) {	if (!Q || !Q->front) return false;	if (!data) return false;	pNode_t tmp;	*data = Q->front->data;//把对头的元素赋值给data;	tmp = Q->front;//让临时节点指向第一个节点	Q->front = tmp->next;//第一个节点指向临时节点(原第一个节点)的下一个节点	if (!Q->front) Q->rear = NULL;	delete tmp;//删除原第一个节点的位置	Q->length--;	return true;}//查看第一个元素bool queueLook(Queue_t *Q, DataType_t *data){	if (!Q || !Q->front) return false;	if (!data) return false;	*data = Q->front->data;	return true;}//打印void queuePrint(Queue_t *Q) {	if (!Q ) return ;	if (Q->length < 0) {		cout << " 空队列" << endl;		return;	}		pNode_t p;	p = Q->front;	while (p) {		cout << p->data << " ";		p = p->next;    }	cout << endl;}void queueDelete(Queue_t* Q) {	if (!Q) return;	pNode_t tmp;	tmp = Q->front;	while(Q->front) {		cout << " clear data:" << Q->front->data << endl;		tmp = Q->front->next;		delete Q->front;		 Q->front=tmp;	}}int main(void) {	Queue_t *q;	q = new Queue_t;	DataType_t tmp = -1;	if (queueInit(q)) {		cout << "init queue succeed!" << endl;	}	else {		cout << "init queue fail!" << endl;	}	for (DataType_t i = 0; i < 10; i++) {		if (queueEntry(q, &i)) {			cout << "entry queue succeed" << endl;		}		else {			cout << "entry queue fail" << endl;		}	}	if (queueRemove(q, &tmp)) {		cout << "remove queue on elements succeend,remove emlements is:" << tmp << endl;	}	else {		cout << "remove queue on elementd fail" << endl;	}	if (queueLook(q, &tmp)) {		cout << "Look queue on elements succeend,remove emlements is:" << tmp << endl;	}	else {		cout << "Look queue on elementd fail" << endl;	}	queuePrint(q);	//for (int i = 0; i < 10; i++) {	//	queueRemove(q, &tmp);	//}	//cout << "清空链表!" << endl;	queuePrint(q);	queueDelete(q);	delete q;	return 0;}

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

你可能感兴趣的文章

C++数据结构 队列

一、提要

二、使用顺序存储（数组）实现：

三、用链式存储

C++数据结构队列