队列(Queue) -- C++ 实现


实现了一个大小自动调节的队列

实现代码

// Queue.h
#ifndef QUEUE_H
#define QUEUE_H

#include<iostream>
using namespace std;

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

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

		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>
	Queue<T>::Queue(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>
	Queue<T>::Queue(const Queue<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 < nSize; i++)
		{
			m_array[i] = rhs.m_array[Front];
			Front++;
		}

		m_nFront = 0;
		m_nLast = nSize;
	}

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

			m_ncapacity = rhs.m_ncapacity;
			m_nFront = 0;
			m_nLast = rhs.m_nLast;
			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 <nSize; i++)
			{
				m_array[i] = rhs.m_array[Front];
				Front++;
			}

			m_nFront = 0;
			m_nLast = nSize;
		}

		return *this;
	}

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

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

	template<typename T>
	int Queue<T>::Size() const
	{
		return m_nLast - m_nFront;
	}

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

		}
		else
		{
			T *newarray=new T[ 2*m_ncapacity ];
			if (newarray == NULL)
			{
				throw "Failed to allocate memory!";
			}

			int nSize = Size();
			for (int i = 0; i < nSize; i++)
			{
				newarray[i] = m_array[m_nFront];
				m_nFront++;
			}
			delete [] m_array;
			m_array = newarray;
			m_nFront = 0;
			m_nLast = nSize;

			m_array[m_nLast] = data;
			m_nLast = m_nLast + 1;

			m_ncapacity = 2*m_ncapacity;
		}
	}

	template<typename T>
	void Queue<T>::Dequeue()
	{
		if (!IsEmpty())
		{
			m_nFront = m_nFront + 1;

			if (m_ncapacity > 1024)
			{
				// 当队列Size小于m_ncapacity的1/4时 队列m_ncapacity = m_ncapacity/2
				if (Size() <= m_ncapacity /4)
				{
					T *newarray=new T[ m_ncapacity/2];
					if (newarray == NULL)
					{
						throw "Failed to allocate memory!";
					}

					int nSize = Size();
					for (int i = 0; i < nSize; i++)
					{
						newarray[i] = m_array[m_nFront];
						m_nFront++;
					}
					delete [] m_array;
					m_array = newarray;

					m_nFront = 0;
					m_nLast = nSize;

					m_ncapacity = m_ncapacity/2;
				}
			}

		}
		else
		{
			throw "empty Queue";
		}
	}

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

		return m_array[m_nFront];
	}

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

		return m_array[m_nFront];
	}

};

#endif

测试代码


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

using namespace Jay;

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

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

		cout << "入队列顺序:";
		for (int i=0; i<nSize; i++)
		{
			myqueue.Enqueue(i + 1);
			cout << i + 1 << " ";
		}
		 
		cout << endl;

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

		Queue<int> myqueue2(myqueue);
		while (!myqueue.IsEmpty())
		{
			cout << myqueue.Front() << " ";
			myqueue.Dequeue();
		}

		cout << endl;


	}
	catch (const char* msg)
	{
		cout << msg << endl;
	}

	cout << endl;

	return 0;
}

 

暂无评论

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