vector实现循环队列

发布时间:2023年12月20日

顺序队列

? ? ? ?顺序队列是一种先进先出的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。因为其入队和出队操作均是(front/rear)指针向后移动,以进行结点的链接和删除,这就造成其使用空间不断向出队的那一边偏移,当出队入队次数频繁时,尾指针移动到我们可以进行队列操作的范围之外去了,则会产生假溢出。

(当使用动态链表创建顺序队列,其向后继续不断的申请内存空间,即使前面出队操作释放掉了前面的空间,但是指针依旧会向后进行移动,直到达到系统预留给程序的内存上界被强行终止)。

循环队列

? ? ? ? 循环队列就是为了解决顺序队列的“假溢出”问题,即将顺序队列臆造为一个环状的空间。循环队列中指针和队列元素之间的关系不变,我们只需要利用模运算就可以很容易实现指针的循环移动。

????????但是循环队列中存在一个问题,在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”,可有两种处理方法:

? ? ?(一)设置队列元素个数成员,以区别队列是“空”还是“满”;

? ? ?(二)front指针表示为虚拟头指针,即不指向元素,队列的实际元素数量要比队列空间maxsize少一个,如下图所示,队列总长度为8,实际元素个数为7个,还有一个被front指针使用。

(一)设置队列元素个数成员,以区别队列是“空”还是“满”;

// vector实现循环队列

#include<iostream>
#include<vector>
using namespace std;


class cirQueue
{
public:
    int maxsize;
    int front;
    int rear;
    int count;
    vector<int> data;

public:
    cirQueue(){
        this->count = 0;
        this->maxsize = 8;
        this->front = 0;
        this->rear = 0;
        for(int i=0; i<maxsize; i++){
            this->data.push_back(0);
        }
    }
    cirQueue(int maxsize):count(0),maxsize(maxsize),front(0),rear(0){
        for(int i=0; i<maxsize; i++){
            this->data.push_back(0);
        } 
    }
    void push_cirQueue(int data);
    void pop_cirQueue();
    void show_cirQueue();
};

// 入队
void cirQueue::push_cirQueue(int val){
    //满了(rear的下一个元素是front),再继续就溢出 
    if( (this->rear+1)%maxsize == this->front ){
        cout<<"the cirQueue is full!"<<endl;
    }
    //从rear加入元素
    else{
        // 判断队列是否为空
        if(this->count == 0){
            this->data[this->rear] = val;
        }
        else{
            this->rear = (this->rear+1)%maxsize;
            this->data[this->rear] = val;    
        }
        this->count++;
    }
}

// 出队
void cirQueue::pop_cirQueue(){
    //判断队列是否为空
    if(this->count == 0){
        cout<<"the cirQueue is empty!"<<endl;
    }
    //front出队
    else{
        this->data[this->front] = 0;
        this->front = (this->front+1)%maxsize;
    }
    this->count--;
}

void cirQueue::show_cirQueue(){
    if(this->count == 0){
        cout<<"the cirQueue is empty!"<<endl;
    }
    else{
        int cur = this->front;
        cout<<this->data[cur]<<", ";
        while(cur != this->rear){
            cur = (cur+1)%maxsize;
            cout<<this->data[cur]<<", ";
        }
        cout<<endl;
    }
}

int main()
{
    cirQueue myCirQueue(5);
    myCirQueue.show_cirQueue();
    cout<<"front:"<<myCirQueue.front<<" rear:"<<myCirQueue.rear<<endl;
    
    myCirQueue.push_cirQueue(1);
    myCirQueue.push_cirQueue(2);
    myCirQueue.push_cirQueue(3);
    myCirQueue.push_cirQueue(4);
    myCirQueue.push_cirQueue(5);
    
    myCirQueue.show_cirQueue();
    cout<<"front:"<<myCirQueue.front<<" rear:"<<myCirQueue.rear<<endl;

    myCirQueue.push_cirQueue(6);
    myCirQueue.show_cirQueue();
    
    myCirQueue.pop_cirQueue();
    myCirQueue.show_cirQueue();
    cout<<"front:"<<myCirQueue.front<<" rear:"<<myCirQueue.rear<<endl;

    return 0;
}

?

(二)?front指针表示为虚拟头指针,即不指向元素,

// vector实现循环队列

#include<iostream>
#include<vector>
using namespace std;


class cirQueue
{
public:
    int maxsize;
    int front;
    int rear;
    int count;
    vector<int> data;

public:
    cirQueue(){
        this->count = 0;
        this->maxsize = 8;
        this->front = 0;
        this->rear = 0;
        for(int i=0; i<maxsize; i++){
            this->data.push_back(0);
        }
    }
    cirQueue(int maxsize):count(0),maxsize(maxsize),front(0),rear(0){
        for(int i=0; i<maxsize; i++){
            this->data.push_back(0);
        } 
    }
    void push_cirQueue(int data);
    void pop_cirQueue();
    void show_cirQueue();
};

// 入队
void cirQueue::push_cirQueue(int val){
    //满了(rear的下一个元素是front),再继续就溢出 
    if( (this->rear+1)%maxsize == this->front ){
        cout<<"the cirQueue is full!"<<endl;
    }
    //从rear加入元素
    else{
        this->rear = (this->rear+1)%maxsize;
        this->data[this->rear] = val;
        this->count++;
    }
}

// 出队
void cirQueue::pop_cirQueue(){
    //判断队列是否为空
    if(this->front == this->rear){
        cout<<"the cirQueue is empty!"<<endl;
    }
    //front出队
    else{
        this->data[this->front] = 0;
        this->front = (this->front+1)%maxsize;
    }
    this->count--;
}

void cirQueue::show_cirQueue(){
    if(this->front == this->rear){
        cout<<"the cirQueue is empty!"<<endl;
    }
    else{
        int cur = this->front;
        while(cur != this->rear){
            cur = (cur+1)%maxsize;
            cout<<this->data[cur]<<", ";
        }
        cout<<endl;
    }
}

int main()
{
    cirQueue myCirQueue(5);
    myCirQueue.show_cirQueue();
    cout<<"front:"<<myCirQueue.front<<" rear:"<<myCirQueue.rear<<endl;
    
    myCirQueue.push_cirQueue(1);
    myCirQueue.push_cirQueue(2);
    myCirQueue.push_cirQueue(3);
    myCirQueue.push_cirQueue(4);
    myCirQueue.push_cirQueue(5);
    
    myCirQueue.show_cirQueue();
    cout<<"front:"<<myCirQueue.front<<" rear:"<<myCirQueue.rear<<endl;

    myCirQueue.push_cirQueue(6);
    myCirQueue.show_cirQueue();
    
    myCirQueue.pop_cirQueue();
    myCirQueue.show_cirQueue();
    cout<<"front:"<<myCirQueue.front<<" rear:"<<myCirQueue.rear<<endl;

    return 0;
}

文章来源:https://blog.csdn.net/qq_43855258/article/details/135083723
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。