C++-queue：queue基本用法【q.push(x)、q.front()、q.back()、q.pop()、q.size()、q.empty()】

桃扇骨 2023-09-25 14:15 22阅读 0赞

### 队列 ###

一种操作受限制的线性表

### 一、基本概念： ###

*  队列是一种线性储存数据结构，数据元素遵循“先进先出”（First in First out （FIFO））的原则
 *  添加元素在队尾（只允许添加元素）实现，删除元素在对头（只允许删除元素）实现

### 适用条件 ###

排队 挂号 [消息队列][Link 1] 广度优先搜索等符合队列特点的操作

### 二、队列的操作： ###

queue<int> q;	//以int型为例
    int x;
    q.empty()               如果队列为空返回true，否则返回false
    q.size()                返回队列中元素的个数
    q.pop()                 删除队列首元素但不返回其值
    q.front()               返回队首元素的值，但不删除该元素
    q.push(x)               在队尾压入新元素
    q.back()                返回队列尾元素的值，但不删除该元素

### 三、 队列的分类; ###

*  基于数组的循环队列（循环队列）
 *  基于链表的队列（链表队列）

### 四、基于数组的[循环队列][Link 2] ###

**数组存储的缺点：**  
入队操作：在数组的末尾添加元素，时间复杂度为O（1）  
出队操作：数组头部元素出队之后，头部之后的元素均需要往前移动一个位置，时间复杂度为O（n）  
**循环队列**  
为了降低时间复杂度，将数组当作一个首尾相连的圆环，分别用两个标志front、rear代表队列的头部和尾部。删除元素时，队首标志往后移，添加元素时，若队尾没有空间，考虑数组的头部空间若还有，则在队头添加元素，防止数组内存空间的流失。  
**判断满或空的方法：**  
*方法一：*  
设置一个标志变量flag，同时满足front=rear且flag=1时为满队列  
*方法二:*  
空一个元素，保持为空  
1.空队列：队首标志与队尾重合  
2.满队列：队尾标志+1=队首标志  
**C++实现：**

#include<iostream>
    using namespace std;
    
    //队列的抽象类
    template <class T>
    class queue
    {
    public:
        virtual ~queue() {};
        virtual bool empty() const=0; 
        virtual int size() const=0;   
        virtual T& front() = 0;
        virtual void pop() = 0;
        virtual void push(const T& theElement) = 0;
    };
    
    //队列的数组类实现
    template<class T>
    class arrayQueue :public queue<T>
    {
        arrayQueue(int initialCapacity = 10);
        ~arrayQueue() { delete[]queue; }
        bool empty()const
        {
            if (queuefront == queuerear)
                return true;
            return false;
        }
        int size() const
        {
            return (queuerear - queuefront + capacity) % capacity;
        }
        T& front()
        {
            if (queuefront == queuerear)
            {
                cout << "The queue is empty!" << endl;
                return false;
            }
            return queue[queuefront];
        }
        void pop()
        {
            if (queuefront == queuerear)
                cout << "The queue is empty!" << endl;
            queue[queuefront].~T;
            queuefront = (queuefront + 1) % capacity;
        }
        void push(const T& theElement);
    private:
        int capacity;
        int queuefront;
        int queuerear;
        T* queue;
    };
    
    template<class T>
    arrayQueue<T>::arrayQueue(int initialCapacity)
    {
        if (initialCapacity < 1)
            cout << "InitialCapacity must >0!" << endl;
        capacity = initialCapacity;
        queue = new T[capacity];
        queuefront = 0;
        queuerear = 0;
    }
    
    template<class T>
    void arrayQueue<T>::push(const T& theElement)
    {
        if ((queuerear + 1) % capacity == queuefront)
        {
            T* temp = new T[2 * capacity];
            //没有形成环
            if (queuefront == 0)
                copy(queuefront, queuerear, temp);
            else
            {
                copy(queuefront, queue + capacity, temp);
                copy(queue, queuerear, temp + queue + capacity - queuefront);
            }
            queuefront = 0;
            queuerear = capacity-1;
            delete[]queue;
            queue = temp;
        }
        queue[queuerear] = theElement;
        queuerear = (queuerear + 1) % capacity;
    }

