我所理解的队列
象栈一样，队列也是表。然而，使用队列时插入在一端进行而删除在另一端进行。 同样的，也有两种方法来实现队列，一种是用链表，一种是用数组。 先来看看用链表实现的队列。 我们把进行删除操作的一端叫队头（通常用链表的头结点表示），而进行插入操作的一端叫队尾， 通常用尾结点表示）。每当删除一个结点，头指针后移一位；反之，尾指针后移一位。所以用链表实现 队列的操作是很简单的，它的基本操作和链表的基本操作几乎完全相同。 实际上人们更喜欢用数组来实现队列。对于每一个队列数据结构，我们保留一个数组Queue[]以及 位置Front和Rear，他们位于表队列的两端。我们还要记录实际存在于队列中的元素的个数Size和 数组的最大容量Capacity，所有这些信息是作为一个结构的一部分。 数组实现的队列的一个特性就是可以循环使用数组的空间，只要Size小于Capacity（Front独占一个空间， 不放数据），就不会出现溢出。 //-----------用数组实现队列的存储结构------------- #define MinQueueSize 5 typedef struct QueueRecord{ ElemType *Array; int Capacity; int Front; int Rear; int Size; } *Queue; //-------------------用数组实现队列的基本操作------------------------ Queue InitQueue(void); //构造一个空队列 Queue MakeEmpty(Queue Q);//初始条件：队列Q非空。 操作结果：将队列Q重置为空队列。 int IsEmpty(Queue Q);//初始条件：队列Q已存在。 操作结果：判断队列Q是否为空队列。 int IsFull(Queue Q);//初始条件：队列Q已存在。 操作结果：判断队列Q是否为满队列。 int QueueLength(Queue Q);//初始条件：队列Q已存在。 操作结果：返回队列Q结点的个数。 ElemType GetFront(Queue Q);//初始条件：队列Q非空。 操作结果：返回队头元素的值 //初始条件：队列Q已存在。 操作结果：插入元素X为新的队尾元素 void EnQueue(Queue Q, ElemType X); ElemType GetRearAndDeQueue(Queue Q);//初始条件：队列Q非空。 操作结果：删除队列Q的队头元素, 并返回其值 //-------------------用数组实现队列的基本操作的算法实现------------------------ Queue InitQueue(int MaxElements)//构造一个空队列 { Queue Q; if(MaxElements < MinQueueSize) { Puts("Queue size is too small!"); return NULL; } Q = (Queue)malloc(sizeof(struct QueueRecord)); if(!Q) { printf("Out of space!"); return NULL; } Q->Array = (ElemType*)malloc(sizeof(ElemType)*MaxElements); if(!Q->Array) { printf("Out of space!"); return NULL; } Q->Capacity = MaxElements; return MakeEmpty(Q); } void DestroyQueue(Queue *Q)//初始条件：栈S已存在。 操作结果：销毁栈S。 { free(Q->Array); free(Q); } Queue MakeEmpty(Queue Q)//初始条件：队列Q非空。 操作结果：将队列Q重置为空队列。 { Q->Size = 0; Q->Rear = Q->Front; return Q; } int IsEmpty(Queue Q)//初始条件：队列Q已存在。 操作结果：判断队列Q是否为空队列。 { return Q->Rear == Q->Front; // return Q->Size == 0; } int IsFull(Queue Q)//初始条件：栈S已存在。 操作结果：判断栈是否为空栈。 { return (Q->Rear - Q->Front == Capacity)||(Q->Rear + 1 == Q->Front); // return Q->Size == Q->Capacity-1; } int QueueLength(Queue Q)//初始条件：队列Q已存在。 操作结果：返回队列Q结点的个数。 { return Q->Size; } //初始条件：队列Q已存在。 操作结果：插入元素X为新的队尾元素 void EnQueue(Queue Q, ElemType X) { if(IsFull(Q)) Error("Full stack!"); else { if(Q->Rear > Q->Capacity-1) { Q->Rear = ++Q->Rear % Q->Capacity; Q->Array[Q->Rear] = X; } else Q->Array[++Q->Rear] = X; } } ElemType DeQueue(Queue Q)//初始条件：队列Q非空。 操作结果：删除队列Q的队头元素 { if(Q->Front > Q->Capacity-1) //如果到数组的顶，则返回数组底，循环利用数组空间 Q->Front = ++Q->Front % Q->Capacity; else ++Q->Front; } ElemType GetFront(Queue Q)//初始条件：队列Q非空。 操作结果：返回队头元素的值 { return Q->Array[Q->Front+1]; } ElemType GetRearAndDeQueue(Queue Q)//初始条件：队列Q非空。 操作结果：删除队列Q的队头元素, 并返回其值 { ElemType X = GetFront(Q); DeQueue(Q); return X; } //---------------------------------------------------------------------------------
评论