队列
1.队列及其基本概念：
(1)队列的基本概念
队列(Queue)：是一种运算受限，先进先出(FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。
队首(front) ：允许进行删除的一端。
队尾(rear) ：允许进行插入的一端。
队列中没有元素时称为空队列。
队列的修改是依先进先出的原则进行的，不允许数据项直接插入队列中，也不允许从中间移除数据项。
(2)队列的抽象数据类型定义：
ADT Queue{
数据对象：D ={ ai|ai∈ElemSet, i=1, 2, …, n, n >= 0 }
数据关系：R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n }
约定a1端为队首，an端为队尾。
基本操作：
Create()：创建一个空队列；
EmptyQue()：若队列为空，则返回true ，否则返回flase ；
InsertQue(x) ：向队尾插入元素x；
DeleteQue(x) ：删除队首元素x；
} ADT Queue
2.队列的顺序表示和实现：
利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元素，称为顺序队列。
对于队列，和顺序栈相类似，也有动态和静态之分。
静态顺序队列类型定义如下：
#define MAX_QUEUE_SIZE 100
typedef struct queue
{
ElemType Queue_array[MAX_QUEUE_SIZE];
int front; //队首（删除数据）
int rear; //队尾（插入数据）
}SqQueue- 队列的顺序存储结构
设立一个队首指针front ，一个队尾指针rear ，分别指向队首和队尾元素。
初始化：front=rear=0。
入队：将新元素插入rear所指的位置，然后rear加1。
出队：删去front所指的元素，然后加1并返回被删元素。
队列为空：front=rear。
队满：rear=MAX_QUEUE_SIZE-1
顺序队列中存在“假溢出”现象
- 循环队列
为充分利用向量空间，克服 “假溢出”现象，将为队列分配的向量空间看成为一个首尾相接的圆环，这种队列称为循环队列(Circular Queue)。
在循环队列中进行出队、入队操作时，队首、队尾指针仍要加1，朝前移动，当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1)时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：
if (i+1==MAX_QUEUE_SIZE)
{
i=0;
}
else
{
i++ ;
}其中： i代表队首指针(front)或队尾指针(rear)
循环队列为空：front=rear 。
循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。
循环队列的基本操作
a.循环队列的初始化
SqQueue Init_CirQueue(void)
{
SqQueue Q;
Q.front = Q.rear = 0;
return(Q);
}b.入队操作
Status Insert_CirQueue(SqQueue Q, ElemType e)
/* 将数据元素e插入到循环队列Q的队尾 */
{
if ((Q.rear + 1) % MAX_QUEUE_SIZE == Q.front)
{
return ERROR; /* 队满，返回错误标志 */
}
Q.Queue_array[Q.rear] = e; /* 元素e入队 */
Q.rear = (Q.rear + 1) % MAX_QUEUE_SIZE; /* 队尾指针向前移动 */
return OK; /* 入队成功 */
}c.出队操作
Status Delete_CirQueue(SqQueue Q, ElemType* x)
/* 将循环队列Q的队首元素出队 */
{
if (Q.front + 1 == Q.rear)
{
return ERROR; /* 队空，返回错误标志 */
}
*x = Q.Queue_array[Q.front]; /* 取队首元素 */
Q.front = (Q.front + 1) % MAX_QUEUE_SIZE;/* 队首指针向前移动 */
return OK;
}3.队列的链式表示和实现：
(1)队列的链式存储表示
队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表.
需要两类不同的结点：数据元素结点，队列的队首指针和队尾指针的结点
数据元素结点类型定义：
typedef struct Qnode
{
ElemType data ;
struct Qnode *next ;
}QNode ;指针结点类型定义：
typedef struct link_queue
{
QNode *front , *rear ;
}Link_Queue ;(2)链队列运算及指针变化
链队列的操作实际上是单链表的操作，只不过是删除在表头进行，插入在表尾进行。插入、删除时分别修改不同的指针。
(3)链队列的基本操作
a.链队列的初始化
LinkQueue * Init_LinkQueue(void)
{
LinkQueue* Q;
QNode* p;
p = (QNode*)malloc(sizeof(QNode)); /* 开辟头结点 */
p->next = NULL;
Q = (LinkQueue*)malloc(sizeof(LinkQueue));
/* 开辟链队的指针结点 */
Q->front = Q->rear = p;
return(Q);
}b.链队列的入队操作
在已知队列的队尾插入一个元素e ，修改队尾指针(Q.rear)。
Status Insert_CirQueue(LinkQueue* Q, QNode* p ,ElemType e)
/* 将数据元素e插入到链队列Q的队尾 */
{
p = (QNode*)malloc(sizeof(QNode));
if (!p) return ERROR;
/* 申请新结点失败，返回错误标志 */
p->data = e; p->next = NULL; /* 形成新结点 */
Q->rear->next = p;
Q->rear = p; /* 新结点插入到队尾 */
return OK;
}c.链队列的出队操作
Status Delete_LinkQueue(LinkQueue* Q, ElemType* x)
{
QNode* p;
if (Q->front == Q->rear) return ERROR; /* 队空 */
p = Q->front->next; /* 取队首结点 */
*x = p->data;
Q->front->next = p->next; /* 修改队首指针 */
if (p == Q->rear) Q->rear = Q->front;
/* 当队列只有一个结点时应防止丢失队尾指针 */
free(p);
return OK;
}d.链队列的撤消
void Destroy_LinkQueue(LinkQueue* Q)
/* 将链队列Q的队首元素出队 */
{
while (Q->front != NULL)
{
Q->rear = Q->front->next;
/* 令尾指针指向队列的第一个结点 */
free(Q->front); /* 每次释放一个结点 */
/* 第一次是头结点，以后是元素结点 */
Q->front = Q->rear;
}
}
Comments NOTHING