C++로 다시 구현하는 선형 자료구조 #1-4 Priority Queue

마지막으로 구현할 선형 자료구조는 우선순위 큐이다.

우선 순위 큐는 기본적으로 비 선형 자료구조인 Heap을 응용하여 만들어진 자료구조다. 

그런데 캐시 친화성을 살짝 고려하자면 이차원 배열 또는 청크 기반 포인터 배열을 통해 같은 우선순위를 갖는 자료형 끼리는 캐시 친화도를 높여 캐시 친화성을 높여줄 수 있다. 

우선 이 글에서는 STL에 맞도록 Heap을 기반으로 작성하고, 이 다음 글에서 올 Chunk - Based-Deque를 구현한 후 vector의 어댑터 클래스로 변형하여 구현해보도록 하겠다.

PriorityQueue

우선순위 큐는 선입선출의 기능을 갖고 있는 자료구조이다.

기존 큐와는 다르게 자료에 우선순위가 부여되어 우선순위에 따라 출력 순서가 제어된다. 

📌 구현 목표

• 본 글에서는 Priority Queue(우선순위 큐) 자료구조를 직접 구현
• 템플릿 기반으로 자료형에 독립적인 구조를 구성
• 내부적으로는 동적 구조체 배열을 사용하여 크기 확장(reallocation)을 지원
• 다음 주요 연산 지원
  • Push : O(logN)
  • Pop : O(logN)
  • Top : O(1)
  • Empty, Size
  • Clear
• 복사 생성자와 대입 연산자를 통한 얕은 복사 방지(Deep Copy)도 고려
• 힙 구조를 통해 삽입, 삭제 효율성 유지
• 구조체 배열을 사용해 우선순위 부여

🧱 프로젝트 구조

• PriorityQueue은 Linear_Data_Structures 네임스페이스에 포함되어 있습니다.
• 전체 프로젝트는 다음과 같은 구조를 가집니다:

/자료구조
 ├── #1.Linear_Data_Structures/
 │    ├── Linear_Data_Structures.h      	// 통합 헤더
 │    └── 1_Stack/Stack.h               	// Stack 템플릿 정의
 │    └── 2_1_Queue/Queue.h             	// Queue 템플릿 정의
 │    └── 2_2_Deque/Deque.h             	// Deque 템플릿 정의
 │    └── 2_2_PriorityQueue/PriorityQueue.h	// PriorityQueue 템플릿 정의
 ├── #2.Non_Linear_Data_Structures/
 │    └── Non_Linear_Data_Structures.h  	// 통합 헤더
 └── main.cpp                           	// 테스트 메인 함수

프로그램 구성은 다음과 같다.

main.cpp

#include <iostream>
#include <string>
#include "#1.Linear_Data_Structures/Linear_Data_Structures.h"
#include "#2.Non_Linear_Data_Structures/Non_Linear_Data_Structures.h"
#include "TestFunctions.h"


using namespace Linear_Data_Structures;
/// <summary>
/// 메인 애플리케이션 진입점 클래스
/// </summary>
/// <param name="argc"></param>
/// <param name="argv"></param>
/// <returns></returns>
/// 

int main(int argc, char* argv[])
{
	// PriorityQueue example usage
	PriorityQueue<int> priorityQueue;
	priorityQueue.Push(1, 100);
	priorityQueue.Push(2, 200);
	priorityQueue.Push(3, 300);
	std::cout << "Priority Queue Top: " << priorityQueue.Top() << '\n'
		<< "Priority Queue Size : " << priorityQueue.Size() << std::endl;
	priorityQueue.Pop();
	std::cout << "After Pop, Priority Queue Top: " << priorityQueue.Top() << '\n'
		<< "Priority Queue Size : " << priorityQueue.Size() << std::endl;
	priorityQueue.Clear();
	std::cout << "Priority Queue is Cleared: " << std::endl;
	PriorityQueue<std::string> stringPriorityQueue;
	stringPriorityQueue.Push(1, "High");
	stringPriorityQueue.Push(2, "Medium");
	stringPriorityQueue.Push(3, "Low");
	std::cout << "String Priority Queue Top: " << stringPriorityQueue.Top() << '\n'
		<< "String Priority Queue Size : " << stringPriorityQueue.Size() << std::endl;
	stringPriorityQueue.Clear();
	std::cout << "String Priority Queue is Cleared: " << std::endl;
	
	return 0;
}

#1.Linear_Data_Structures/Linear_Data_Structures.h

#pragma once

#include "1_Stack/Stack.h"
#include "2_1_Queue/Queue.h"
#include "2_2_Deque/Deque.h"
#include "2_3_PriorityQueue/PriorityQueue.h"

#1.Linear_Data_Structures/2_2_Deque/Deque.h

#pragma once

#include <iostream>

