C++队列

时间：2025-03-15 09:53:22

C++队列

一、基本概念：

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

二、队列的操作：

  • 判断队列是否为空
  • 入队，通常命名为push（）
  • 出队，通常命名为pop（）
  • 获取队头元素，通常命名为front（）
  • 求队列中元素个数

三、 队列的分类;

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

四、基于数组的循环队列

数组存储的缺点：
入队操作：在数组的末尾添加元素，时间复杂度为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;
}

相关文章