循环队列和链队列的表示和实现_栈和队列实现循环队列队列中元素类型elemtype为char

目录

一.队列的定义和特点

 二.队列的表示和实现

1.循环队列的表示和实现

1.1循环队列的表示

1.2循环队列的初始化

1.3求队列长度

1.4入队

1.5出队

1.6取队头元素

1.7遍历循环队列（从队头开始）

1.8完整代码

2.链队的表示和实现

2.1链队的表示

2.2初始化链队

 2.3入队

2.4出队

2.5取队头元素

2.6遍历链队

2.7完整代码

---

一.队列的定义和特点

和栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入（一般称队尾），而在另一端删除元素（一般称队头）。可以将队列类比成一个只允许一个人同时通过的隧道，只有前面的人走出后，后面的人才能通过。

 

 注意Q.rear指向的空间是没有元素的。

 二.队列的表示和实现

1.循环队列的表示和实现

1.1循环队列的表示

和顺序栈类似，在队列的存储结构中，用一组地址连续的单元依次存放队列元素。设队头指针front和队尾指针rear来分别指示队头和队尾元素。

#define MAXSIZE 100
#define ERROR -1
#define OK 1
#define OVERFLOW 0
#define ElemType char
typedef struct 
{
	ElemType *base;
	int front;
	int rear;
}SqQueue;

因为顺序表结构本身的局限性，会出现空间浪费或溢出的情况。为了解决这一问题，我们采用循环队列的方式。同时为了区分队满和队空的条件，规定少用一个空间，即队列有N个空间时，有N-1个元素就认为队满。

1.2循环队列的初始化

int InitQueue(SqQueue &Q){
	Q.base=new ElemType[MAXSIZE];
	if(!Q.base) exit(OVERFLOW);
	Q.front=0;
	Q.rear=0;
	return OK;
}

循环队列的初始化与普通队列一样，仅需分配一组连续的存储空间，并将队头队尾指针置为0。

1.3求队列长度

