数据结构专题 | 先序非递归遍历二叉树

目录

一、队列的类型定义

二、顺序队列的表示和实现

2.1 初始化队列

2.2 入队

2.3 出队

2.4 判断循环队列是否为空

三、链队的表示和实现

3.1 链队的初始化 

3.2 判断队列为空

3.3 入队

3.4 出队

附：系列文章

---

一、队列的类型定义

队列是限定只能在表的两端分别进行插入或删除操作的线性表。在队列结构中，数据元素只能从一端（表尾）插入，从另一端（表头）删除。允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front）。当队列中没有包含数据元素时，称为空队。向一个队列插入新的元素称为入队，此时，插入的元素成为新的队尾元素；从队列中删除一个元素时，只能删除当前的队头元素，称为出队。基于队列的这种“先进先出”的结构特点，因而也称为先进先出线性表。

在实际生活中，有关队列的例子也很多。各种排队现象如排队买票、排队购物、排队上车等，处于队头的首先出队，而新来的总是排到队尾。队列的这种先进先出的特性也反映了现实生活中先来先服务的处理原则。

队列的表示和实现也可以采用顺序存储结构和链式存储结构加以描述，以下分别说明

二、顺序队列的表示和实现

采用顺序存储结构表示队列时，可以用 C语言中的一维数组进行描述。由于对于队列的操作只能在队头和队尾进行，因此，需要设置两个指针front和rear分别指示队头和队尾的位置，并可约定队尾指针rear指向当前队尾元素后的下一个位置，队头指针front指向当前的队头元素。顺序队列的表示形式如下：

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

（1）初始化队列。队尾指针和队头指针均指向下标为0的单元，令front=rear=0。

（2）入队操作。新元素将存放到当前队尾指针所指的单元，并使队尾指针rear增1，指示下一次插入的位置，则rear=rear+1。

（3） 出队操作。将当前队头指针所指单元的值返回，并将队头指针front增1即可，则front=front+1。

队列为空时，不能做出队操作，因此判断队列为空的条件是front==rear；经过多次插入和删除操作以后，队列的队尾指针和队头指针将逐步向后移动，最终出现当队尾指针已指向所定义空间中的最后单元时，即rear=MAXSIZE-1时，队列满，无法再入队。虽然此时队头指针所指位置之前可能存在若干单元空闲，却无法进行入队操作的问题。这种现象称为“假溢出”

可以借助两种方法解决顺序队列的“假溢出”问题 。一是采用“移动队列”的方法，即每当执行一次出队操作，则依次将队头和队尾指针向数组的起始位置移动，始终保持队头在数组的起始位置。这种方法的代价是产生大量的元素移动，显然不是一种好方法

更合理有效的解决方法是，将一维数组的最后一个单元和第一个单元连接起来构成循环数组，此时称为“循环队列”。当队尾指针已指向数组的最后时，在进行入队操作的过程中，可将队尾指针rear移至数组的起始位置，表示下一次入队操作时的队尾。队尾指针移动的方法是rear=(rear+1)%MAXSIZE，队头指针的移动也是一样front=(front+1)%MAXSIZE。

循环队列初始化空队时，front=rear=0；当队列经过多次出队入队操作后，会出现队头指针front和队尾指针rear再次指向同一单元的情况，此时有可能队列空也有可能队列满。为了区分队满和队空的情况，规定当队空时，front==rear；队满时，队尾指针指向队头指针的前一个位置即为队满（rear+1)%MAXSIZE==fron，实际循环队列队满时，所容纳的元素个数为MAXSIZE-1；通过空留一个存储单元的方式区分循环队列队满和队空的情况。下面详细说明循环队列的存储表示和基本操作的实现方法。

循环队列的顺序存储表示如下： 

#define MAXSIZE 100
typedef struct{
	ElemType *base;
	int front;
	int rear;
}SqQueue;

2.1 初始化队列

int InitQueue(SqQueue *Q){
	Q->base=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));
	if(!Q->base) return ERROR;
	Q->front=Q->rear=0;
	return OK;
}

2.2 入队

入队操作需要判断循环队列是否已满。当队列不满，新元素入队，修改队尾指针指向下一个存储单元。

int EnQueue(SqQueue *Q,ElemType e){
	if((Q->rear+1)%MAXSIZE==Q->front) return ERROR;
	Q->base[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXSIZE;
	return OK;
}

2.3 出队

出队操作需要判断循环队列是否为空。当队列不为空时，队头元素出队，修改队头指针指向下一个元素。

int DeQueue(SqQueue *Q,ElemType *e){
	if(Q->front==Q->rear) return ERROR;
	*e=Q->base[Q->front];
	Q->front=(Q->front+1)%MAXSIZE;
	return OK;
}

2.4 判断循环队列是否为空

int QueueEmpty(SqQueue *Q){
	if(Q->front==Q->rear){
		return OK;
	}else{
		return ERROR;
	}
}

三、链队的表示和实现

采用链式存储结构表示队列，称为链队。显然，利用与线性链表类似的方法可以容易实现链队结构，并分别设置队尾和队头指针指示链队的位置。在链队结构中增加一个附加的头结点，并使队头指针front指向它。此时，判断空队的标志是，链队的队尾指针rear和队头指针front均指向头结点。

链队的操作十分简单，只需要根据实际操作情况修改相应的队头指针或队尾指针的指向即可。链队的表示和实现形式如下：

typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct LinkQueue{
	LinkNode *front,*rear;
}LinkQueue;

在进行链队的删除（出栈）操作时，需要注意的是，如果删除的结点是当前队列的唯一结点时，除了队列的头结点的指针作相应修改外，队尾指针也必须重新赋值为队列的头结点，否则将导致队尾指针的丢失。

3.1 链队的初始化 

int InitQueue_L(LinkQueue *Q){
	LinkNode *p;
	p=(LinkNode *)malloc(sizeof(LinkNode));
	if(!p) return ERROR;
	p->next=NULL;
	Q->front=Q->rear=p;
	return OK;
}

3.2 判断队列为空

int EmptyQueue_L(LinkQueue *Q){
	if(Q->front==Q->rear) return OK;
	else return ERROR;
}

3.3 入队

int EnQueue_L(LinkQueue *Q,ElemType e){
	LinkNode *p;
	p=(LinkNode *)malloc(sizeof(LinkNode));
	if(!p) return ERROR;
	p->data=e;
	p->next=NULL;
	Q->rear->next=p;
	Q->rear=p;
	return OK;
}

3.4 出队

int DeQueue_L(LinkQueue *Q,ElemType *e){
	LinkNode *p;
	if(EmptyQueue_L(Q)){
		return ERROR;
	}
	p=Q->front->next;
	*e=p->data;
	if(Q->front->next==Q->rear){
		Q->front->next=NULL;
		Q->rear=Q->front;
	}else{
		Q->front->next=p->next;
	}
	free(p);
	return OK;
}

附：系列文章