[C++] Queue 직접 구현

<연결 리스트로 Queue 구현>

//LinkedList Queue
#include <iostream> 
using namespace std;

template <typename T>
class Queue
{
public:
	struct Node
	{
		T data;
		Node* next;
		Node(T _data)
		{
			data = _data;
			next = nullptr;
		}
	};
	Queue() :mHead(nullptr) {}
	~Queue() {}
	void Push_back(T value)
	{
		Node* t = new Node(value);
		if (mHead == nullptr)
			mHead = t;
		else
		{
			Node* p = mHead;
			for (p; p->next != nullptr; p = p->next) {}
			p->next = t;
		}
	}
	void Push_front(T value)
	{
		Node* t = new Node(value);
		if (mHead == nullptr)
			mHead = t;
		else
		{
			t->next = mHead;
			mHead = t;
		}
	}
	void Pop()
	{
		if (mHead == nullptr)
			return;

		Node* p = mHead;
		mHead = p->next;
		delete p;
	}
	int Size()
	{
		int cnt = 0;
		Node* t = mHead;
		for (t; t != nullptr; t = t->next)
		{
			cnt++;
		}
		return cnt;
	}
	void Front()
	{
		cout << mHead->data << '\n';
	}
	void Back()
	{
		Node* mTail = mHead;
		for (; mTail->next != nullptr; mTail = mTail->next) {}
		cout << mTail->data << '\n';
	}
	bool Empty()
	{
		if (Size() == 0)
			return true;
		else
			return false;
	}
	void Print()
	{
		Node* t = mHead;
		for (; t != nullptr; t = t->next)
		{
			cout << t->data << ' ';
		}
		cout << '\n';
	}

private:
	Node* mHead;
};

int main()
{
	Queue<int> q;
	q.Push_back(5);
	q.Push_back(3);
	q.Push_back(2);
	q.Front();	//5
	q.Push_front(6);	//6 5 3 2
	q.Print();
	cout << q.Empty() << '\n';	//0 (비어있지않음)
	q.Front();	//6
	q.Back();	//2
	cout << q.Size() << '\n';	//4
	q.Pop();
	q.Pop();
	q.Pop();
	q.Pop();
	cout << q.Size() << '\n';	//0
	cout << q.Empty() << '\n';	//1 (비어있음)

	return 0;
}

 

<배열로 Queue 구현>

//Array Queue
#include<iostream>
using namespace std;

template <typename T> 
class Queue
{
public:
	Queue() : mHead(0), mTail(0), mSize(3), mArr(new T[mSize]{}) {}
	void Enqueue(T data) 
	{
		mArr[mTail] = data;
		mTail = (mTail + 1) % mSize;

		if (mTail == mHead) 
		{
			T* newArr = new T[mSize * 2]{};
			T* t = mArr;
			for (int i = 0; i < mSize; i++)
				newArr[i] = mArr[(mHead + i) % mSize];
			mArr = newArr;
			delete t;

			mHead = 0;
			mTail = mSize;
			mSize *= 2;
		}
	}
	T Front() 
	{
		return mArr[mHead];
	}
	void Dequeue() 
	{
		mArr[mHead++] = 0;
	}
	void Print() 
	{
		for (int i = mHead; i < mTail; i++)
			cout << mArr[i] << " ";
		cout << "\n";
	}
	int Size()
	{
		return mTail - mHead;
	}
	bool Empty()
	{
		if (Size() == 0)
			return true;
		else
			return false;
	}

private:
	int mHead, mTail, mSize;
	T* mArr;
};
int main() 
{
	Queue<int> q;
	q.Enqueue(5);
	q.Enqueue(3);
	q.Enqueue(2);
	q.Enqueue(1);
	cout << q.Size() << '\n';
	q.Print();
	q.Dequeue();
	q.Dequeue();
	q.Dequeue();
	q.Print();
	q.Enqueue(2);
	q.Enqueue(2);
	q.Enqueue(2);
	q.Enqueue(2);
	q.Enqueue(2);
	q.Enqueue(2);
	q.Print();
	q.Dequeue();
	q.Print();

	return 0;
}