Queue 막 구현하기

https://cplusplus.com/reference/queue/queue/

https://cplusplus.com/reference/queue/queue/

 

기능>

1. 생성자: 기본 생성자

2. empty() : 큐가 비어있는지 체크 후 bool 타입 반환

3. size() : 큐에 저장된 데이터 갯수 integer 타입 반환

4. front() : 큐에 가장 처음에 추가한 데이터 반환 (제거 x, 수정 가능)

5. back() : 큐에 가장 마지막에 추가한 데이터 반환 (제거 x, 수정 가능)

6. push() : 큐에 데이터 추가

7. emplace() : 큐에 데이터 추가

8. pop() : 가장 처음에 추가한 데이터 제거

9. swap() : 서로 다른 큐간에 데이터 관리 자료구조 변경

 

※ 더블 링크드 리스트로 구현한 Queue의 경우 모든 데이터를 Heap 메모리에서 관리하도록 하였다.

그전까지는 value의 경우 Stack 메모리 에서 관리되도록 하였는데 이번에는 Heap에 추가하고

Queue 소멸자 호출 시 전부 해제되도록 하였다.

 

 

이번에는 큐를 구현해 보자

저번 스택과 마찬가지로

데이터를 관리하는 자료 구조는 배열과 더블링크드 리스트를 통해서 관리한다.

 

[QueueByArray.h]

배열을 이용해 데이터를 관리한다.

#include <iostream>

template <class T>
class QueueByArray
{
public:
	QueueByArray()
	{
		nLength = 0;
		nCapacity = 2;
		pArr = new T[nCapacity];
	}
	~QueueByArray()
	{
		delete[] pArr;
		pArr = nullptr;
	}
public:
	bool empty()
	{
		return nLength == 0;
	}
	int size()
	{
		return nLength;
	}
	T& front()
	{
		if (nLength == 0)
		{
			printErrMsg("Queue empty!");
			return pArr[nLength];
		}
		return pArr[1];
	}
	T& back()
	{
		if (nLength == 0)
		{
			printErrMsg("Queue empty!");
		}
		return pArr[nLength];
	}
	void push(const T& value)
	{
		if (nLength == nCapacity - 1)
		{
			T* pNewArr = new T[nCapacity * 2];
			for (int i = 0; i < nCapacity; ++i)
			{
				pNewArr[i] = pArr[i];
			}

			nCapacity *= 2;
			delete[] pArr;
			pArr = pNewArr;
		}

		pArr[++nLength] = value;
		return;
	}
	void emplace(const T& value)
	{
		if (nLength == nCapacity - 1)
		{
			T* pNewArr = new T[nCapacity * 2];
			for (int i = 0; i < sizeof(pArr) / sizeof(T*); ++i)
			{
				pNewArr[i] = pArr[i];
			}

			nCapacity *= 2;
			delete[] pArr;
			pArr = pNewArr;
		}

		pArr[++nLength] = value;
		return;
	}
	void pop()
	{
		if (nLength == 0)
		{
			printErrMsg("Queue empty!");
		}
		else
		{
			for (int i = 1; i < nLength; ++i)
			{
				pArr[i] = pArr[i + 1];
			}
			--nLength;
		}
		return;
	}
	void swap(QueueByArray<T>& other)
	{
		T* pTmpArr = pArr;
		int nTmpLength = nLength;
		int nTmpCapacity = nCapacity;

		pArr = other.pArr;
		nLength = other.nLength;
		nCapacity = other.nCapacity;

		other.pArr = pTmpArr;
		other.nLength = nTmpLength;
		other.nCapacity = nTmpCapacity;
		return;
	}

	void printErrMsg(const char* msg)
	{
		std::cout << "ERROR: " << msg << '\n';
		return;
	}
private:
	T* pArr;
	int nLength;
	int nCapacity;
};

 

[QueueByDoubleLinkedList.h]

더블링크드 리스트를 통해 데이터를 관리한다.

#pragma once

#include <iostream>

template <typename T>
struct Node
{
	T* pValue;
	Node<T>* pPrevNode;
	Node<T>* pNextNode;
};

template <class T>
class QueueByDoubleLinkedList
{
public:
	QueueByDoubleLinkedList()
	{
		nLength = 0;
		pHeadNode = new Node<T>();
		pHeadNode->pValue = nullptr;
		pHeadNode->pPrevNode = nullptr;
		pHeadNode->pNextNode = pTailNode;

		pTailNode = new Node<T>();
		pTailNode->pValue = nullptr;
		pTailNode->pPrevNode = pHeadNode;
		pTailNode->pNextNode = nullptr;
	}

	~QueueByDoubleLinkedList()
	{
		Node<T>* pCurNode = pHeadNode;
		while (pCurNode != nullptr)
		{
			Node<T>* pDelNode = pCurNode;
			pCurNode = pCurNode->pNextNode;
			delete pDelNode->pValue;
			delete pDelNode;
		}
	}

public:
	bool empty()
	{
		return nLength == 0;
	}

