队列

队列

队列的顺序存储解构

队列的顺序存储

队列的顺序存储类型可描述为

#define MaxSize 50						//定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];				//存放队列元素
    int front,rear;						//队头指针和队尾指针
}SqQueue;

循环队列的操作

(1)初始化

void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;					//初始化队首、队尾指针
}

(2)判队空

bool isEmpty(SqQueue Q){
    if(Q.rear == Q.front) return true;		//队空条件
    else return false;
}

(3)入队

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front)    return false;		//队满则报错
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;								//队尾指针加1取模
    return true;
}

(4)出队

bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear == Q.front)			return false; 			//队列空则报错
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;							//队头指针加1取模
    return true;
}

循环队列的完整操作

程序源代码：

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
#define MaxSize 50						//定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];				//存放队列元素
    int front,rear;						//队头指针和队尾指针
}SqQueue;
void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;					//初始化队首、队尾指针
}
bool isEmpty(SqQueue Q){
    if(Q.rear == Q.front) return true;		//队空条件
    else return false;
}
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front)    return false;		//队满则报错
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;								//队尾指针加1取模
    return true;
}
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear == Q.front)			return false; 			//队列空则报错
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;							//队头指针加1取模
    return true;
}
void PrintSqQueue(SqQueue Q){								//遍历操作 
	int point = Q.front;
	while(point!=Q.rear)									//如果point指向Q.rear说明遍历结束 
	{														//也就是point指向了队尾元素的下一个位置 
		cout<<Q.data[point]<<" ";
		point=(point+1)%MaxSize;
	}
	cout<<endl;
}
int main(){
	SqQueue Q;												//声明了一个顺序队列 
	InitQueue(Q);											//初始化这个队列 
	for(int i=0;i<5;i++)
	{
		EnQueue(Q,i);										//入队操作 
	}
	PrintSqQueue(Q);										//遍历 
	for(int i=1;i<=5;i++)
	{
		int x;
		DeQueue(Q,x);										//出队 
		cout<<"这是第"<<i<<"次出队"<<"出队的元素是" <<x<<endl;
		if(!isEmpty(Q))										//队列非空则遍历 
		{	
			cout<<"当前队列为：";
			PrintSqQueue(Q);
		}else{
			cout<<"此时的队列为空队列"<<endl;
		}
		
	} 
	return 0;
} 

程序输出：

0 1 2 3 4
这是第1次出队出队的元素是0
当前队列为：1 2 3 4
这是第2次出队出队的元素是1
当前队列为：2 3 4
这是第3次出队出队的元素是2
当前队列为：3 4
这是第4次出队出队的元素是3
当前队列为：4
这是第5次出队出队的元素是4
此时的队列为空队列

队列的链式存储结构

队列的链式存储

队列的链式存储类型可描述为

typedef struct LinkNode{								//链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{											//链式队列	
    LinkNode *front,*rear;								//队列的对头和队尾指针
}LinkQueue;

链式队列的基本操作

(1)初始化

void InitQueue(LinkQueue &Q){
    Q.front = Q.rear=(LinkNode*)malloc(sizeof(LinkNode));		//建立头结点
    Q.front->next=NULL;					//初始为空
}

(2判队空

bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)			return true;
    else return false;
}

(3)入队

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s =(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;											//创建新结点，插入到链尾
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

(4)出队

bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front == Q.rear)	return false;		//空队
    LinkNode *p =Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p){
        Q.rear = Q.front;						//若原队列中只有一个结点，删除后变空
    }
    free(p);
    return true;
}

链式队列的完整操作

程序源代码：

#include<bits/stdc++.h>
using namespace std; 
typedef struct LinkNode{								//链式队列结点
    int data;
    struct LinkNode *next;
}LinkNode;
typedef struct{											//链式队列	
    LinkNode *front,*rear;								//队列的对头和队尾指针
}LinkQueue;
void InitQueue(LinkQueue &Q){
    Q.front = Q.rear=(LinkNode*)malloc(sizeof(LinkNode));		//建立头结点
    Q.front->next=NULL;					//初始为空
}
bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)			return true;
    else return false;
}
void EnQueue(LinkQueue &Q,int x){
    LinkNode *s =(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;											//创建新结点，插入到链尾
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}
bool DeQueue(LinkQueue &Q,int &x){
    if(Q.front == Q.rear)	return false;		//空队
    LinkNode *p =Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p){
        Q.rear = Q.front;						//若原队列中只有一个结点，删除后变空
    }
    free(p);
    return true;
}
void PrintQueue(LinkQueue Q)					//遍历队列 
{
	LinkNode *tmp=Q.front->next;				//声明一个结点用于遍历
	while(tmp!=NULL)							//如果这个结点为空则停止遍历
	{											//这里即tmp已经指向最后一个元素的->next
		cout<<tmp->data<<" ";					//因为在初始化时已经置最后一个元素的->next=NULL
		tmp=tmp->next;							//所以说这里只需要判断tmp为空即可
	}
	cout<<endl;
	
}
int main()
{
	LinkQueue Q;				//声明链式一个队列 
	InitQueue(Q);				//初始化队列 
	for(int i=5;i>0;i--)     	//创建队列 
	{
		EnQueue(Q,i);
	}
	PrintQueue(Q);      		//遍历 
	for(int i=1;i<=5;i++)
	{
		int x;
		DeQueue(Q,x);										//出队 
		cout<<"这是第"<<i<<"次出队"<<"出队的元素是" <<x<<endl;
		if(!IsEmpty(Q))										//队列非空则遍历 
		{	
			cout<<"当前队列为：";
			PrintQueue(Q);
		}else{
			cout<<"此时的队列为空队列"<<endl;
		}
		
	}
	return 0;
}

程序输出：

5 4 3 2 1
这是第1次出队出队的元素是5
当前队列为：4 3 2 1
这是第2次出队出队的元素是4
当前队列为：3 2 1
这是第3次出队出队的元素是3
当前队列为：2 1
这是第4次出队出队的元素是2
当前队列为：1
这是第5次出队出队的元素是1
此时的队列为空队列