队列

队列的基本运算：置空队列、判空队列、入队列、出队列、取队列头

顺序队列(循环队列)

• 置空队列

  void InitQueue(CirQueue *Q){
      Q->front=Q->rear=0;
  } 
  

• 判空队列

  int QueueEmpty(CirQueue *Q){
      return Q->rear==Q->front;
  }
  

• 判队满

  int QueueFull(CirQueue *Q){
      return (Q->rear+1)%QueueSize==Q->front;
  }
  

• 入队列

  void EnQueue(CirQueue *Q,DataType x){
      if(QueueFull(Q)){
          prinf("Queue overflow");
      }else{
          Q->data[Q->rear]=x;
          Q->rear=(Q->rear+1)%QueueSize;
      }
  }
  

• 取队列头

  DataType GetFront(CirQueue *Q){
      if(QueueEmpty(Q)){
          prinf("Queue empty");
      }else{
          return Q->data[Q->front];
      }
  }
  

• 出队列

  DataType DeQueue(CirQueue *Q){
      DataType x;
      if(QueueEmpty(Q)){
          prinf("Queue empty");
          exit(0);
      }else{
          x=Q->data[Q->front];
          Q->front=(Q->front+1)%QueueSize;
          return x;
      }
  }
  

链队列（带头结点）

• 构造空队列

  void InitQueue(LinkQueue *Q){
      Q->front=(QueueNode *)malloc(sizeof(QueueNode));
      Q->rear=Q-front;
      Q->rear->next=NULL;
  }
  

• 判队空

  int QueueEmpty(LinkQueue *Q){
     return Q->rear==Q->front; 
  }
  

• 入队列

  void EnQueue(LinkQueue *Q){
      QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));
      p->data=x;
      p->next=NULL;
      Q->rear->next=p;
      Q->rear=p;
  }
  

• 取队列头元素

  DataType GetFront(LinkQueue *Q){
      if(QueueEmpty(Q)){
          prinf("Queue underflow");
          exit(0);
      }else{
          return Q->front->next->data;
      }
  }
  

• 出队列

  DataType DeQueue(LinkQueue *Q){
      QueueNode *p;
      if(QueueEmpty(Q)){
          prinf("Queue underflow");
          exit(0);
      }else{
          p=Q->front;
          Q->front=Q->front->next;
          free(p);
          return(Q->front->data);
      }
  }