队列的基本操作（顺序结构）C/C++

Bertha 。 2022-07-15 10:38 231阅读 0赞

顺序结构的队列，大多情况下对空间的申请比较死，想了个办法：用string形式来存储队列元素，对于new的方式，我也实在想不出够准确的申请方法。

C语言式：

#include <iostream>
    #include <memory.h>
    using namespace std;
    
    struct Queue
    {
        char data[1024];
        int front,rear ;
    };
    
    void initQueue(Queue *q)
    {
        q->front=q->rear=0;
        memset(q->data,0,1024);
    }
    
    bool Isfull(Queue *q)
    {
        return q->rear==1024;
    }
    
    char pop(Queue *q)
    {
        return q->data[q->front++];
    }
    
    void push(Queue *q,char c)
    {
        q->data[q->rear++]=c;
    }
    
    int Isempty(Queue *q)
    {
        if(q->front==q->rear)
            return 1;
        return 0;
    }
    
    int main()
    {
        Queue q;
        initQueue(&q);
        for(char i='a';i<='z';i++)
        {
            if(!Isfull(&q))
            push(&q,i);
        }
    
        while(!Isempty(&q))
        cout<<pop(&q)<<" ";
    
        return 0;
    }

C++版：

注意！

realloc()的作用是对之前用malloc()/calloc()分配的空间修改大小，而不是分配新空间，realloc()修改过的空间地址和之前的相同，除非之前的地址开始的连续空间不如修改后的空间大，中这种情况下，它会在其它地方分配一块新大小的空间，并将原空间保存的内容复制到新空间中，然后释放原空间。
    
    简单的说，就是这里应该用malloc()分配新空间，而不是realloc()修改先前分配的空间。

#include <iostream>
    #include <memory.h>
    #include <stdlib.h>
    using namespace std;
    
    int size = 10;
    struct Queue
    {
        char *data;
        int front,rear ;
    };
    
    void initQueue(Queue *q)
    {
        q->front=q->rear=0;
        q->data=(char*)calloc(size,sizeof(char));
    }
    
    bool Isfull(Queue *q)
    {
        return q->rear==10;
    }
    
    char pop(Queue *q)
    {
        return q->data[q->front++];
    }
    
    void push(Queue *q,char c)
    {
        q->data[q->rear++]=c;
        if(q->rear>=size-1)         //如果空间不够，就用realloc重置data的空间大小
        {
            size=2*size;
            while(!(q->data=(char*)realloc(q->data,sizeof(char))))
                q->data=(char*)realloc(q->data,size*sizeof(char));
        }
    }
    
    int Isempty(Queue *q)
    {
        if(q->front==q->rear)
            return 1;
        return 0;
    }
    
    int main()
    {
        Queue q;
        initQueue(&q);
        for(char i='a';i<='z';i++)
        {
            push(&q,i);
        }
    
        while(!Isempty(&q))
        cout<<pop(&q)<<" ";
    
        return 0;
    }

#include <iostream>
    #include <memory.h>
    #include <string>
    
    using namespace std;
    
    struct Queue
    {
        string data;//不用担心溢出了，不过感觉有点变味了
        int front,rear ;
    };
    
    void initQueue(Queue *q)
    {
        q->front=q->rear=0;
    }
    
    char pop(Queue *q)
    {
        return q->data[q->front++];
    }
    
    void push(Queue *q,char c)
    {
        q->data.push_back(c);//因为这里用了pushback，所以感觉能实现功能但是怪怪的
        q->rear++;
    }
    
    int Isempty(Queue *q)
    {
        if(q->front==q->rear)
            return 1;
        return 0;
    }
    
    int main()
    {
        Queue q;
        initQueue(&q);
        for(char i='a';i<='z';i++)
        {
            push(&q,i);
        }
    
        while(!Isempty(&q))
        cout<<pop(&q)<<" ";
    
        return 0;
    }

主要是，我觉得上面C++的方式能够省去判满的步骤![微笑][smile.gif]

大家有好的办法的话，可以分享下。 ![大笑][laugh.gif]

![Center][]

[smile.gif]: /images/20220715/1db62d3d8b0d43b38d00f7541e3dc9af.png
[laugh.gif]: /images/20220715/794fca43bf6041fc8cc18ee9fce14a50.png
[Center]: /images/20220715/31438262fe2540e5b82c4f40dc6fd322.png