573-环形队列和链式队列实现

￡神魔★判官ぃ 2022-09-11 14:10 194阅读 0赞

## 环形队列实现 ##

**注意一下扩容操作：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

#include <iostream>
    using namespace std;
    
    //环形队列：queue  push  pop  front  back  empty size
    class Queue
    {
        
    public:
        Queue(int size = 10)//构造函数 
            : cap_(size)
            , front_(0)
            , rear_(0)
            , size_(0)
        {
        
            pQue_ = new int[cap_];
        }
        ~Queue()//析构函数 
        {
        
            delete[]pQue_;
            pQue_ = nullptr;
        }
    
    public:
        //入队 O(1)
        void push(int val)
        {
        
            if ((rear_ + 1) % cap_ == front_)//队满了 
            {
        
                expand(2 * cap_);//二倍扩容 
            }
            pQue_[rear_] = val;
            rear_ = (rear_ + 1) % cap_;
            size_++;//队列中有效元素个数加1 
        }
        //出队 O(1)
        void pop()
        {
        
            if (front_ == rear_)//队空了 
                throw "queue is empty!";
            front_ = (front_ + 1) % cap_;
            size_--;//队列中有效元素个数减1 
        }
        //队头元素
        int front() const
        {
        
            if (front_ == rear_)
                throw "queue is empty!";
            return pQue_[front_];
        }
        //队尾元素
        int back() const
        {
        
            if (front_ == rear_)
                throw "queue is empty!";
            return pQue_[(rear_ - 1 + cap_) % cap_];
            //rear可能在0号位置，此时队尾元素位置在pQue[cap-1] 
        }
        //队空
        bool empty() const
        {
        
            return front_ == rear_;
        }
        //队列元素的个数
        int size() const
        {
        
            //return size;  O(1)
    
            //遍历一遍统计队列中有效元素的个数 O(n)
            int size = 0;
            for (int i = front_; i != rear_; i = (i + 1) % cap_)
            {
        
                size++;
            }
            return size;
        }
    
    private:
        //扩容接口
        void expand(int size)
        {
        
            int* p = new int[size];
            int i = 0;
            int j = front_;
            for (; j != rear_; i++, j = (j + 1) % cap_)
                //新内存比旧内存大，所以肯定是从新数组的0号位置直接拷贝下去就可以，肯定不会占满的 
            {
        
                p[i] = pQue_[j];
            }
            delete[]pQue_;
            pQue_ = p;
            cap_ = size;
            front_ = 0;
            rear_ = i;
        }
    
    private:
        int* pQue_;//方便自动扩容 
        int cap_;//空间容量
        int front_;//队头
        int rear_;//队尾
        int size_;//队列元素个数
    };
    
    int main()
    {
        
        int arr[] = {
         12,4,56,7,89,31,53,75 };
        Queue que;
    
        for (int v : arr)
        {
        
            que.push(v);
        }
    
        cout << que.front() << endl;
        cout << que.back() << endl;
    
        que.push(100);
        que.push(200);
        que.push(300);
        cout << que.front() << endl;
        cout << que.back() << endl;
    
        while (!que.empty())
        {
        
            cout << que.front() << " " << que.back() << endl;
            que.pop();
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 链式队列实现 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**链式队列占用的内存比较大，因为数组实现的队列每个元素只存储val值，对于双向链表来说，要存储val值和2个地址域**

**因为队列是从队尾入队（链表的尾插），从队头出队（删除链表中第一个有效节点）**，如果是用单向链表实现，从头节点head开始访问，那么，第一个有效节点是很好访问的，head->next就是第一个有效节点。但是，进行尾插的时候，得从头节点head开始遍历整个链表到尾节点，时间复杂度是O(n），非常耗时间。  
**我们使用双向循环链表，head->pre指向的就是链表的尾节点，这样时间复杂度是O(1)，节省了大量时间！**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**使用双向循环链表实现的队列，入队出队的时间复杂度都是O(1)**  
![在这里插入图片描述][fbd63d5c0dbc446483d2e4053f784da2.png]  
**删除操作图解**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**入队，尾插图解：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**出队，头删图解**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

#include <iostream>
    using namespace std;
    
    //链式队列
    class LinkQueue
    {
        
    public:
    	LinkQueue()//构造函数 
    	{
        
    		head_ = new Node();
    		head_->next_ = head_;
    		head_->pre_ = head_;
    	}
    	~LinkQueue()//析构函数 
    	{
        
    		Node* p = head_->next_;
    		while (p != head_)
    		{
        
    			head_->next_ = p->next_;
    			p->next_->pre_ = head_;
    			delete p;
    			p = head_->next_;
    		}
    		delete head_;
    		head_ = nullptr;
    	}
    
    public:
    	//入队 队尾入队 尾插 
    	void push(int val)
    	{
        
    		Node* node = new Node(val);
    		node->next_ = head_;
    		node->pre_ = head_->pre_;
    		head_->pre_->next_ = node;
    		head_->pre_ = node;
    	}
    	//出队 队头出队 头删 
    	void pop()
    	{
        
    		Node* p = head_->next_;
    		head_->next_ = p->next_;
    		p->next_->pre_ = head_;
    		delete p;
    	}
    	//获取队头元素
    	int front() const
    	{
        
    		if (head_->next_ == head_)
    		{
        
    			throw "queue is empty!";
    		}
    		return head_->next_->data_;
    	}
    	//获取队尾元素
    	int back() const
    	{
        
    		if (head_->next_ == head_)
    		{
        
    			throw "queue is empty!";
    		}
    		return head_->pre_->data_;
    	}
    	//判空
    	bool empty() const
    	{
        
    		return head_->next_ == head_;
    	}
    
    private:
    	struct Node//节点类型 
    	{
        
    		Node(int data = 0)
    			: data_(data)
    			, next_(nullptr)
    			, pre_(nullptr)
    		{
        }
    		int data_;
    		Node* next_;
    		Node* pre_;
    	};
    
    	Node* head_;//指向头节点
    };
    
    int main()
    {
        
    	int arr[] = {
         12,4,56,7,89,31,53,75 };
    	LinkQueue que;
    
    	for (int v : arr)
    	{
        
    		que.push(v);
    	}
    
    	cout << que.front() << endl;
    	cout << que.back() << endl;
    
    	que.push(100);
    	que.push(200);
    	que.push(300);
    	cout << que.front() << endl;
    	cout << que.back() << endl;
    
    	while (!que.empty())
    	{
        
    		cout << que.front() << " " << que.back() << endl;
    		que.pop();
    	}
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f6b3d2c206f74a38a131db2bc4519967.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d76fbfe335584c1386e8ed233ac09798.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/ed83fd632a884c0d80c8bfe554b75e37.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/498c2854ccb748749e83f1f0de64d648.png
[fbd63d5c0dbc446483d2e4053f784da2.png]: /images/20220828/667d561280394f29b6a980146a3e2b9a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/c123cce1ea7e415d970117d4c0a93271.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/fcec2f05de8d42c8a1d29dd107bf6885.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/0093c5d74fa64cbb92e34e9af987b04b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/ee2b393c307e4d83a77112afe65a949f.png