数据结构-007-队列、顺序队、循环队

队列的定义及其操作

队列的定义
队列是限定在一端进行插入，在另一端进行删除的线性表
队列中允许插入一端称为队尾。用rear指针指示队尾。队列中允许删除的一端称为队头。front指针指示队头。

在队尾插入元素的操作称为入队。在队头删除元素的操作称为出队。 是一种很重要的数据结构哦????????????????????????????????????????????????
特点：“先进先出”（First In First Out，缩写为FIFO。

1、顺序队定义

#define QUEUESIZE 100
typedef struct{	
	DataType items[QUEUESIZE];	
	int front,rear;
}SqQueue;

2、循环队

循环队列基本概念
把队列的首尾相连，形成一个环，即允许队列直接从数组中下标最大的位置前进到下标最小的位置。

逻辑环：
front=(front+1)% QUEUESIZE
rear=(rear+1) % QUEUESIZE

2.1 求循环队列的长度

int QueueLength(SqQueue Q){
	return(Q.rear-Q.front+QUEUESIZE)%QUEUESIZE;
}

2.2 入队

步骤：

1. 判断所给循环队列是否已满，若满则产生上溢出错误，算法结束。否则执行步骤（2）。
2. 将新元素插入队尾指针所指的位置。
3. 队尾指针增一，指向新的队尾位置。

int EnQueue(SqQueue *Q,DataType e){	
	if((Q->rear+1)%QUEUESIZE==Q->front){
			printf("队列已满，不能完成入队操作！\n");
			return 0;
	}
	Q->items[Q->rear]=e;
	Q->rear=(Q->rear+1)%QUEUESIZE;
	return 1;
} 

2.3 出队

操作步骤：
判断所给循环队列是否为空，若空则产生下溢出错误，算法结束。否则执行步骤（2）。
删除队头指针所指元素，并赋值给指定的变量。
队头指针增一，指向新的队头位置。

int DeQueue(SqQueue *Q,DataType *e){	
	if(Q->front==Q->rear){
		   printf("队列已空，不能完成出队操作！\n");
		   return 0;
	}	
	*e=Q->items[Q->front];
	Q->front=(Q->front+1)%QUEUESIZE;
	return 1;
}  

2.4 遍历队列

int TraverseQueue(SqQueue Q){	
	int pos;
	pos=Q.front;
	while((pos+1)%QUEUESIZE<=Q.rear){
		    printf("%d\t",Q.items[pos]);
		    pos++;
	}	
	printf("\n");
	return 1;
} 

【例3-9】利用两个堆栈模拟队列，并用栈的运算实现出队和入队操作，请设计入队和出队算法。
思路：用堆栈SIN和SOUT分别作为输入和输出。入队时，向SIN入栈元素模拟入队操作；出队时，则将SIN中元素全部入栈到SOUT中，再从SOUT中出栈元素，最后将SOUT中的元素全部入栈到SIN中。
（1）入队

int EnQueue(SqStack* SIN,DataType item){
	if(SIN->top>=STACKSIZE-1){
		 printf("队列已满，不能完成入队操作！\n");return 0;}
	Push(SIN,item);	
	return 1;}