循环队列三种实现方式的基本操作(王道标准)

牺牲一个存储空间来区分队空和队满

缺点： 有一个单元无法利用

1. 定义

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;
}SqQueue;

2. 初始化

void InitSqQueue(SqQueue &Q){Q.rear=Q.front=0;
}

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;return true;
}

4. 出队

bool DeQueue(SqQueue &Q,ElemType &x){if(Q.front==Q.rear)		//当队空return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;
}

5. 判断队列是否为空

bool QueueEmpty(SqQueue Q){if(Q.rear==Q.front)return true;return false;
}

6. 获得队头元素

bool GetHead(SqQueue Q,ElemType &x){if(Q.front==Q.rear)return false;x=Q.data[Q.front];return true;
}

设置size数据成员，表示队列当前长度

1. 定义

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;int size;
}SqQueue;

2. 初始化

void InitSqQueue(SqQueue &Q){Q.rear=Q.front=0;Q.size=0;
}

3. 入队

bool EnQueue(SqQueue &Q,ElemType x){if(Q.size==MaxSize)return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;Q.size++;
}

4. 出队

bool DeQueue(SqQueue &Q,ElemType &x){if(Q.Size==0)return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;Q.size--;return true;
}

5. 判断队列是否为空

bool QueueEmpty(SqQueue Q){if(Q.size==0)return true;return false;
}

6. 获得队头元素

bool GetHead(SqQueue Q,ElemType &x){if(Q.size==0)return false;x=Q.data[Q.front];return true;
}

设置tag数据成员

1. 定义

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;int tag;		//最近进行的是删除-0/插入-1
}SqQueue;

2. 初始化

void InitSqQueue(SqQueue &Q){Q.rear=Q.front=0;Q.tag=0;
}

3. 入队

bool EnQueue(SqQueue &Q,ElemType x){if(Q.front==Q.rear&&tag==1)		//若队满return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;Q.size++;
}

4. 出队

bool DeQueue(SqQueue &Q,ElemType &x){if(Q.front==Q.rear&&tag==0)		//若队空return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;Q.size--;return true;
}

5. 判断队列是否为空

bool QueueEmpty(SqQueue Q){if(Q.front==Q.rear&&tag==0)return true;return false;
}

6. 获得队头元素

bool GetHead(SqQueue Q,ElemType &x){if(Q.front==Q.rear&&tag==0)return false;x=Q.data[Q.front];return true;
}