	int size()
	{
		return nLength;
	}

	T& front()
	{
		Node<T>* pCurNode;
		if (nLength == 0)
		{
			printErrMsg("Queue empty!");
			pCurNode = pHeadNode;
		}
		else
		{
			pCurNode = pHeadNode->pNextNode;
		}

		return *(pCurNode->pValue);
	}

	T& back()
	{
		Node<T>* pCurNode;
		if (nLength == 0)
		{
			printErrMsg("Queue empty!");
			pCurNode = pTailNode;
		}
		else
		{
			pCurNode = pTailNode->pPrevNode;
		}

		return *(pCurNode->pValue);
	}

	void push(const T& value)
	{
		Node<T>* pCurNode = pTailNode->pPrevNode;
		Node<T>* pNewNode = new Node<T>();
		pNewNode->pValue = new T(value);

		pCurNode->pNextNode = pNewNode;
		pNewNode->pPrevNode = pCurNode;

		pNewNode->pNextNode = pTailNode;
		pTailNode->pPrevNode = pNewNode;

		++nLength;
		return;
	}

	void emplace(const T& value)
	{
		Node<T>* pCurNode = pTailNode->pPrevNode;
		Node<T>* pNewNode = new Node<T>();
		pNewNode->pValue = new T(value);

		pCurNode->pNextNode = pNewNode;
		pNewNode->pPrevNode = pCurNode;

		pNewNode->pNextNode = pTailNode;
		pTailNode->pPrevNode = pNewNode;

		++nLength;
		return;
	}

	void pop()
	{
		if (nLength == 0)
		{
			printErrMsg("Queue empty!");
		}
		else
		{
			Node<T>* pDelNode = pHeadNode->pNextNode;
			Node<T>* pNextNode = pDelNode->pNextNode;

			pHeadNode->pNextNode = pNextNode;
			pNextNode->pPrevNode = pHeadNode;

			delete pDelNode->pValue;
			delete pDelNode;

			--nLength;
		}
		
		return;
	}

	void swap(QueueByDoubleLinkedList<T>& other)
	{
		Node<T>* pTmpHeadNode = pHeadNode;
		Node<T>* pTmpTailNode = pTailNode;
		int nTmpLength = nLength;

		pHeadNode = other.pHeadNode;
		pTailNode = other.pTailNode;
		nLength = other.nLength;

		other.pHeadNode = pTmpHeadNode;
		other.pTailNode = pTmpTailNode;
		other.nLength = nTmpLength;
		return;
	}

	void printErrMsg(const char* msg)
	{
		std::cout << "ERROR: " << msg << '\n';
		return;
	}

private:
	Node<T>* pHeadNode;
	Node<T>* pTailNode;
	int nLength;
};

 

[Main.cpp]

#include "QueueByArray.h"
#include "QueueByDoubleLinkedList.h"

int main(int argc, char* argv[])
{
	QueueByDoubleLinkedList<int> myqueue1;
	QueueByDoubleLinkedList<int> myqueue2;

	myqueue1.push(10);
	myqueue1.push(20);
	myqueue1.push(30);
	myqueue1.push(40);
	myqueue1.push(50);

	myqueue2.push(100);
	myqueue2.push(200);
	myqueue2.push(300);
	myqueue2.push(400);
	myqueue2.push(500);
	myqueue2.push(600);
	myqueue2.push(700);
	myqueue2.push(800);
	myqueue2.push(900);

	std::cout << "myqueue1 size: " << myqueue1.size() << '\n';
	std::cout << "myqueue2 size: " << myqueue2.size() << '\n';

	myqueue1.front() = 99999;
	myqueue1.back() = 88888;
	std::cout << "myqueue1 front: " << myqueue1.front() << '\n';
	std::cout << "myqueue1 back: " << myqueue1.back() << '\n';


	std::cout << "myqueue2 front: " << myqueue2.front() << '\n';
	std::cout << "myqueue2 back: " << myqueue2.back() << '\n';

	myqueue1.pop();
	myqueue1.pop();
	myqueue1.pop();

	myqueue1.swap(myqueue2);
	std::cout << "myqueue1 size: " << myqueue1.size() << '\n';
	std::cout << "myqueue2 size: " << myqueue2.size() << '\n';

	while (!myqueue1.empty())
	{
		std::cout << "myqueue front: " << myqueue1.front() << '\n';
		myqueue1.pop();
	}

	std::cout << "myqueue1 size: " << myqueue1.size() << '\n';
	std::cout << "myqueue2 size: " << myqueue2.size() << '\n';

	return 0;
}

 

[실행 화면]

 

단순하게 기능 동작만 구현 해보았는데

이전에 구현해보았던 스택과 공통적인 부분이 많다.

그래서 c++ STL 에서는 기본 컨테이너(underlying containe)를 두고

이를 확장한 자료구조들이 존재하나 보다~