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

스택 다음으로 구현할 자료구조는 Queue다.

사실 STL 문서를 뒤적이다가 알게 된 것인데, Stack과 Queue는 사실 뒤에 나올 Deque를 통해 구현된 어댑터 패턴이 적용된 클래스이다. 

기본 구현은 이미 Deque를 통해 구현되어 있지만, 메서드 hiding을 통해 필요한 부분만 사용자에게 노출시키는 전략을 사용한다.

하지만 우리는 다시 구현하는 입장이기 때문에 우선 Stack과 Queue를 구현한 뒤, Deque를 구현하고 나서 어댑터를 통해 Stack과 Queue 클래스를 수정하도록 하겠다.

Queue

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

📌 구현 목표

• 본 글에서는 Queue(큐) 자료구조를 직접 구현
• 템플릿 기반으로 자료형에 독립적인 구조를 구성
• 내부적으로는 동적 배열을 사용하여 크기 확장(reallocation)을 지원
• 다음 주요 연산 지원
  • Push(Enqueue), Pop(Dequeue) : O(1) / 재할당 시 O(n)
  • Front, Back : O(1)
  • Empty, Size : O(1)
  • Clear : O(1)
• 복사 생성자와 대입 연산자를 통한 얕은 복사 방지(Deep Copy)도 고려
• 원형 큐 구조를 통해 메모리 효율성 개선

🧱 프로젝트 구조

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

/자료구조
 ├── #1.Linear_Data_Structures/
 │    ├── Linear_Data_Structures.h      // 통합 헤더
 │    └── 1_Stack/Stack.h               // Stack 템플릿 정의
 │    └── 2_1_Queue/Queue.h             // Queue 템플릿 정의
 ├── #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"

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

int main(int argc, char* argv[])
{
	// Stack example usage
	/*
	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
	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;

	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"

#1.Linear_Data_Structures/2_1_Queue/Queue.h

#pragma once

namespace Linear_Data_Structures
{
	// Queue class definition
	template<typename T>
	class Queue
	{
	public:
		Queue(int initialCapacity = 16) 
			: front(0), back(-1), size(0), capacity(initialCapacity)
		{
			data = new T[capacity];
		}

		// DeepCopy constructor, ensuring a new array is allocated
		Queue(const Queue& other)
			: front(other.front), back(other.back), size(other.size), capacity(other.capacity)
		{
			data = new T[capacity];
			for (int i = 0; i < size; ++i)
				data[i] = other.data[(front + i) % capacity];
		}
		
		~Queue()
		{
			delete[] data;
		}

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

		// modified methods
		void Push(const T& value);	// Enqueue
		void Pop();					// Dequeue

		// accessor methods
		T& Front();
		const T& Front() const;
		T& Back();
		const T& Back() const;

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

		// custom methods
		void Clear();

	private:
		T* data;
		int front;
		int back;
		int size;
		int capacity;
	};

	template<typename T>
	inline void Queue<T>::Push(const T& value)
	{
		if (size + 1 >= capacity)
		{
			// reallocate memory
			int oldCapacity = capacity;
			capacity *= 2;
			T* newData = new T[capacity];
			for (int i = 0; i < size; ++i)
			{
				newData[i] = data[(front + i) % oldCapacity];	// front 앞으로 당기기
			}
			front = 0;
			back = size - 1;

			delete[] data;
			data = newData;
		}
		back = (back + 1) % capacity;
		data[back] = value;
		size++;
	}

	template<typename T>
	inline void Queue<T>::Pop()
	{
		if (size > 0)
		{
			front = (front + 1) % capacity;
			size--;
		}
	}

	template<typename T>
	inline T& Queue<T>::Front()
	{
		return data[front];
	}

	template<typename T>
	inline const T& Queue<T>::Front() const
	{
		return data[front];
	}

	template<typename T>
	inline T& Queue<T>::Back()
	{
		return data[back];
	}

	template<typename T>
	inline const T& Queue<T>::Back() const
	{
		return data[back];
	}

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

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

	template<typename T>
	inline void Queue<T>::Clear()
	{
		front = 0;
		back = -1;
		size = 0;
	}
}

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

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

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

 

 

 

 

 

※ 25.08.06 수정사항

STL에 맞도록 자료형 Empty() == true 일 때 아무것도 안함

==> 모든 함수에서 예외처리 구문 삭제