队列（顺序存储结构）

废江_小江

发布于 2022-09-05 11:21:13

4450

发布于 2022-09-05 11:21:13

文章被收录于专栏：总栏目

自己写一个队列和教材上对比
习题板块

自己写的队列

这里我新加了一个打印函数，并且我只写了循环队列，教材有两种，一种是循环队列，一种是顺序队列，但是顺序队列实在太耗空间了，基本用不到，所以我就直接跳了

//自己写的队列（数组实现）
//因为非循环队列太耗空间了，我就直接写循环队列，其实区别很小，要注意的就两点：
//利用求余操作就可以实现：front=（front+1）%max   rear=（rear+1）%max
//例外需要注意的数组必须留一个空间，不能存满，为了方便判断队列满和队列空的情况 
//要写的操作有 ：   初始化队列 ：initqueue  ，  销毁队列： destroyqueue  ，  判断为空： emptyqueue
//  进队列 enqueue   ， 出队列  dequeueu   打印队列 printqueue 
#include<bits/stdc++.h>
#define maxsize 100
using namespace std;
typedef int elemtype;//之前不喜欢这样写，觉得太麻烦了，后来我想把int换成char去写字符串匹配的时候，就爱上了这样的写法 
typedef struct{
	elemtype data[maxsize];
	int front,rear;
}squeue;
void initqueue(squeue*&q){
	q=(squeue*)malloc(sizeof(squeue));
	q->front=q->rear=0;  
}
void destroyqueue(squeue*&q){
	free(q);
}
bool emptyqueue(squeue*q){
	return (q->front==q->rear);
}
bool enqueue(squeue*&q,elemtype e){
	if((q->rear+1)%maxsize==q->front)
	return false;
	q->rear=(q->rear+1)%maxsize;
	q->data[q->rear]=e;
	return true;
}
bool dequeue(squeue*&q,elemtype &e){
	if(q->rear==q->front)
	return false;
	q->front=(q->front+1)%maxsize;
	e=q->data[q->front];//因为队列中必须空一个数，空的数我们让front指向 
	return true;
}
void printqueue(squeue*q){
	int pre=q->front;
	while(pre!=q->rear){
		pre=(pre+1)%maxsize;
		cout<<q->data[pre]<<" ";
	}
	cout<<endl;
}
int main(){
	squeue *q;
	elemtype e;
	initqueue(q);
	for(elemtype i=1;i<=10;i++)
	enqueue(q,i);
	printqueue(q);
	enqueue(q,5);
	enqueue(q,7);
	printqueue(q);
	dequeue(q,e);
	dequeue(q,e);
	dequeue(q,e);
	printqueue(q);
}

教材标准队列（循环队列）

//顺序队列（环形队列）基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int front,rear;		//队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)
{
	free(q);
}
bool QueueEmpty(SqQueue *q)
{
	return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)
{	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
		return false;
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{	if (q->front==q->rear)		//队空下溢出
		return false;
	q->front=(q->front+1)%MaxSize;
	e=q->data[q->front];
	return true;
}

教材标准队列（顺序队列）

//顺序队列（非环形队列）基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int front,rear;						//队头和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=-1;
}
void DestroyQueue(SqQueue *&q)			//销毁队列
{
	free(q);
}
bool QueueEmpty(SqQueue *q)				//判断队列是否为空
{
	return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)	//进队
{	if (q->rear==MaxSize-1)				//队满上溢出
		return false;					//返回假
	q->rear++;							//队尾增1
	q->data[q->rear]=e;					//rear位置插入元素e
	return true;						//返回真
}
bool deQueue(SqQueue *&q,ElemType &e)	//出队
{	if (q->front==q->rear)				//队空下溢出
		return false;
	q->front++;
	e=q->data[q->front];
	return true;
}