队列和循环队列的实现

绝地灬酷狼 2022-05-16 01:34 256阅读 0赞

## 队列 ##

> **定义**：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

按照队列的定义，结合内存地址的理解，初始化队列的时候，准备`head`和`rear`指针分别指向头和尾。Push操作，只需要改变`rear`指针；PopLeft操作只需要改变`head`。由于是线性表结构，所以在封装GetSize的时候，不能简单的用`rear-head`，因为每次申请的结点都是内存中随机的区域，正因如此，这种队列链（线性表实现）更具有灵活性。

**代码实现**

#include<iostream>
    using namespace std;
    typedef int DataType;
    
    struct Queue{
        DataType data;
        Queue *next;
    };
    
    void InitQueue(Queue *&head,Queue *&rear){
        head = new Queue;
        head->next = NULL;
        rear = head;
    }
    
    void Push(Queue *&rear,DataType data){
        Queue *q = new Queue;
        q->data = data;
        q->next = NULL;
        rear->next = q;
        rear = q;
    }
    void PopLeft(Queue *&head,DataType &data){ //data 是弹出的数据 
        if(!head->next) //判断是否是空的队列 
            return ;
        else{
            Queue *q = head->next;  //保存No 1的队列结点 
            delete head;
            head = q;
            data = q->data;
        }
    }
    int GetSize(Queue *head){
        if(!head->next) //head->next是NULL的时候，队列为空 
            return 0;
        else{ //迭代计算长度 
            int length= 0;
            Queue *tem = head->next ;
            while(tem){
                ++length;
                tem = tem->next;
            }
            return length;
        }
    }
    void DeleteQueue(Queue *&head){
        Queue *p = head; //当前要删除的结点 
        Queue *q = p->next;
        while(q){
            delete p;
            p = q;
            q = p->next;
        }
        delete p;
    }
    
    int main(){
        Queue *head=NULL,*rear = NULL;
        DataType data ;     //用来保存弹出的元素 
        
        InitQueue(head,rear);
        
        Push(rear,-1);
        Push(rear,-2);
        Push(rear,100);
        Push(rear,-100);
        
        cout<<"长度是："<<GetSize(head)<<endl;
        
        PopLeft(head,data);
        cout<<"弹出元素："<<data<<endl;
        PopLeft(head,data);
        cout<<"弹出元素："<<data<<endl;
        
        DeleteQueue(head);
        //cout<<"长度是："<<GetSize(head)<<endl; 无法执行，说明DeleQueue成功 
        return 0;
    }

--------------------

## 循环队列 ##

> **定义**：为充分利用向量空间，**克服"假溢出"现象**的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。

虽然可以克服假溢出，但是循环队列**长度有限**，并且内存中不可能有类似循环的物理结构。我们需要用逻辑来实现这种循环队列。

如果采用一段连续地址进行实现，可以使用数组，实现简单，不做实现；这里是采用使用的连续指针进行实现。

需要准备`base_front`指针来记录最初的头位置。需要`count`和`size`分别存放队列大小和队列中的数据个数。**循环的逻辑实现就是：在特定条件下，`front` 和 `rear` 都要重新指向`save_front` ，形成一个环。**

#include<iostream>
    using namespace std;
    
    const int SIZE = 3; //默认队列大小 
    template <class T>  //为了适应各种数据类型，使用类模板 
    class CirQueue {
        private:
            T *front;
            T *rear;
            T *save_front;
            int size;
            int count ; //记录有多少个元素 
        public:
            CirQueue(){
                count = 0;
                size = SIZE;
                front = new T [size];
                save_front = rear  = front;
            }
            CirQueue(int s){
                count = 0;
                size = s;
                front = new T [size];
                save_front = rear = front;
            }
            int GetSize(){
                return size;
            }
            void Push(T data){
                if(count==size)
                    return ; //队列已满 
                *rear = data;
                ++count;
                if (count==size)//只剩最后一个位置 
                    rear = save_front; //完成逻辑上的循环 
                else
                    ++rear; 
            }
            void PopLeft(T &data){
                if(!count) //如果没有元素
                    return;
                --count;
                data = *front;
                if(front-save_front==size-1)
                    front = save_front;
                else
                    ++front;
            }
            void Delete(){
                delete [] save_front;
                cout<<"删除成功"<<endl;
            }
    };
    int main(){
        CirQueue <int> tem;
        int data;
        for(int i=0;i<4;++i)
            tem.Push(i+1); //1 2 3
        for(int i=0;i<tem.GetSize();++i){
            tem.PopLeft(data);
            cout<<data<<endl;
        }
        tem.Delete();
        return 0;
    }