### 五、基于链表的队列 ###

**特点**：  
以结构体节点为单位，不存在元素移动复杂度问题以及内存的浪费问题。  
链表头为队列头部，链表尾为队列尾部。  
设计两个变量queueFront、queueBack记录队列的两端变化  
指针queueFront为标志头指针，指针queueBack指向最后一个元素  
**C++实现**

#include<iostream>
    using namespace std;
    //队列节点结构体
    template<class T>
    struct QueueNode
    {
    	T element;              //存储元素
    	QueueNode<T>* next;        //记录下一个队列节点
    	QueueNode(T a, QueueNode<T>* b=nullptr)
    	{
    		this->element = a;
    		this->next = b;
    	}
    };
    template<class T>
    class ChainQueue
    {
    public:
    	ChainQueue();
    	~ChainQueue();
    	bool Empty()const;
    	int size() const;
    	void pop();
    	void push(T theElement);
    	T& top();
    private:
    	QueueNode<T>* front;            //指向头部前一位的空指针
    	QueueNode<T>* back;             //指向队列尾部的指针
    	int count;
    };
    //队列的具体实现
    template<class T>
    ChainQueue<T>::ChainQueue()
    {
    	front = new QueueNode<T>(NULL);
    	back = front;
    	count = 0;
    }
    template<class T>
    ChainQueue<T>::~ChainQueue()
    {
    	while (front->next!= nullptr)
    	{
    		QueueNode<T> *temp = front->next;
    		front->next = front->next->next;
    		delete temp;
    	}
    }
    template<class T>
    bool ChainQueue<T>::Empty()const
    {
    	if (front==back)
    		return true;
    	return false;
    }
    template<class T>
    int ChainQueue<T>::size() const
    {
    	return count;
    }
    template<class T>
    void ChainQueue<T>::pop()
    {
    	if (count == 0)
    		cout << "The ChainQueue is empty!" << endl;
    	QueueNode<T>* temp = front->next;
    	front->next = front->next->next;
    	delete temp;
    	count--;
    }
    template<class T>
    void ChainQueue<T>::push(T theElement)
    {
    	QueueNode<T>* temp = new QueueNode<T>(theElement);
    	back->next = temp;
    	back = temp;
    	count++;
    }
    template<class T>
    T& ChainQueue<T>::top()
    {
    	if (count == 0)
    		cout<<"The ChainQueue is empty!"<<endl;
    	return front->next->element;
    }
    int main()
    {
    	ChainQueue<int> cq;
    	cout << "Empty?   " <<cq.Empty() <<endl;
    	cq.push(10);
    	cq.push(20);
    	cout << "The top element is" << cq.top() << endl;
    	cout << "The size is " << cq.size() << endl;
    	cq.push(30);
    	cq.push(40);
    	cq.pop();
    	cout << "The top element is" << cq.top() << endl;
    	cout << "The size is " << cq.size() << endl;
    	cq.pop();
    	cq.pop();
    	cout << "The top element is" << cq.top() << endl;
    	cout << "The size is " << cq.size() << endl;
    	system("pause");
    	return 0;
    }

[C++队列\_Potato\_10的博客-CSDN博客\_c++ 队列][C_Potato_10_-CSDN_c_]

[C++队列详解\_T\_Y\_F666的博客-CSDN博客\_c++ 队列][C_T_Y_F666_-CSDN_c_]

[Link 1]: https://so.csdn.net/so/search?q=%E6%B6%88%E6%81%AF%E9%98%9F%E5%88%97&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E5%BE%AA%E7%8E%AF%E9%98%9F%E5%88%97&spm=1001.2101.3001.7020
[C_Potato_10_-CSDN_c_]: https://blog.csdn.net/Potato_10/article/details/108056179
[C_T_Y_F666_-CSDN_c_]: https://blog.csdn.net/T_Y_F_/article/details/125304554