namespace Linear_Data_Structures
{
	template<typename T>
	struct PriorityQueueNode
	{
		T data;
		int priority;

		PriorityQueueNode()
			: priority(0), data(T())
		{
		}

		PriorityQueueNode(int priority, const T& value)
			: priority(priority), data(value)
		{}

		friend bool operator<(const PriorityQueueNode& left, const PriorityQueueNode& right)
		{
			return left.priority < right.priority;
		}

		friend std::ostream& operator<<(std::ostream& os, const PriorityQueueNode& node)
		{
			return os << '{' << node.priority << ", '" << node.data << "'}";
		}
	};

	// PriorityQueue class definition
	template<typename T>
	class PriorityQueue
	{
	public:
		PriorityQueue(int initialCapacity = 16)
			: capacity(initialCapacity), size(0)
		{
			data = new PriorityQueueNode<T>[capacity];
		}

		// DeepCopy constructor, ensuring a new array is allocated
		PriorityQueue(const PriorityQueue& other)
			: capacity(other.capacity), size(other.size)
		{
			data = new PriorityQueueNode<T>[capacity];
			for (int i = 0; i < size; ++i)
			{
				data[i] = other.data[i];
			}
		}

		PriorityQueue& operator=(const PriorityQueue& other)
		{
			if (this != &other)
			{
				delete[] data;
				size = other.size;
				capacity = other.capacity;
				data = new PriorityQueueNode<T>[capacity];
				for (int i = 0; i < size; ++i)
				{
					data[i] = other.data[i];
				}
			}
			return *this;
		}

		~PriorityQueue()
		{
			delete[] data;
		}

		// modified methods
		void Push(int priority = 0, const T& value = T());
		void Pop();

		// accessor methods
		T& Top();
		const T& Top() const;

		// capacity methods
		bool Empty() const;
		int Size() const;

		// Custom methods
		void Clear();

	private:
		PriorityQueueNode<T>* data;
		int size;
		int capacity;
	};

	template<typename T>
	void PriorityQueue<T>::Push(int priority, const T& value)
	{
		if (size >= capacity)
		{
			// Reallocate memory
			int oldCapacity = capacity;
			capacity *= 2;
			PriorityQueueNode<T>* newData = new PriorityQueueNode<T>[capacity];
			for (int i = 0; i < size; ++i)
			{
				newData[i] = data[i]; // Copy existing nodes
			}
			delete[] data;
			data = newData;
		}

		// Insert the new node
		data[size] = PriorityQueueNode<T>(priority, value); // Default priority 0
		int current = size++;

		while (current > 0)
		{
			int parent = (current - 1) / 2;
			if (data[parent] < data[current])
			{
				std::swap(data[parent], data[current]);
				current = parent;
			}
			else
			{
				break;
			}
		}
	};

	template<typename T>
	void PriorityQueue<T>::Pop()
	{
		if (size == 0)
		{
			return;
		}

		int current = 0;
		data[0] = data[--size]; // Move the last element to the root
		
		while (true)
		{
			int leftChild = 2 * current + 1;
			int rightChild = 2 * current + 2;
			int largest = current;

			if (leftChild < size && data[largest] < data[leftChild])
			{
				largest = leftChild;
			}

			if (rightChild < size && data[largest] < data[rightChild])
			{
				largest = rightChild;
			}

			if (largest == current)
			{
				break;
			}

			std::swap(data[current], data[largest]);
			current = largest;
		}
	}

	template<typename T>
	T& PriorityQueue<T>::Top()
	{
		return data[0].data;
	}

	template<typename T>
	const T& PriorityQueue<T>::Top() const
	{
		return data[0].data;
	}

	template<typename T>
	bool PriorityQueue<T>::Empty() const
	{
		return size == 0;
	}

	template<typename T>
	int PriorityQueue<T>::Size() const
	{
		return size;
	}

	template<typename T>
	void PriorityQueue<T>::Clear()
	{
		delete[] data;
		data = new PriorityQueueNode<T>[capacity];
		size = 0;
	}
}

실습 코드는 제 깃허브에 있습니다.

Workspace/자료구조 at main · cyphen156/Workspace

Workspace/자료구조 at main · cyphen156/Workspace

 

 

 

 

 

※ 25.08.07 수정사항

이제부터 테스트용 코드는 main.cpp에서는 호출만함

실제 코드는 TestFuncions.cpp에서 작성

#include <iostream>
#include <string>
#include "#1.Linear_Data_Structures/Linear_Data_Structures.h"
#include "#2.Non-linear_Data_Structures/Non-linear_Data_Structures.h"
#include "TestFunctions.h"


using namespace Linear_Data_Structures;
/// <summary>
/// 메인 애플리케이션 진입점 클래스
/// </summary>
/// <param name="argc"></param>
/// <param name="argv"></param>
/// <returns></returns>
/// 

