队列(C语言实现)

队列其实和栈一样,也是一种限定性线性表,只不过队列的操作顺序与栈不同,栈是后进先出,而队列是先进先出。
在队列中,允许插入的一端称为队尾。而允许删除的一端称为队头。

数据元素:可以是任意类型的数据,但必须属于同一个数据对象。
关系:队列中数据元素之间是线性关系。
基本操作:
(1)InitQueue(&Q):初始化操作。设置一个空队列。
(2)IsEmpty(Q):判空操作。若队列为空,则返回TRUE,否则返回FALSE。
(3)IsFull(Q):判满操作。若队列为满,则返回TRUE,否则返回FALSE。
(4)EnterQueue(&Q,x):进队操作。在队列Q的队尾插入x。操作成功,返回值为TRUE,否则返回值为FALSE。
(5)DeleteQueue(&Q,&x):出队操作。使队列Q的队头元素出队,并用x带回其值。操作成功,返回值为TRUE,否则返回值为FALSE。
(6)GetHead(Q,&x):取队头元素操作。用x取得队头元素的值。操作成功,返回 TRUE,否则返回值为FALSE。
(7)ClearQueue(&Q):队列置空操作。将队列Q置为空队列。
(8)DestroyQueue(&Q): 队列销毁操作。释放队列的空间。

但是,队列的定义与栈的定义有点不一样。到底怎么个不一样法呢?那就来看看呗。

链队列定义如下: 
typedef struct Node 
{ 
    QueueElementType  data; /*数据域*/   
    struct Node*next; /*指针域*/ 
}LinkQueueNode; 

typedef struct  
{ 
    LinkQueueNode   * front; 
    LinkQueueNode   * rear; 
}LinkQueue; 

为什么这里需要两个typedef呢,感觉明明可以合起来用一个进行表示的阿。这个lyjgod也想了很久。不过花点时间还是可以理解的,其实我们可以将第一个typedef不看作是队列,而看成是队列中的一个个结点,而第二个定义才是队列本命。这是为什么呢,因为队列的操作模式要求我们要顾及的是队头和队尾,而不是中间的各个结点,因此,我们需要考虑到的只是有头指针和尾指针的LinkQueue而已,因为有了这两个我们就可以进行队列的所有操作了。当头尾指针指向同一个地址时,说明此时队列为空。(并不一定是指向NULL)

那么有了队列的定义,我们就可以进行队列的基本操作了。这理解列出队列最最基本的三个操作:初始化、入队、出队。

链队列初始化 
int InitQueue(LinkQueue * Q) 
{ /* 将 Q 初始化为一个空的链队列 */ 
  Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));   
  if(Q->front!=NULL) 
    { 
          Q->rear=Q->front;            
        Q->front->next=NULL;            
          return(TRUE); 
     } 
  else   
       return(FALSE);/* 溢出!*/ 
} 

链队列入队操作算法 
int EnterQueue(LinkQueue *Q, QueueElementType x) 
{  /* 将数据元素 x 插入到队列 Q 中 */ 
  LinkQueueNode  * NewNode; 
  NewNode=(LinkQueueNode * )malloc(sizeof(LinkQueueNode)); 
if(NewNode!=NULL) 
{ 
   NewNode->data=x; 
   NewNode->next=NULL; 
   Q->rear->next=NewNode; 
   Q->rear=NewNode; return(TRUE); 
} 
  else  return(FALSE);/* 溢出!*/ 
} 


链队列出队操作算法 
int DeleteQueue(LinkQueue * Q, QueueElementType *x) 
{  /* 将队列 Q 的队头元素出队,并存放到 x 所指的存储空间中 */ 
  LinkQueueNode * p; 
  if(Q->front==Q->rear)
     return(FALSE); 
  p=Q->front->next; 
  Q->front->next=p->next;  /* 队头元素 p 出队 */ 
  if(Q->rear==p)  /* 如果队中只有一个元素 p,则 p 出队后成为空队*/ 
      Q->rear=Q->front;   
  *x=p->data; 
  free(p);   /* 释放存储空间 */ 
  return(TRUE);  
}