2.6 队列的顺序存储

2.6.1 序队列的定义

顺序队列：队列的顺序存储。

2.6.2 顺序队列的实现方式

实现方式：静态分配和动态分配

注：这两种方式：只是类型描述和初始化不一样，判空、入队、出队、取队头操作都一样

2.6.3 顺序队列上的操作

以循环队列为主

静态分配的顺序队列：类型描述和初始化

#define MaxSize 10
typedef struct{
	Elemtype data[MaxSize];//静态数组存放队列中元素
	Elemtype front,rear;        //队列顶指针
}SqQueue;

//初始化一个队列
void InitStack(SqQueue &Q){
	Q.rear = Q.front = 0;   //初始化队列顶指针
}

动态分配的顺序队列：类型描述和初始化

typedef struct{
	Elemtype *base;             //静态数组存放队列中元素
	Elemtype front,rear;        //队列顶指针
}SqQueue;

//初始化一个队列
bool InitQueue(SqQueue &Q){
	Q.base=(Elemtype *)malloc(MAXQSIZE*sizeof(Elemtype));
	if(!Q.Base) return false;
	Q.front = Q.rear = 0;
	return true;
}

判队列空

//判空
bool StackEmpty(SqStack S){
    if(Q.rear == Q.front){  //队列已空
        return true;
    }else{
        return false;
    }
}

入队（循环队列）

//入队
bool EnQueue(SqQueue &Q,Elemtype e){
	if((Q.rear+1)%MAXSIZE == Q.front) return false;  //队列已满
	Q.data[Q.rear] = e;				//e为队尾元素
    Q.rear = (Q.rear + 1)%MaxSize;  //队尾指针后移
	return true;
}

出队（循环队列）

//出队
bool DeQueue(SqQueue &Q,Elemtype &e){
	if(Q.rear == Q.front) return false;
	e = Q.data[Q.front];            //e为队头元素
    Q.front=(Q.front+1)%MAXQSIZE;	//队头指针后移
    return true;
}

获取队头元素

//获取队头元素
bool GetHead(SqQueue &Q,Elemtype &e){
	if(Q.rear == Q.front) return false;
	e = Q.data[Q.front];   //e为队列顶元素
    return true;
}

队列已空/已满

方案一：

#define MaxSize 10
typedef struct{
	Elemtype data[MaxSize];//静态数组存放队列中元素
	int front,rear;        //队列顶指针
}SqQueue;

已空：Q.rear == Q.front 已满：(Q.rear+1)%MAXSIZE == Q.front

方案二：

#define MaxSize 10
typedef struct{
	Elemtype data[MaxSize];//静态数组存放队列中元素
	int front,rear;        //队列顶指针
    int size;              //队列当前长度
}SqQueue;

已空：size == 0 已满：size == MAXSIZE

方案三：

#define MaxSize 10
typedef struct{
	Elemtype data[MaxSize];//静态数组存放队列中元素
	int front,rear;        //队列顶指针
    int tag;              //记录最近是删除还是插入，0是删除，1是插入
}SqQueue;

已空：Q.rear == Q.front && tag = 0 已满：Q.rear == Q.front && tag = 1

元素的个数

(Q.rear+MAXSIZE-Q.front)%MAXSIZE == Q.front