【数据结构之旅】循环队列

说明：

    时间关系，这里只给出代码及注释，有空的时候再详细介绍一下代码的实现流程。

1.代码及注释

    如下：

#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;
typedef struct {
   ElemType  *elem;  // 存储空间的基址
   int front;        // 队头位标
   int rear;         // 队尾位标，指示队尾元素的下一位置
   int maxSize;      // 最大长度
} SqQueue;


#define OVERFLOW -1
#define OK 1
#define ERROR 0    
#define TRUE 2
#define FALSE -2

typedef int Status;

Status InitQueue_Sq(SqQueue &Q, int size) { // 构造一个空队列
   Q.elem = (ElemType *)malloc(size*sizeof(ElemType));
   Q.maxSize = size;
   Q.front = Q.rear = 0;
   return OK;
} 


Status QueueEmpty_Sq(SqQueue Q){ // 判断队列Q是否空，若空则返回TRUE，否则FALSE
   if(Q.front == Q.rear)
      return TRUE;
   else  
      return FALSE; 
}

Status EnQueue_Sq(SqQueue &Q, ElemType e) {
        // 若当前队列不满，在队列的尾元素之后，插入元素 e 为新的队列尾元素

   if(Q.front == (Q.rear + 1)%Q.maxSize)
       return ERROR;

   Q.elem[Q.rear] = e;
   Q.rear = (Q.rear + 1)%Q.maxSize;
   return OK;
}


Status DeQueue_Sq(SqQueue &Q, ElemType &e) {
        // 若队列不空，则删除队列Q中的头元素，用 e 返回其值
   if(Q.front == Q.rear)
      return ERROR; // 队空报错
   e = Q.elem[Q.front];
   Q.front = (Q.front+1)%Q.maxSize; // Q.front循环加1
   return OK;
}

int main(void) {    
    SqQueue Q;
    ElemType e;
    Status result1, result2;
    
    //1. 初始化一个size为5的循环队列Q
    InitQueue_Sq(Q, 5);
    EnQueue_Sq(Q, ‘A‘); 
    EnQueue_Sq(Q, ‘B‘); 
    EnQueue_Sq(Q, ‘C‘);    
    EnQueue_Sq(Q, ‘D‘);
    DeQueue_Sq(Q, e);   
    EnQueue_Sq(Q, ‘E‘);  
    DeQueue_Sq(Q, e);   
    EnQueue_Sq(Q, ‘F‘);   //出现了要用求余确定来确定新进队列的元素位置，
                          //即“循环使用空间的情况”   
    result1 = EnQueue_Sq(Q, ‘G‘);   //满了，放不下
   
    printf("result1 = %d\n", result1);
                                               
    DeQueue_Sq(Q, e);   
    DeQueue_Sq(Q, e);   
    DeQueue_Sq(Q, e);   
    DeQueue_Sq(Q, e);   
    result2 = DeQueue_Sq(Q, e);   //空了，return FALSE      
      
    printf("result2 = %d\n", result2);
                                          
    
}

2.执行结果

    如下：

result1 = 0
result2 = 0
请按任意键继续. . .

3.研究方法

    第2步只是直接给出结果，实际上利用编译器的断点功能可以观察每一步的执行情况，从而加深对循环队列的理解，可以尝试一下。

本文出自 “香飘叶子” 博客，请务必保留此出处http://xpleaf.blog.51cto.com/9315560/1696608

【数据结构之旅】循环队列

原文：http://xpleaf.blog.51cto.com/9315560/1696608