大话数据结构-4.10 队列的定义 - 高飞网

4.10 队列的定义

2016-12-22 15:28:40.0

4.10 队列的定义

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

    队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。


4.11 队列的抽象数据类型

ADT 队列(Queue)
Data
	同线性表。元素具有相同的类型,相邻元素有前驱和后继关系
Operation
	InitQueue(*Q);		//初始化操作,建立一个空队列
	DesttroyQueue(*Q);	//若队列Q存在,则销毁它
	ClearQueue(*Q);		//将队列Q清空
	QueueEmpty(Q);		//若队列Q为空,返回true,否则返回false
	GetHead(Q,*e);		//若队列Q存在且非空,用e返回队列Q的队头元素。
	EnQueue(*Q,e);		//若队列Q存在,插入新元素e到队列Q中并成为队列尾元素
	DeQueue(*Q,e);		//删除队列Q中队头元素,并用e返回其值
	QueueLength(Q);		//返回队列Q的元素个数
endADT

4.12 循环队列

    与栈一样,队列也是一种特殊的线性表,因此也有两种存储方式:顺序存储方式和链式存储方式。

4.12.1 队列顺序存储的不足

    对于顺序队列,假设其有一个n个元素的数组,当添加元素的时候,直接在队尾添加一个元素,时间复杂度为O(1)。

    

    但当队列删除元素的时候,需要在队头进行,即下标为0的位置,那就意味着,队列中的所有元素都得向前移动,以保证队列的队头,也就是下标为0的位置不为空,此时的时间复杂度为O(n)。


    鉴于此,如果队头不需要一定在下标为0的位置,如下图:


    这样当在队头删除元素时,队头变为下一个位置的元素,为了避免当队头和队尾重合处理变得麻烦,引入两个指针front和rear,分别指向队头和队尾。当两者相等时,front等于rear,此队列不是还剩下一个元素,而是空队列。

    这样解决了删除队头元素导致的元素移动问题,但当队尾已经到达数组的最后时,会出现“假溢出”现象:

4.12.2 循环队列定义

    所以解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把这种头尾相接的顺序存储结构称为循环队列

    当然这会带来新的问题。前面说到,当front==rear时,表示队列为空,但现在是循环队列,当两者相等时,也有可能是队满的情况,解决办法有两种:

  1. 设置标识位,当两者相等,且flag=0时,为空队列;当flag=1时,为队满。
  2. 当队列为空时,就是front==rear,而队列满时,保留一个空单元。如下:

    这里重点讨论第二种方法,由于rear可能比front大,也可能比front小,所以尽管它们只相差一个位置时是满的情况,但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize,那么队满的条件(rear+1)%QueueSize == front。这里取模的目的就是为了整合rear与front相差一圈的情况。

    队长度的计算公式为:(rear-front+QueueSize)%QueueSize。因为当rear>front时,长度为rear-front;相反,当read<front时,长度分为两段,即QueueSize-front和0+rear,相加为rear-front+QueueSize。

    循环队列的顺序存储结构代码如下:

/* 循环 顺序队列 */

typedef int SQElemType;

typedef struct
{
	SQElemType data[MAXSIZE];
	int front;
	int rear;
}SqCirQueue;

初始化循环队列:

//初始化操作,建立一个空队列
Status InitQueue(SqCirQueue *Q)
{
	memset(Q,0,sizeof(SQElemType)*MAXSIZE);
	Q->front=0;
	Q->rear =0;
	return OK;
}	

循环队列求长度代码:

//返回队列Q的元素个数
int QueueLength(SqCirQueue Q)
{
	return (Q.rear - Q.front + MAXSIZE )%MAXSIZE;
}

循环队列的入队操作代码如下:

//若队列Q存在,插入新元素e到队列Q中并成为队列尾元素
Status EnQueue(SqCirQueue *Q,SQElemType e)
{
	if((Q->rear+1)%MAXSIZE==Q->front)
	{
		return ERROR;//队列已满	
	}
	Q->data[(Q->rear)%MAXSIZE] = e;
	Q->rear = (Q->rear +1)%MAXSIZE;
	return OK;
}

循环队列的办队代码:

//删除队列Q中队头元素,并用e返回其值
Status DeQueue(SqCirQueue *Q,SQElemType *e)
{
	if(QueueEmpty(*Q))
	{
		return ERROR;//队列已空	
	}
	*e = Q->data[Q->front];
	Q->data[Q->front] = 0;
	Q->front = (Q->front+1)%MAXSIZE;
	return OK;
}

4.13 队列的链式存储结构及实现

    队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已。简称为链队列。

    链队列的结构为:

typedef int Status;

#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef struct QNode	//结点结构
{
	LQElemType data;
	struct QNode *next;
}QNode,*QNodePtr;

typedef struct 
{
	QNodePtr front;	//头指针
	QNodePtr rear;//尾指针
}LinkedQueue;

    入队操作代码:

//若队列Q存在,插入新元素e到队列Q中并成为队列尾元素
Status EnQueue(LinkedQueue *Q,LQElemType e)
{
	QNodePtr s = (QNode *)malloc(sizeof(QNode));//初始化头结点
	s->data=e;
	s->next=NULL;
	Q->rear->next = s;//将当前尾结点的后继设为此新结点
	Q->rear=s;//移动尾指针指向头新结点
	return OK;
}

    出队代码:

//删除队列Q中队头元素,并用e返回其值
Status DeQueue(LinkedQueue *Q,LQElemType *e)
{
	if(QueueEmpty(*Q))
	{
		return ERROR;//队列已空	
	}
	*e = Q->front->next->data;
	Q->front = Q->front->next;
	return OK;
}