返回顶部

收藏

循环队列

更多

线性结构的不多说,是一种操作受限制的线性结构,推荐队列对比起栈学习会更简单,也就是和栈差不多,多了而一个指针,栈是由一个头指针就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 &amp;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型作为基本的数据单元,在实际应用中碰到的很多都是结构体,或者是面向对象的类;

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning

发表评论