int main(int argc, char* argv[])
{
	testPriorityQueue();
	
	return 0;
}

TestFuncions.cpp

#include "TestFunctions.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include "#1.Linear_Data_Structures/Linear_Data_Structures.h"
#include "#2.Non-linear_Data_Structures/Non-linear_Data_Structures.h"

using namespace Linear_Data_Structures;
/// <summary>
/// 테스트 함수 모음집
/// </summary>

// Stack example usage
void testStack()
{
	Stack<int> stack;
	stack.Push(10);
	stack.Push(20);
	std::cout << "Stack top: " << stack.Top() << '\n'
		<< "Stack Size : " << stack.Size() << std::endl;
	stack.Pop();
	std::cout << "After Pop, Stack top: " << stack.Top() << '\n'
		<< "Stack Size : " << stack.Size() << std::endl;
	stack.Clear();
	std::cout << "Stack is Cleared: " << std::endl;

	Stack<std::string> stringStack;
}

// queue example usage
void testQueue()
{
	Queue<int> queue;
	queue.Push(30);
	queue.Push(40);
	std::cout << "Queue front: " << queue.Front() << '\n'
		<< "Queue Size : " << queue.Size() << std::endl;
	queue.Pop();
	std::cout << "After Pop, Queue front: " << queue.Front() << '\n'
		<< "Queue Size : " << queue.Size() << std::endl;
	queue.Clear();
	std::cout << "Queue is Cleared: " << std::endl;

	Queue<std::string> stringQueue;
	stringQueue.Push("Hello");
	stringQueue.Push("World");
	std::cout << "Queue Back: " << stringQueue.Back() << '\n'
		<< "Queue Size : " << stringQueue.Size() << std::endl;
	stringQueue.Clear();
	std::cout << "String Queue is Cleared: " << std::endl;
}

// Deque example usage
void testDeque()
{
	Deque<int> deque;
	deque.PushFront(50);
	deque.PushBack(60);
	std::cout << "Deque Front: " << deque.Front() << '\n'
		<< "Deque Back: " << deque.Back() << '\n'
		<< "Deque Size : " << deque.Size() << std::endl;
	deque.PopFront();
	std::cout << "After PopFront, Deque Front: " << deque.Front() << '\n'
		<< "Deque Size : " << deque.Size() << std::endl;
	deque.PopBack();
	std::cout << "After PopBack, Deque Back: " << deque.Back() << '\n'
		<< "Deque Size : " << deque.Size() << std::endl;
	deque.Clear();
	std::cout << "Deque is Cleared: " << std::endl;

	Deque<std::string> stringDeque;
	stringDeque.PushFront("Deque");
	stringDeque.PushBack("Example");
	std::cout << "String Deque Front: " << stringDeque.Front() << '\n'
		<< "String Deque Back: " << stringDeque.Back() << '\n'
		<< "String Deque Size : " << stringDeque.Size() << std::endl;

	stringDeque.PopFront();
	std::cout << "After PopFront, String Deque Front: " << stringDeque.Front() << '\n'
		<< "String Deque Size : " << stringDeque.Size() << std::endl;
}

// PriorityQueue example usage
void testPriorityQueue()
{
	PriorityQueue<int> priorityQueue;
	priorityQueue.Push(1, 100);
	priorityQueue.Push(2, 200);
	priorityQueue.Push(3, 300);
	std::cout << "Priority Queue Top: " << priorityQueue.Top() << '\n'
		<< "Priority Queue Size : " << priorityQueue.Size() << std::endl;
	priorityQueue.Pop();
	std::cout << "After Pop, Priority Queue Top: " << priorityQueue.Top() << '\n'
		<< "Priority Queue Size : " << priorityQueue.Size() << std::endl;
	priorityQueue.Clear();
	std::cout << "Priority Queue is Cleared: " << std::endl;
	PriorityQueue<std::string> stringPriorityQueue;
	stringPriorityQueue.Push(1, "High");
	stringPriorityQueue.Push(2, "Medium");
	stringPriorityQueue.Push(3, "Low");
	std::cout << "String Priority Queue Top: " << stringPriorityQueue.Top() << '\n'
		<< "String Priority Queue Size : " << stringPriorityQueue.Size() << std::endl;
	stringPriorityQueue.Clear();
	std::cout << "String Priority Queue is Cleared: " << std::endl;
}

void testChunkBasedDeque()
{
}

void testAdaptorStack()
{
}

void testAdaptorQueue()
{
}

void testAdaptorPriorityQueue()
{
}

TestFuncions.h

#pragma once

// Linear Data Structures Test
void testStack();
void testQueue();
void testDeque();
void testPriorityQueue();
void testChunkBasedDeque();
void testAdaptorStack();
void testAdaptorQueue();
void testAdaptorPriorityQueue();


// Non-linear Data Structures Test