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

선형 자료구조 중 꽃이라 할 수 있는 Deque다. 

앞서 글에서 보았듯 STL에서는 Deque를 통해 Stack과 Queue를 구현한다.

이 작업이 끝나면 Deque의 자료형을 단순 1차원 배열에서 Chunk Base Block을 통해 더 빠른 인덱싱이 가능하도록 수정하고, Stack과 Queue를 어댑터 클래스로 적용한다.

Deque(Double-Ended Queu)

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

큐와는 다르게 자료의 입출력이 자료구조의 앞과 뒤 모두에서 일어날 수 있다. 

📌 구현 목표

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

🧱 프로젝트 구조

• Deque은 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.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;
	*/

	// Deque example usage
	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;

	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_2_Deque/Deque.h

#pragma once

namespace Linear_Data_Structures
{
	// Deque class definition
	template<typename T>
	class Deque
	{
	public:
		Deque(int initialCapacity = 16)
			: capacity(initialCapacity), front(0), back(-1), size(0)
		{
			data = new T[capacity];
		}
		// DeepCopy constructor, ensuring a new array is allocated
		Deque(const Deque& other)
			: capacity(other.capacity), front(other.front), back(other.back), size(other.size)
		{
			data = new T[capacity];
			for (int i = 0; i < size; ++i)
				data[(front + i) % capacity] = other.data[(other.front + i) % other.capacity];
		}
		Deque& operator=(const Deque& other)
		{
			if (this != &other)
			{
				delete[] data;
				capacity = other.capacity;
				size = other.size;
				front = other.front;
				back = other.back;
				data = new T[capacity];
				for (int i = 0; i < size; ++i)
				{
					data[(front + i) % capacity] = other.data[(other.front + i) % other.capacity];
				}
			}
			return *this;
		}
		~Deque()
		{
			delete[] data;
		}
	private:
		T* data;
		int capacity;
		int front;
		int back;
		int size;

	public:
		void PushFront(const T& value);
		void PushBack(const T& value);
		
		void PopFront();
		void PopBack();
		T& Front();
		const T& Front() const;
		T& Back();
		const T& Back() const;

		bool Empty() const;
		int Size() const;;

		void Clear();
	};

	template<typename T>
	inline void Deque<T>::PushFront(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;

			delete[] data;
			data = newData;
		}

		front = (front - 1 + capacity) % capacity;
		data[front] = value;
		size++;
	}

	template<typename T>
	inline void Deque<T>::PushBack(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 Deque<T>::PopFront()
	{
		if (!Empty())
		{
			front = (front + 1) % capacity;
			size--;
		}
	}

	template<typename T>
	inline void Deque<T>::PopBack()
	{
		if (!Empty())
		{
			back = (back - 1 + capacity) % capacity;
			size--; 
		}
	}

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

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

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

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

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

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

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

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

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

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