int QueueLength(SqQueue Q)
{
	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

因为循环队列可能会出现Q.rear<Q.front的情况，所以不能像普通队列那样直接返回Q.rear-Q.front。而是加上MAXSIZE再取模。同下面的代码：

int QueueLength(SqQueue Q)
{
	if(Q.rear>=Q.front) return Q.rear-Q.front;
	else return Q.rear-Q.front+MAXSIZE;
}

1.4入队

int EnQueue(SqQueue &Q,ElemType e){
	if((Q.rear+1)%MAXSIZE==Q.front) return ERROR;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXSIZE;
	return OK;
}

入队仅需将元素存进Q.rear指向的空间后，将队尾指针加一，如果超出MAXSIZE则模MAXSIZE。注意要先判断队列是否已满，队满的条件是(Q.rear+1)%MAXSIZE==Q.front。

1.5出队

int DeQueue(SqQueue &Q,ElemType &e){
	if(Q.rear==Q.front) return ERROR;
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXSIZE;
	return 0;
}

出队列的操作与入队列相似，区别在于修改的指针为Q.front。注意要先判断队列是否为空，队空的条件是Q.rear==Q.front。

1.6取队头元素

ElemType GetHead(SqQueue &Q){
	if(Q.rear!=Q.front) 
	return Q.base[Q.front];
}

1.7遍历循环队列（从队头开始）

void Traverse(SqQueue Q){
	while(Q.front!=Q.rear){
		cout<<Q.base[Q.front]<<"\n";
		Q.front=(Q.front+1)%MAXSIZE;
	}
}

1.8完整代码

#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR -1
#define OVERFLOW 0
#define Status int 
#define ElemType char
typedef struct{
	ElemType *base;
	int front;
	int rear;
}SqQueue;
Status InitQueue(SqQueue &Q);
Status EnQueue(SqQueue &Q,ElemType e);
Status DeQueue(SqQueue &Q,ElemType &e);
ElemType GetHead(SqQueue Q);
void Traverse(SqQueue Q);
int main(){
	int n;
	ElemType e;
	SqQueue Q;
	InitQueue(Q);
	cout<<"请输入入队列的元素个数：";
	cin>>n;
	cout<<"请输入入队列元素："<<"\n"; 
	while(n--){
		cin>>e;
		EnQueue(Q,e);
	}
	Traverse(Q);
	return 0; 
}
Status InitQueue(SqQueue &Q){
	Q.base=new ElemType[MAXSIZE];
	if(!Q.base) exit(OVERFLOW);
	Q.front=0;
	Q.rear=0;
	return OK;
}
Status EnQueue(SqQueue &Q,ElemType e){
	if((Q.rear+1)%MAXSIZE==Q.front) return ERROR;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXSIZE;
	return OK;
}
Status DeQueue(SqQueue &Q,ElemType &e){
	if(Q.rear==Q.front) return ERROR;
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXSIZE;
	return 0;
}
ElemType GetHead(SqQueue &Q){
	if(Q.rear!=Q.front) 
	return Q.base[Q.front];
}
void Traverse(SqQueue Q){
	while(Q.front!=Q.rear){
		cout<<Q.base[Q.front]<<"\n";
		Q.front=(Q.front+1)%MAXSIZE;
	}
}

2.链队的表示和实现

2.1链队的表示

同带有头指针和尾指针的链表。

#define ERROR -1
#define OK 1
#define OVERFLOW 0
#define ElemType char
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{
	LinkNode *front;
	LinkNode *rear;
}LinkQueue;

2.2初始化链队

初始化链队就是就是构造一个带有头结点的空队。

int InitQueue(LinkQueue &Q){
	Q.front=Q.rear=new LinkNode;
	Q.front->next=NULL;
	return OK;
}

 2.3入队

int EnQueue(LinkQueue &Q,ElemType e){
	LinkNode *p=new LinkNode;
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

2.4出队

int DeQueue(LinkQueue &Q,ElemType &e){
	LinkNode *p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p) Q.front=Q.rear;
	delete p;
	return OK;
}

注意不能直接释放p，如果出队的是队列中的最后一个元素时，由于p=Q.front->next，此时p会指向Q.rear的位置，直接delete p会丢失Q.rear。

2.5取队头元素

ElemType GetFront(LinkQueue Q){
	if(Q.front!=Q.rear)
	return Q.front->next->data;
}

2.6遍历链队

void Traverse(LinkQueue Q){
    //链队不为空
	if(Q.front->next){
			cout<<"队列的遍历结果为："<<endl; 
	LinkNode *p=Q.front->next;
	while(p){
		cout<<p->data<<endl;
		p=p->next;
	}
	}
}

2.7完整代码

#include<iostream>
using namespace std;
#define ERROR -1
#define OK 1
#define OVERFLOW 0
#define Status int 
#define ElemType char
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{
	LinkNode *front;
	LinkNode *rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q);
Status EnQueue(LinkQueue &Q,ElemType e);
Status DeQueue(LinkQueue &Q,ElemType &e);
ElemType GetFront(LinkQueue Q);
void Traverse(LinkQueue Q);
int main(){
	LinkQueue Q;
	InitQueue(Q);
	ElemType e;
	int n;
	cout<<"请输入入队元素个数：";
	cin>>n;
	while(n--){
		cin>>e;
		EnQueue(Q,e);
	}
	Traverse(Q);
	//cout<<GetFront(Q);
	return 0;
}
Status InitQueue(LinkQueue &Q){
	Q.front=Q.rear=new LinkNode;
	Q.front->next=NULL;
	return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e){
	LinkNode *p=new LinkNode;
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e){
	LinkNode *p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p) Q.front=Q.rear;
	delete p;
	return OK;
}
ElemType GetFront(LinkQueue Q){
	if(Q.front!=Q.rear)
	return Q.front->next->data;
}
void Traverse(LinkQueue Q){
	if(Q.front->next){
			cout<<"队列的遍历结果为："<<endl; 
	LinkNode *p=Q.front->next;
	while(p){
		cout<<p->data<<endl;
		p=p->next;
	}
	}
}