隊列模拟實作

隊列的特點：

先進先出/後進後出

隊列的常見操作：

Push——往隊尾插入一個元素

Pop——從隊頭删除一個元素

Front——傳回隊列的第一個元素

Back——傳回隊列的最後一個元素

Size——求隊列的元素個數

Empty——判斷隊列是否為空

隊列的模拟實作：

#include<assert.h>

template<class T>
struct QueueNode
{
	T _data;
	QueueNode<T>* _next;

	QueueNode(const T& data)
		: _data(data)
		, _next(NULL)
	{}
};

template<class T>
class Queue
{
	typedef QueueNode<T> Node;
public:
	Queue()		//構造函數
		: _head(NULL)
		, _tail(NULL)
	{}

	~Queue()		//析構函數
	{
		Node* cur = _head;
		while (cur)
		{
			Node* del = cur;
			cur = cur->_next;
			delete del;
		}
	}

	void Push(const T& data)	//在末尾插入一個數
	{
		if (_head == NULL)		//為空
		{
			_head = _tail = new Node(data);
		}
		else      //不為空
		{
			_tail->_next = new Node(data);
			_tail = _tail->_next;
		}
	}

	void Pop()					//删除第一個元素
	{
		if (_head == _tail)	//隻有一個元素時
		{
			delete _head;
			_head = _tail = NULL;
		}
		else               //有多個元素時
		{
			Node* del = _head;
			_head = _head->_next;

			delete del;
		}
	}

	size_t Size()	//傳回隊列中元素的個數
	{
		size_t count = 0;
		Node* cur = _head;
		while (cur)
		{
			++count;
			cur = cur->_next;
		}
		return count;
	}

	T& Front()	//傳回隊列中的第一個元素
	{
		assert(_head);
		return _head->_data;
	}

	T& Back()	//傳回隊列的最後一個元素
	{
		assert(_tail);
		return _tail->_data;
	}

	bool Empty()	//判斷一個隊列是否為空
	{
		return _head == NULL;
	}

protected:
	Node* _head;
	Node* _tail;
};


void TestQueue()
{
	Queue<int> q;
	q.Push(1);
	q.Push(2);
	q.Push(3);
	q.Push(4);
	q.Push(5);

	cout << q.Size() << endl;
	while (!q.Empty())
	{
		cout << q.Front() << " ";
		q.Pop();
	}
	cout << endl;
}

#include<iostream>
using namespace std;
#include "queue.h"

int main()
{
	TestQueue();
	system("pause");
	return 0;
}
           

代碼運作結果：