目录

队列的实现

顺序队列的几种溢出情况

队列的顺序存储结构

循环队列

循环队列初始化

求队列长度

入队

出队

取队头元素

链队列

链式存储结构

初始化

入队

出队

​

取队头元素

队列是一种先进先出的线性表，只允许在队尾插入，在队头删除元素。
队列也分为顺序队列和链队列

队列的实现

顺序队列的几种溢出情况

（1） "下溢"现象：当队列为空时，出队运算产生的溢出现象。“下溢”是正常现象。

（2）"真上溢"现象：当队列满时，进栈运算产生空间溢出的现象。“真上溢”是一种出错状态。是一种错误。

（3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，使被删元素的空间永远无法重新利用。不能做入队操作。这种现象称为"假上溢"现象。

队列的顺序存储结构

在队列的存储结构中，需要设置front和rear两个整形变量来分别指示队头元素和队尾元素（又称头指针和尾指针）。

typedef struct {
	QElemType *base;//初始化时动态分配存储空间
	int front;//头指针
	int rear;//尾指针
} SqQueue;

循环队列

当入队次数足够多时，我们会发现数据不能如队列了，但队列中还有剩余空间，这是由队列的特点决定的（可以称为假溢出）。所以引入了循环队列。

循环队列指的是队列的实现方式，用一个头尾相接的循环链表，或者逻辑上头尾相接的数组（读取最后一个元素的下一个元素时会跳转到第一个元素），将队列安置在其中，空间被循环使用。

循环队列初始化

1. 循环队列初始化也就是为队列分配一个预定义大小的存储空间。
2. 再让base指针指向首地址
3. 将rear和front指针置空

Status InitQueue(SqQueue &Q) {//构造一个空队列Q
	Q.base = new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXSIZE的数组空间
	if (!Q.base)
		exit(OVERFLOW); //存储分配失败
	Q.front = Q.rear = 0; //头指针和尾指针置为零，队列为空
	return OK;
}

求队列长度

1. 对于非循环队列，尾指针和头指针之差就是队列的长度
2. 对于循环队列，差值可能为负数，所以要进行求余运算

int QueueLength(SqQueue Q) {//返回Q的元素个数，即队列的长度
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

入队

入队，也就是在队尾插入新元素

1.  判断队列是否为栈满
2.  将新元素插入队尾
3.  队尾指针加一

Status EnQueue(SqQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素
	if ((Q.rear + 1) % MAXQSIZE == Q.front) //尾指针在循环意义上加1后等于头指针，表明队满
		return ERROR;
	Q.base[Q.rear] = e; //新元素插入队尾
	Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针加1
	return OK;
}

出队

出队，也就是删除队头元素

1. 判断队列是否空栈
2. 引入变量，暂时保存队头元素
3. 头指针加一

Status DeQueue(SqQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值
	if (Q.front == Q.rear)
		return ERROR; //队空
	e = Q.base[Q.front]; //保存队头元素
	Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
	return OK;
}

取队头元素

1. 判断非空
2. 取头元素

SElemType GetHead(SqQueue Q) {//返回Q的队头元素，不修改队头指针
	if (Q.front != Q.rear) //队列非空
		return Q.base[Q.front]; //返回队头元素的值，队头指针不变
}

链队列

一般，链队列采用单链表来表示。和之前一样，要设置两个指针表示队头元素和队尾元素，并让头指针始终指向头结点。

链式存储结构

typedef struct QNode {
	QElemType data;
	struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
} LinkQueue;

初始化

构造一个有头结点的空队列

1. 创建头结点
2. 让front和rear指向头结点
3. 头结点指针域置空

Status InitQueue(LinkQueue &Q) {//构造一个空队列Q
	Q.front = Q.rear = new QNode; //生成新结点作为头结点，队头和队尾指针指向此结点
	Q.front->next = NULL; //头结点的指针域置空
	return OK;
}

入队

链队列元素入队列时不需要判断队满

1. 为入队元素开辟存储空间
2. 将新结点插到表尾
3. 修改rear指针

Status EnQueue(LinkQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素
	QueuePtr p;
	p = new QNode; //为入队元素分配结点空间，用指针p指向
	p->data = e; //将新结点数据域置为e
	p->next = NULL;
	Q.rear->next = p; //将新结点插入到队尾
	Q.rear = p; //修改队尾指针
	return OK;
}

出队

需要判断是否空栈

Status DeQueue(LinkQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值 
	QueuePtr p;
	if (Q.front == Q.rear)
		return ERROR; //若队列空，则返回ERROR
	p = Q.front->next; //p指向队头元素
	e = p->data; //e保存队头元素的值
	Q.front->next = p->next; //修改头指针
	if (Q.rear == p)
		Q.rear = Q.front; //最后一个元素被删，队尾指针指向头结点
	delete p; //释放原队头元素的空间
	return OK;
}

取队头元素

SElemType GetHead(LinkQueue Q) {//返回Q的队头元素，不修改队头指针
	if (Q.front != Q.rear) //队列非空
		return Q.front->next->data; //返回队头元素的值，队头指针不变
}

最后

以上就是机智月光为你收集整理的数据结构（队列）队列的实现的全部内容，希望文章能够帮你解决数据结构（队列）队列的实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。