循环队列(Circular queue) -- C++ 实现


实现代码

// CircularQueue.h
#ifndef CIRULARQUEUE_H
#define CIRULARQUEUE_H

#include<iostream>
using namespace std;

namespace jay{
	template<typename T>
	class CircularQueue
	{
	public:
		CircularQueue(int maxsize = 100);
		CircularQueue(const CircularQueue<T>& rhs);
		CircularQueue<T>& operator=(const CircularQueue<T>& rhs);
		~CircularQueue();

		void Enqueue(const T& data);
		void Dequeue();

		bool isFull();

		T& Front();
		T  Front() const;

		bool IsEmpty() const;
		int Size() const;
	private:
		// 存放T的内存区域
		T *m_array;
		// 首元素
		int m_nFront;
		// 最后一个入队列的元素[的下一个内存地址]
		int m_nLast;
		int m_ncapacity;
	};

	template<typename T>
	CircularQueue<T>::CircularQueue(int nMaxsize) :
	m_nFront(0), m_nLast(0),m_ncapacity(nMaxsize)
	{
		m_array = NULL;
		m_array = new T[nMaxsize+1];
		if (m_array == NULL)
		{
			throw "Failed to allocate memory!";
		}
	}

	template<typename T>
	CircularQueue<T>::CircularQueue(const CircularQueue<T>& rhs) :
	m_nFront(rhs.m_nFront), m_nLast(rhs.m_nLast),m_ncapacity(rhs.m_ncapacity)
	{
		int nSize = rhs.Size();
		int Front = rhs.m_nFront;

		m_array = new T[m_ncapacity+1];
		if (m_array == NULL)
		{
			throw "Failed to allocate memory!";
		}

		for (int i = 0; i < rhs.m_ncapacity; i++)
		{
			m_array[i] = rhs.m_array[i];
		}
	}

	template<typename T>
	CircularQueue<T>& CircularQueue<T>::operator=(const CircularQueue<T>& rhs)
	{
		if (this != &rhs)
		{
			delete[] m_array;

			m_ncapacity = rhs.m_ncapacity;
			m_nFront = rhs.m_nFront;
			m_nLast = rhs.m_nLast;
			int Front = rhs.m_nFront;

			m_array = new T[m_ncapacity+1];
			if (m_array == NULL)
			{
				throw "Failed to allocate memory!";
			}

			for (int i = 0;i <rhs.m_ncapacity; i++)
			{
				m_array[i] = rhs.m_array[i];
			}

		}

		return *this;
	}

	template<typename T>
	CircularQueue<T>::~CircularQueue()
	{
		delete[] m_array;
	}

	template<typename T>
	bool CircularQueue<T>::isFull() 
	{  
		return (m_nLast + 1) % m_ncapacity == m_nFront;   
	}   

	template<typename T>
	bool CircularQueue<T>::IsEmpty() const
	{
		return m_nLast == m_nFront;
	}

	template<typename T>
	int CircularQueue<T>::Size() const
	{
		return (m_nLast - m_nFront + m_ncapacity) % m_ncapacity;
	}

	template<typename T>
	void CircularQueue<T>::Enqueue(const T& data)
	{
		// 当队列Size大于m_ncapacity的1/2时 队列 m_ncapacity = m_ncapacity *2
		if (!isFull())
		{
			m_array[m_nLast] = data;
			m_nLast = (m_nLast + 1) % m_ncapacity;

		}
		else
		{
			throw "full Queue";
		}
	}

	template<typename T>
	void CircularQueue<T>::Dequeue()
	{
		if (!IsEmpty())
		{
			//	m_nFront = m_nFront + 1;
			m_nFront = (m_nFront + 1) % m_ncapacity;
		}
		else
		{
			throw "empty Queue";
		}
	}

	template<typename T>
	T& CircularQueue<T>::Front()
	{
		if (IsEmpty())
			throw "empty Queue";

		return m_array[m_nFront];
	}

	template<typename T>
	T CircularQueue<T>::Front() const
	{
		if (IsEmpty())
			throw "empty Queue";

		return m_array[m_nFront];
	}
};

#endif

测试代码


//main.cpp
#include "CircularQueue.h"

using namespace jay;

int main(int argc, char* argv[])
{
	CircularQueue<int> myqueue(10); //声明队列

	int nSize;
	cout << "请输入队列的大小:";
	cin >> nSize;

	cout << "入队列顺序:";
	for (int i=0; i<nSize; i++)
	{
		if (!myqueue.isFull())
		{
			myqueue.Enqueue(i + 1);
			cout << i + 1 << " ";
		}
		else
		{
			cout << endl;
			cout << "Full Queue" << endl;
			break;
		}
	}

	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Enqueue(111);
	myqueue.Enqueue(112);
	myqueue.Enqueue(113);
	myqueue.Enqueue(114);
	myqueue.Enqueue(115);
	myqueue.Enqueue(116);
	myqueue.Enqueue(117);
	myqueue.Enqueue(118);
	myqueue.Enqueue(119);
	myqueue.Dequeue();
	myqueue.Dequeue();
	myqueue.Enqueue(211);
	myqueue.Enqueue(212);

	cout << endl;

	cout << "当前队列的大小:";
	cout << myqueue.Size() << endl;
	cout << "出队列顺序: ";

	while (!myqueue.IsEmpty())
	{
		cout << myqueue.Front() << " ";
		myqueue.Dequeue();
	}

	cout << endl;

	return 0;
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。