• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

队列(顺序存储结构)

算法笔记 站点默认 2个月前 (10-04) 23次浏览 已收录 0个评论
文章目录[隐藏]

自己写的队列

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

//自己写的队列(数组实现)
//因为非循环队列太耗空间了,我就直接写循环队列,其实区别很小,要注意的就两点:
//利用求余操作就可以实现: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;
}

习题板块


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:队列(顺序存储结构)
喜欢 (5)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到