@[TOC]

队列

逻辑结构：线性表
存储结构：顺序存储\链式存储
基本运算：
1. 初始化
2. 判断队空
3. 判断队满
4. 入队
5. 出队
6. 访问队头

注意：队列也是线性表，其特殊性在于有特殊的运算规则。即：队结构只能在一端进行插入，该操作端称为队尾，另一端删除元素，该操作端称为队头。按照“先进先出”（First In First Out,FIFO）原则处理数据节点。

1.循环队列

之所以用循环对列，就是了为了提高利用率。要不然每删除一个元素，对头就空了一个还用不了了。
实现循环，就用“模”运算：
队空的条件：Q.front == Q.rear
堆满条件：（Q.rear+1）%Max == Q.front

队列的定义

typedef int ElemType;

typedef struct{
	ElemType *base;
	int front;
	int rear;							//队头、尾 
}SqQueue;

初始化

void SqQueueInit(SqQueue &Q){			//初始化队列 
	Q.base=new ElemType[MAX];
	Q.front=Q.rear=0;
}

判断队空

bool SqQueueEmpty(SqQueue Q){			//判断队列空 
	if(Q.front==Q.rear){
		return true;
	}
	else return false;
}

判断队满

bool SqQueueFull(SqQueue Q){			//判断队列满 
	if((Q.rear+1)%MAX==Q.front){
		return true;
	}
	else return false;
}

回到目录

入队

SqQueue SqQueueIn(SqQueue Q,ElemType x){	//入队 
	if(SqQueueFull(Q)){
		cout<<"队满了"<<endl;
		return Q;
	}
	Q.base[Q.rear]=x;
	Q.rear=(Q.rear+1)%MAX;
	return Q;
}

出队

SqQueue SqQueueOut(SqQueue Q,ElemType *x){//出队 
	if(SqQueueEmpty(Q)){
		cout<<"队空"<<endl;
		return Q;
	}
	*x=Q.base[Q.front];
	Q.front=(Q.front+1)%MAX;
	return Q;
}

访问队头

1
2
3

ElemType GetSqQueueTop(SqQueue Q){			//访问队头元素 
	return (Q.base[Q.front]);
}

计算队列长度

1
2
3

int GetQueueLength(SqQueue Q){				//元素个数 
	return (Q.rear-Q.front+MAX)%MAX;
}

回到目录

总的代码:

#include<iostream>
#define MAX 100							//定义队列的最大值 
using namespace std;

typedef int ElemType;

typedef struct{
	ElemType *base;
	int front;
	int rear;							//队头、尾 
}SqQueue;

void SqQueueInit(SqQueue &Q){			//初始化队列 
	Q.base=new ElemType[MAX];
	if(!Q.base)
		exit(1);
	Q.front=Q.rear=0;
}

bool SqQueueEmpty(SqQueue Q){			//判断队列空 
	if(Q.front==Q.rear){
		return true;
	}
	else return false;
}

bool SqQueueFull(SqQueue Q){			//判断队列满 
	if((Q.rear+1)%MAX==Q.front){
		return true;
	}
	else return false;
}

SqQueue SqQueueIn(SqQueue Q,ElemType x){	//入队 
	if(SqQueueFull(Q)){
		cout<<"队满了"<<endl;
		return Q;
	}
	Q.base[Q.rear]=x;
	Q.rear=(Q.rear+1)%MAX;
	return Q;
}

ElemType GetSqQueueTop(SqQueue Q){			//获取队头元素 
	return (Q.base[Q.front]);
}

int GetQueueLength(SqQueue Q){				//元素个数 
	return (Q.rear-Q.front+MAX)%MAX;
}

SqQueue SqQueueOut(SqQueue Q,ElemType *x){	//出队 
	if(SqQueueEmpty(Q)){
		cout<<"队空"<<endl;
		return Q;
	}
	*x=Q.base[Q.front];
	Q.front=(Q.front+1)%MAX;
	return Q;
}

int main(){
	//测试 
	int a[5];
	cout<<"请输入5个整数构成一个队列" <<endl;
	for(int i=0;i<5;i++){
		cin>>a[i];
	} 
	SqQueue s;
	SqQueueInit(s);
	cout<<"现在将初始化一个队列！"<<endl;
	if(SqQueueEmpty(s)){
		cout<<"队空"<<endl;
	}
	else cout<<"队非空"<<endl;
	cout<<"现在将上面的元素入队"<<endl;
	for(int i=0;i<5;i++){
	 	s=SqQueueIn(s,a[i]);
	 }
	cout<<"现在将依次出队"<<endl;
	for(int i=0;i<5;i++){
	 	cout<<"对头元素"<<GetSqQueueTop(s)<<endl;
	 	cout<<"当前元素个数"<<GetQueueLength(s)<<endl<<endl;
	 	s=SqQueueOut(s,&s.front);
	 }	
	if(SqQueueEmpty(s)){
		cout<<"队空"<<endl;
			}  
		else cout<<"队非空"<<endl; 

	return 0; 
}

运行结果：

回到目录

2.链队

链队的定义

typedef int DATATYPE;

typedef struct QNode			//定义节点
{
    DATATYPE data;
    struct QNode * next;
    
}QNode,*Queue;

