제네릭 데이터 구조 구현

실습 개요 및 목표

이 실습의 목표는 C++ 템플릿을 사용하여 재사용 가능한 제네릭 데이터 구조를 구현하는 것입니다.

우리는 다음과 같은 기본적인 데이터 구조를 구현할 것입니다.

동적 배열 (Vector)
연결 리스트 (Linked List)
스택 (Stack)
큐 (Queue)

이 실습을 통해 다음과 같은 학습 목표를 달성할 수 있습니다.

템플릿을 사용한 제네릭 프로그래밍의 실제 응용
기본적인 데이터 구조의 내부 작동 원리 이해
효율적인 메모리 관리 및 예외 처리 방법 학습
객체 지향 프로그래밍과 제네릭 프로그래밍의 결합

동적 배열 (Vector) 구현

동적 배열은 크기가 동적으로 조절되는 배열입니다.

요소를 추가하거나 제거할 때 자동으로 크기가 조절됩니다.

Vector 클래스 템플릿 정의

#include <iostream>
#include <stdexcept>
 
template <typename T>
class Vector {
private:
    T* arr;
    size_t capacity;
    size_t length;
 
public:
    Vector();
    ~Vector();
    void push_back(const T& value);
    void pop_back();
    T& operator[](size_t index);
    const T& operator[](size_t index) const;
    size_t size() const;
    bool empty() const;
 
private:
    void resize();
};

Vector 멤버 함수 구현

template <typename T>
Vector<T>::Vector() : arr(new T[1]), capacity(1), length(0) {}
 
template <typename T>
Vector<T>::~Vector() {
    delete[] arr;
}
 
template <typename T>
void Vector<T>::push_back(const T& value) {
    if (length == capacity) {
        resize();
    }
    arr[length++] = value;
}
 
template <typename T>
void Vector<T>::pop_back() {
    if (empty()) {
        throw std::out_of_range("Vector is empty");
    }
    --length;
}
 
template <typename T>
T& Vector<T>::operator[](size_t index) {
    if (index >= length) {
        throw std::out_of_range("Index out of range");
    }
    return arr[index];
}
 
template <typename T>
const T& Vector<T>::operator[](size_t index) const {
    if (index >= length) {
        throw std::out_of_range("Index out of range");
    }
    return arr[index];
}
 
template <typename T>
size_t Vector<T>::size() const {
    return length;
}
 
template <typename T>
bool Vector<T>::empty() const {
    return length == 0;
}
 
template <typename T>
void Vector<T>::resize() {
    capacity *= 2;
    T* newArr = new T[capacity];
    for (size_t i = 0; i < length; i++) {
        newArr[i] = arr[i];
    }
    delete[] arr;
    arr = newArr;
}

Vector 사용 예시

int main() {
    Vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
 
    std::cout << "Vector contents: ";
    for (size_t i = 0; i < vec.size(); i++) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
 
    vec.pop_back();
    std::cout << "After pop_back: ";
    for (size_t i = 0; i < vec.size(); i++) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

연결 리스트 (Linked List) 구현

연결 리스트는 각 노드가 데이터와 다음 노드에 대한 포인터를 가지는 선형 데이터 구조입니다.

LinkedList 클래스 템플릿 정의

template <typename T>
class LinkedList {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& d) : data(d), next(nullptr) {}
    };
 
    Node* head;
    size_t size;
 
public:
    LinkedList();
    ~LinkedList();
    void push_front(const T& value);
    void push_back(const T& value);
    void pop_front();
    T& front();
    const T& front() const;
    bool empty() const;
    size_t length() const;
    void clear();
    void print() const;
};

LinkedList 멤버 함수 구현

template <typename T>
LinkedList<T>::LinkedList() : head(nullptr), size(0) {}
 
template <typename T>
LinkedList<T>::~LinkedList() {
    clear();
}
 
template <typename T>
void LinkedList<T>::push_front(const T& value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    head = newNode;
    ++size;
}
 
template <typename T>
void LinkedList<T>::push_back(const T& value) {
    Node* newNode = new Node(value);
    if (empty()) {
        head = newNode;
    } else {
        Node* current = head;
        while (current->next) {
            current = current->next;
        }
        current->next = newNode;
    }
    ++size;
}
 
template <typename T>
void LinkedList<T>::pop_front() {
    if (empty()) {
        throw std::out_of_range("List is empty");
    }
    Node* temp = head;
    head = head->next;
    delete temp;
    --size;
}
 
template <typename T>
T& LinkedList<T>::front() {
    if (empty()) {
        throw std::out_of_range("List is empty");
    }
    return head->data;
}
 
template <typename T>
const T& LinkedList<T>::front() const {
    if (empty()) {
        throw std::out_of_range("List is empty");
    }
    return head->data;
}
 
