循环队列

2014/12/31 11974

线性结构的不多说，是一种操作受限制的线性结构，推荐队列对比起栈学习会更简单，也就是和栈差不多，多了而一个指针，栈是由一个头指针就ok了，队列多一个尾指针，因为栈是先进后出，队列是先进先出；比如排队买票排在前面的先买到票；

刚开始先看普通队列，

不断的入队，rear往上移动，出队front往上移动，这个队列的实际有效区域在两个指针之间，于是随front往上移动的过程中front以下的空间就不能利用了，这种就叫什么内存泄露（好像是这么说的）；

要解决这个问题就要把普通队列改为循环队列，下面就以循环队列写代码；

在循环队列中难理解的就是判断队空队满，在用循环队列的时候我们将要空出一个内存单元不用（作用见下面）；

Q.front==Q.rear就为队空，

(Q.front+1)%MAXSIZE==Q.rear就为队满，（MAXSIZE为队列最大容量）；这里就是说为什么循环队列要空一个空间的原因了；还有就是(Q.front+1)%MAXSIZE这里用到了取膜的方法；

下面写的循环队列：

    #include<stdio.h>  
    #define M 1000  
    typedef struct quene  
    {  
        int *a;  
        int top;  
        int Tail;  
    }*Quene;  
    void Initialization(Quene);  
    void Add(Quene,int);  
    int * Out(Quene);  
    void PutAll(Quene);  
    bool Full(Quene);  
    bool Empty(Quene);  
      
    int main()  
    {  
        Quene p=new struct quene;  
        Initialization(p);  
        Add(p,2);  
        Add(p,3);  
        Add(p,4);  
        Add(p,5);  
        Out(p);  
        PutAll(p);  
        return 0;  
    }  
    void Initialization(Quene p)  
    {  
        p->a=new int[M];  
        p->top=p->Tail=0;  
    }  
    bool Full(Quene p)  
    {  
        if((p->Tail+1)%M==p->top)  
            return true;  
        return false;  
    }  
    bool Empty(Quene p)  
    {  
        if(p->top==p->Tail)  
            return true;  
        return false;  
    }  
    void Add(Quene p,int e)  
    {  
        if(Full(p))  
            return;  
        p->a[p->Tail]=e;  
        p->Tail=(p->Tail+1)%M;  
    }  
    int * Out(Quene p)  
    {  
        if(Empty(p))  
            return NULL;  
        int w;  
        w=p->a[p->top];  
        p->top=(p->top+1)%M;  
        return &w;  
    }  
    void PutAll(Quene p)  
    {  
        while(p->top!=p->Tail)  
        {  
            printf("%d ",p->a[p->top]);  
            p->top=(p->top+1)%M;  
        }  
        printf("\n");  
    }

写的很简单，看懂了自己就可以多写一些功能了，都是以int型作为基本的数据单元，在实际应用中碰到的很多都是结构体，或者是面向对象的类；

代码片段