[数据结构与算法]数据结构第三章---队列（顺序实现）

1.队列的初始化操作

#define MaxSize 10    //定义队列中元素最大个数
typedef struct{
ElemType data[MaxSize];//用静态数组存放队列元素
int front,rear;//队头指针和队尾指针
}SqQuene;
//初始化队列
void InitQueue(SqQuene &Q){
    //初始时 队头、队尾指针指向0
    Q.rear = Q.front = 0;
}

void testQueue(){
    //声明一个队列（顺序存储）
    SqQuene Q;
    InitQueue(Q);
    //...后续操作
}
//判断队列是否为空
bool QueueEmpty(SqQuene Q){
    if(Q.rear==Q.front)//队空条件
        return true;
    else
        return false;
}

2.入队操作

【1】

循环队列：用“模”运算将存储空间在逻辑上变成了“环状”
队列已满的条件：队尾指针的再下一个位置是队头，即((Q.rear+1)%MaxSize==Q.front)
代价：牺牲一个存储单元

//判断队列是否为空
bool QueueEmpty(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;//将x插入队尾
	Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模
	return true;
}

3.出队操作

出队操作 只能让队头元素出队
//出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue &Q,ElemType &x){
	if(Q.rear==Q.front)
		return false;//队空则报错
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;//队头指针后移
	return true;
}
//获得队头元素的值，用x返回
bool GetHead(SqQueue Q,ElemType &x){
	if(Q.rear==Q.front)
		return false;//队空则报错
	x=Q.data[Q.front];
	return true;
}

【方案一】判断队列已满/已空
队列元素的个数：(rear+MaxSize-front)%MaxSize
队列已满的条件：队尾指针的再下一个位置是队头，即((Q.rear+1)%MaxSize==Q.front)
队空条件：Q.rear==Q.front
缺点：会浪费一个存储空间

#define MaxSize 10    //定义队列中元素最大个数
typedef struct{
ElemType data[MaxSize];//用静态数组存放队列元素
int front,rear;//队头指针和队尾指针
}SqQuene;

【方案二】判断队列已满/已空
队列元素个数=size
队满条件：size==MaxSize
队空条件：size==0
初始化时：rear=front=0?? size=0
插入成功：size++
删除成功：size--

#define MaxSize 10    //定义队列中元素最大个数
typedef struct{
ElemType data[MaxSize];//用静态数组存放队列元素
int front,rear;//队头指针和队尾指针
int size;//队列当前长度
}SqQuene;

【方案三】判断队列已满/已空
队列元素个数=？？？
队满条件：front==rear&&tag==1
队空条件：front==rear&&tag==0
初始化时：rear=front=0?? tag=0
每次删除成功都令tag=0
每次插入成功都令tag=1
?

#define MaxSize 10    //定义队列中元素最大个数
typedef struct{
ElemType data[MaxSize];//用静态数组存放队列元素
int front,rear;//队头指针和队尾指针
int tag;//最近进行的是删除/插入
}SqQuene;