template <typename T>
bool LinkedList<T>::empty() const {
    return size == 0;
}
 
template <typename T>
size_t LinkedList<T>::length() const {
    return size;
}
 
template <typename T>
void LinkedList<T>::clear() {
    while (!empty()) {
        pop_front();
    }
}
 
template <typename T>
void LinkedList<T>::print() const {
    Node* current = head;
    while (current) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

LinkedList 사용 예시

int main() {
    LinkedList<int> list;
    list.push_back(1);
    list.push_back(2);
    list.push_front(0);
 
    std::cout << "List contents: ";
    list.print();
 
    std::cout << "Front element: " << list.front() << std::endl;
    list.pop_front();
 
    std::cout << "After pop_front: ";
    list.print();
 
    return 0;
}

스택 (Stack) 구현

스택은 LIFO (Last In First Out) 원칙을 따르는 자료구조입니다.

Stack 클래스 템플릿 정의

template <typename T>
class Stack {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& d) : data(d), next(nullptr) {}
    };
 
    Node* top;
    size_t size;
 
public:
    Stack();
    ~Stack();
    void push(const T& value);
    void pop();
    T& peek();
    const T& peek() const;
    bool empty() const;
    size_t length() const;
};

Stack 멤버 함수 구현

template <typename T>
Stack<T>::Stack() : top(nullptr), size(0) {}
 
template <typename T>
Stack<T>::~Stack() {
    while (!empty()) {
        pop();
    }
}
 
template <typename T>
void Stack<T>::push(const T& value) {
    Node* newNode = new Node(value);
    newNode->next = top;
    top = newNode;
    ++size;
}
 
template <typename T>
void Stack<T>::pop() {
    if (empty()) {
        throw std::out_of_range("Stack is empty");
    }
    Node* temp = top;
    top = top->next;
    delete temp;
    --size;
}
 
template <typename T>
T& Stack<T>::peek() {
    if (empty()) {
        throw std::out_of_range("Stack is empty");
    }
    return top->data;
}
 
template <typename T>
const T& Stack<T>::peek() const {
    if (empty()) {
        throw std::out_of_range("Stack is empty");
    }
    return top->data;
}
 
template <typename T>
bool Stack<T>::empty() const {
    return size == 0;
}
 
template <typename T>
size_t Stack<T>::length() const {
    return size;
}

Stack 사용 예시

int main() {
    Stack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
 
    std::cout << "Stack top: " << stack.peek() << std::endl;
 
    while (!stack.empty()) {
        std::cout << "Popped: " << stack.peek() << std::endl;
        stack.pop();
    }
 
    return 0;
}

큐 (Queue) 구현

큐는 FIFO (First In First Out) 원칙을 따르는 자료구조입니다.

Queue 클래스 템플릿 정의

template <typename T>
class Queue {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& d) : data(d), next(nullptr) {}
    };
 
    Node* front;
    Node* rear;
    size_t size;
 
public:
    Queue();
    ~Queue();
    void enqueue(const T& value);
    void dequeue();
    T& peek();
    const T& peek() const;
    bool empty() const;
    size_t length() const;
};

Queue 멤버 함수 구현

template <typename T>
Queue<T>::Queue() : front(nullptr), rear(nullptr), size(0) {}
 
template <typename T>
Queue<T>::~Queue() {
    while (!empty()) {
        dequeue();
    }
}
 
template <typename T>
void Queue<T>::enqueue(const T& value) {
    Node* newNode = new Node(value);
    if (empty()) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
    ++size;
}
 
template <typename T>
void Queue<T>::dequeue() {
    if (empty()) {
        throw std::out_of_range("Queue is empty");
    }
    Node* temp = front;
    front = front->next;
    delete temp;
    --size;
    if (empty()) {
        rear = nullptr;
    }
}
 
template <typename T>
T& Queue<T>::peek() {
    if (empty()) {
        throw std::out_of_range("Queue is empty");
    }
    return front->data;
}
 
template <typename T>
const T& Queue<T>::peek() const {
    if (empty()) {
        throw std::out_of_range("Queue is empty");
    }
    return front->data;
}
 
template <typename T>
bool Queue<T>::empty() const {
    return size == 0;
}
 
template <typename T>
size_t Queue<T>::length() const {
    return size;
}

Queue 사용 예시

int main() {
    Queue<int> queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
 
    std::cout << "Queue front: " << queue.peek() << std::endl;
 
    while (!queue.empty()) {
        std::cout << "Dequeued: " << queue.peek() << std::endl;
        queue.dequeue();
    }
 
    return 0;
}

연습 문제

