【数据结构周周练】006队列基本操作-顺序结构及链式结构实现

本是古典何须时尚 2021-06-11 15:12 487阅读 0赞

今天给大家带来的是队列的基本操作的算法实现，以及相关代码的执行结果，包括初始化、入队、出队、销毁队、清空队、求队长、遍历队等等。把自己写的代码分享给大家，实现方式不唯一，如果大家有更好的算法，欢迎大家一起交流讨论，也欢迎大家在下面评论。

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

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

一、顺序循环队列实现

1、代码

2、执行结果

二、链队实现

1、代码

2、执行结果

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

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

### 1、代码 ###

#define MAXQSIZE 20
    
    #include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct {
    	int *base;
    	int front;
    	int rear;
    }SqQueue;
    
    int InitQueue(SqQueue &SQ) {
    	SQ.base = (int *)malloc(MAXQSIZE * sizeof(SqQueue));
    	if (!SQ.base)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	SQ.front = SQ.rear = 0;
    	return 1;
    }
    
    int EnQueue(SqQueue &SQ, int e) {
    	if ((SQ.rear + 1)%MAXQSIZE == SQ.front)
    	{
    		cout << "队列已满" << endl;
    		exit(OVERFLOW);
    	}
    	SQ.base[SQ.rear] = e;
    	SQ.rear = (SQ.rear + 1) % MAXQSIZE;
    	
    	return 1;
    }
    
    int DeQueue(SqQueue &SQ, int &e) {
    	if (SQ.rear == SQ.front)
    	{
    		cout << "队列已空" << endl;
    		return 0;
    	}
    	e = SQ.base[SQ.front];
    	SQ.front = (SQ.front + 1) % MAXQSIZE;
    	return 1;
    }
    
    int DestoryQueue(SqQueue &SQ) {
    	if (SQ.base)
    		free(SQ.base);
    	SQ.base = NULL;
    	SQ.front = SQ.rear = 0;
    	return 1;
    }
    
    int ClearQueue(SqQueue &SQ) {
    	SQ.front = SQ.rear = 0;
    	return 1;
    }
    
    int QueueEmpty(SqQueue SQ) {
    	return(SQ.front == SQ.rear);
    }
    
    int QueueLength(SqQueue SQ) {
    	
    	return (SQ.rear-SQ.front+MAXQSIZE)% MAXQSIZE;
    }
    
    int VisitQueue(SqQueue SQ) {
    	for (int i = 0; i < QueueLength(SQ); i++)
    	{
    		cout << SQ.base[(SQ.front + i) % MAXQSIZE];
    	}
    	cout << endl;
    	return 1;
    }
    
    void main() {
    
    	cout << "顺序结构实现队列操作" << endl;
    	SqQueue SQ;
    	InitQueue(SQ);
    	cout << "刚刚创建的队列长度为：" << QueueLength(SQ);
    	if (QueueEmpty(SQ))
    		cout << "，该队列是一个空队列。" << endl;
    	else
    		cout << "，该队列不是一个空队列。" << endl;
    	for (int i = 0; i < 10; i++)
    	{
    		EnQueue(SQ, i);
    	}
    	cout << "第一次入队的队列长度为：" << QueueLength(SQ) << endl;
    	cout << "第一次入队的队列内容为：";
    	VisitQueue(SQ);
    	cout << "出队4个元素为：";
    	int OutQueueElem;
    	for (int i = 0; i < 4; i++)
    	{
    
    		DeQueue(SQ, OutQueueElem);
    		cout << OutQueueElem << ",";
    
    	}
    	cout << "\n出队4个元素后队列内容为：";
    	VisitQueue(SQ);
    
    	ClearQueue(SQ);
    	cout << "清空队列后队列长度为：" << QueueLength(SQ) << endl;
    	DestoryQueue(SQ);
    
    }

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

![70][]

## 二、链队实现 ##

### 1、代码 ###

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct QNode {//定义队列结点
    	int data;
    	struct QNode *next;
    }QNode, *QueuePtr;
    
    typedef struct LinkQueue {//定义队列
    	QueuePtr front;
    	QueuePtr rear;
    }LinkQueue;
    
    int InitQueue(LinkQueue &LQ) {
    	LQ.front = LQ.rear = (QueuePtr)malloc(sizeof(QNode));//链队列初始化要初始化队头指针和队尾指针。
    	if (!LQ.front)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	LQ.front->next = NULL;//将队头指针的后继指向空，完成初始化。
    	return 1;
    
    }
    
    int EnQueue(LinkQueue &LQ, int e) {
    	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    	if (!p)
    	{
    		cout << "结点分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	p->data = e;
    	p->next = NULL;
    	LQ.rear->next = p;
    	LQ.rear = p;
    
    	return 1;
    }
    
    int DeQueue(LinkQueue &LQ, int &e) {
    	if (LQ.front == LQ.rear)
    	{
    		cout << "链表为空" << endl;
    		return 0;
    	}
    	QueuePtr p = LQ.front->next;
    	e = p->data;
    	LQ.front->next = p->next;
    	free(p);
    	return 1;
    }
    
    int DestoryQueue(LinkQueue &LQ) {
    	while (LQ.front)
    	{
    		LQ.rear = LQ.front->next;
    		free(LQ.front);
    		LQ.front = LQ.rear;
    	}
    	return 1;
    }
    
    int ClearQueue(LinkQueue &LQ) {
    	QueuePtr p ,q;
    	p = LQ.front->next;
    	LQ.rear = LQ.front;
    	LQ.front->next = NULL;
    	while (p)
    	{
    		q = p;
    		p = q->next;
    		free(q);
    	}
    	return 1;
    }
    
    int QueueEmpty(LinkQueue LQ) {
    	return(LQ.front == LQ.rear);
    }
    
    int QueueLength(LinkQueue LQ) {
    	QueuePtr p = LQ.front;
    	int length = 0;
    	while (p != LQ.rear)
    	{
    		p = p->next;
    		length++;
    	}
    	return length;
    }
    
    int VisitQueue(LinkQueue LQ) {
    	QueuePtr p = LQ.front->next;
    	while (p != LQ.rear->next)
    	{
    		
    		cout << p->data << ',';
    		p = p->next;
    	}
    	cout << endl;
    	return 1;
    }
    
    void main() {
    	cout << "链式结构实现队列操作" << endl;
    	LinkQueue LQ;
    	InitQueue(LQ);
    	cout << "刚刚创建的队列长度为：" << QueueLength(LQ);
    	if (QueueEmpty)
    		cout << "，该队列是一个空队列。" << endl;
    	else
    		cout << "，该队列不是一个空队列。" << endl;
    	for (int i = 0; i < 10; i++)
    	{
    		EnQueue(LQ, i);
    	}
    	cout << "第一次入队的队列长度为：" << QueueLength(LQ)<<endl;
    	cout << "第一次入队的队列内容为：";
    	VisitQueue(LQ);
    	cout << "出队4个元素为：";
    	int OutQueueElem;
    	for (int i = 0; i < 4; i++)
    	{
    		
    		DeQueue(LQ, OutQueueElem);
    		cout << OutQueueElem << ",";
    
    	}
    	cout << "\n出队4个元素后队列内容为：";
    	VisitQueue(LQ);
    
    	ClearQueue(LQ);
    	cout << "清空队列后队列长度为：" << QueueLength(LQ)<<endl;
    	DestoryQueue(LQ);
    
    }

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

![70 1][]

[70]: /images/20210516/22a00558f4794a25b28008b4f63450cc.png
[70 1]: /images/20210516/1a684c475d524863b3d4f2b6a0297991.png