typedef struct					//定义一个链队 
{
    Queue front;  				//队头指针 
    Queue rear;					//队尾指针
    int count; 					//计数器 记录链队的元素个数
    
}LinkQueue;

初始化

void init(LinkQueue &Q)
{
    Q.front=Q.rear=new QNode;
    if(!Q.front) 
    	exit(1);
    Q.front->next=NULL;					//与单链表一样，为了方便，给队列添加了头结点 
    Q.count=0;							//初始化时长度为零
}

判断空

bool SqQueueEmpty(SqQueue Q){			//判断队列空 
	if(Q.front==Q.rear){
		return true;
	}
	else return false;
}

判断队满

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

回到目录

入队

void EnQueue(LinkQueue &Q,DATATYPE a)	//入队 
{
    Queue p=new QNode;
    if(!p)								//申请不成功
        exit(1);
    else
    {
        p->data=a;			
        p->next=NULL;					//将新节点的指针域清空 
        Q.rear->next=p;					//新节点挂在队尾上 
        Q.rear=p;						//更新新的队尾 
        Q.count++;
    }
}

出队

注意：当队列中最后一个元素被删时，队列尾指针也丢失了，因此需要对队尾指针从新赋值。

void DeQueue(LinkQueue &Q,DATATYPE &a)	//出队 
{
    if( IsEmpty(Q))
        cout<<"error!队空"<<endl;
    else
    {
    	Queue p;
        p =Q.front->next;				
        a=p->data;
		Q.front->next=p->next;
        Q.count--;
        if(Q.rear==p)
        	Q.rear=Q.front;		//最后一个，队尾指针指向头结点
        delete p;		
    }
}

访问队头

DATATYPE GetFront(LinkQueue Q)
{
    if(IsEmpty(Q))
        return 0;
    else
    {
        return Q.front->next->data;
    }
}

计算队列长度

int length(LinkQueue Q)
{
    return Q.count;
}

回到目录

总的代码:

#include<iostream>
using namespace std;

typedef int DATATYPE;

typedef struct QNode			//定义节点
{
    DATATYPE data;
    struct QNode * next;
    
}QNode,*Queue;

typedef struct					//定义一个链队 
{
    Queue front;  				//队头指针 
    Queue rear;					//队尾指针
    int count; 					//计数器 记录链队的元素个数
    
}LinkQueue;

void init(LinkQueue &Q);					//初始化
bool IsEmpty(LinkQueue Q);					//判断是否为空
void EnQueue(LinkQueue &Q,DATATYPE a);		//入队 
void DeQueue(LinkQueue &Q,DATATYPE &a);		//出栈
DATATYPE GetFront(LinkQueue Q);				//访问队头 
int length(LinkQueue Q);					//计算队列长度(元素个数) 

void init(LinkQueue &Q)
{
    Q.front=Q.rear=new QNode;
    if(!Q.front) 
    	exit(1);
    Q.front->next=NULL;					//与单链表一样，为了方便，给队列添加了头结点 
    Q.count=0;							//初始化时长度为零
}

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

void EnQueue(LinkQueue &Q,DATATYPE a)	//入队 
{
    Queue p=new QNode;
    if(!p)								//申请不成功
        exit(1);
    else
    {
        p->data=a;			
        p->next=NULL;					//将新节点的指针域清空 
        Q.rear->next=p;					//新节点挂在队尾上 
        Q.rear=p;						//更新新的队尾 
        Q.count++;
    }
}

void DeQueue(LinkQueue &Q,DATATYPE &a)	//出队 
{
    if( IsEmpty(Q))
        cout<<"error!队空"<<endl;
    else
    {
    	Queue p;
        p =Q.front->next;				//将即将出队的数据存在a中。不存也不影响出队操作 
        a=p->data;
		Q.front->next=p->next;
        Q.count--;
        if(Q.rear==p)
        	Q.rear=Q.front;
        delete p;		
    }
}

DATATYPE GetFront(LinkQueue Q)
{
    if(IsEmpty(Q))
        return 0;
    else
    {
        return Q.front->next->data;
    }
}

int length(LinkQueue Q)
{
    return Q.count;
}

int main()
{
    LinkQueue Q;
    init(Q);       			 // 初始化队列 
	for (int i=0; i<5; i++)
    {
    	EnQueue(Q,i); 
    }
    
    DATATYPE temp;	
    while(!IsEmpty(Q))
    {    
    	printf("队列长度为：%d\n",length(Q));
		printf("此时的队头为：%d\n",GetFront(Q));  
		DeQueue(Q,temp);
        printf("将%d出队\n",temp); 
        printf("\n");
    }
    return 0;
}

运行结果：

注意一个小细节：
在进行某些操作时，不管是栈还是队列还是其他，需要注意函数是设为 void 型还是有返回类型。如果是 void ，要想要改变参数，需要用 * 或 &，如果有返回就不需要了。

回到目录

songsong的垃圾堆

队列--循环队列与链队

队列

1.循环队列

队列的定义

初始化

判断队空

判断队满

入队

出队

访问队头

计算队列长度

总的代码:

运行结果：

2.链队

链队的定义

初始化

判断空

判断队满

入队

出队

访问队头

计算队列长度

总的代码:

运行结果：