Vector 클래스에 insert와 erase 메서드를 추가하세요.
LinkedList 클래스에 반복자(iterator) 기능을 추가하세요.
Stack 클래스를 Vector를 사용하여 다시 구현해보세요.
Queue 클래스를 두 개의 Stack을 사용하여 구현해보세요.

성능 분석 및 최적화

각 데이터 구조의 연산에 대한 시간 복잡도와 공간 복잡도를 분석해보세요.

다음은 기본적인 분석입니다.

1. Vector

삽입/삭제 (끝) : O(1) 평균, O(n) 최악 (재할당 시)
임의 접근 : O(1)
검색 : O(n)

2. LinkedList

삽입/삭제 (앞/뒤) : O(1)
임의 접근 : O(n)
검색 : O(n)

3. Stack

push/pop : O(1)

4. Queue

enqueue/dequeue : O(1)

성능 최적화를 위해 다음과 같은 기법들을 고려해보세요.

Vector의 경우, 초기 용량을 적절히 설정하여 불필요한 재할당을 줄입니다.
LinkedList에서 자주 접근하는 노드에 대한 캐시를 구현합니다.
메모리 풀링을 사용하여 동적 할당/해제의 오버헤드를 줄입니다.

스레드 안전성

멀티스레딩 환경에서 사용할 수 있도록 데이터 구조들을 스레드 안전하게 만들어보세요.

다음과 같은 방법들을 고려할 수 있습니다.

뮤텍스를 사용한 동기화
락-프리(lock-free) 알고리즘 구현
원자적 연산 사용

예를 들어, 스레드 안전한 스택을 다음과 같이 구현할 수 있습니다.

#include <mutex>
 
template <typename T>
class ThreadSafeStack {
private:
    Stack<T> stack;
    mutable std::mutex mtx;
 
public:
    void push(const T& value) {
        std::lock_guard<std::mutex> lock(mtx);
        stack.push(value);
    }
 
    bool pop(T& value) {
        std::lock_guard<std::mutex> lock(mtx);
        if (stack.empty()) {
            return false;
        }
        value = stack.peek();
        stack.pop();
        return true;
    }
 
    bool empty() const {
        std::lock_guard<std::mutex> lock(mtx);
        return stack.empty();
    }
};

단위 테스트

각 데이터 구조에 대한 단위 테스트를 작성하여 구현의 정확성을 검증하세요.

다음과 같은 시나리오를 테스트해볼 수 있습니다.

빈 상태에서의 연산
대량의 데이터 삽입 및 삭제
경계 조건 (예 : 최대 용량에 도달했을 때)
예외 처리

예를 들어, Vector 클래스에 대한 간단한 테스트 코드는 다음과 같습니다.

#include <cassert>
 
void testVector() {
    Vector<int> vec;
    assert(vec.empty());
    assert(vec.size() == 0);
 
    vec.push_back(1);
    assert(!vec.empty());
    assert(vec.size() == 1);
    assert(vec[0] == 1);
 
    vec.push_back(2);
    vec.push_back(3);
    assert(vec.size() == 3);
    assert(vec[2] == 3);
 
    vec.pop_back();
    assert(vec.size() == 2);
    assert(vec[1] == 2);
 
    // 예외 테스트
    bool exceptionThrown = false;
    try {
        vec[2]; // 범위를 벗어난 접근
    } catch (const std::out_of_range&) {
        exceptionThrown = true;
    }
    assert(exceptionThrown);
 
    std::cout << "Vector tests passed!" << std::endl;
}

결론

이 실습을 통해 우리는 C++ 템플릿을 사용하여 다양한 제네릭 데이터 구조를 구현해보았습니다.

이러한 경험은 다음과 같은 이점을 제공합니다.

데이터 구조의 내부 작동 원리에 대한 깊은 이해
템플릿을 사용한 제네릭 프로그래밍 기술 향상
효율적인 메모리 관리와 예외 처리 능력 개발
성능 분석 및 최적화 기법 학습

실제 프로젝트에서는 대부분의 경우 표준 라이브러리의 컨테이너를 사용하게 될 것입니다.

하지만 이러한 기본적인 데이터 구조를 직접 구현해보는 것을 통해 우리는 더 효율적으로 표준 라이브러리를 사용할 수 있게 되었습니다.

이제 개인이 필요한 경우에 커스텀 데이터 구조를 설계하고 구현할 수 있는 능력을 갖추게 되었습니다.

앞으로 더 복잡한 데이터 구조와 알고리즘을 학습하고 구현해보면서, 여러분의 프로그래밍 실력은 더욱 향상될 것입니다. 끊임없는 학습과 실습을 통해 더 나은 프로그래머가 되시기 바랍니다.

이전으로 다음으로