스택, 큐, 연결 리스트

1. 스택 (Stack)

1.1. 기본 지식

• 개념: LIFO(Last-In, First-Out), 즉 '마지막에 들어온 것이 가장 먼저 나간다'는 원칙을 따르는 자료구조. 접시를 쌓는 것을 생각하면 쉽다. 가장 위에 쌓은 접시를 가장 먼저 꺼내게 된다.
• 핵심 연산:
  • push(item): 스택의 가장 윗부분(top)에 데이터를 추가.
  • pop(): 스택의 가장 윗부분(top)에 있는 데이터를 제거하고 반환.
  • peek() 또는 top(): 스택의 가장 윗부분에 있는 데이터를 제거하지 않고 확인.
  • isEmpty(): 스택이 비어있는지 확인.
• 사용 예시:
  • 함수 호출 스택: 프로그램에서 함수가 호출될 때마다 해당 함수의 정보(매개변수, 복귀 주소 등)가 스택에 쌓이고, 함수 실행이 끝나면 스택에서 제거된다.
  • 브라우저 뒤로 가기: 웹 페이지를 이동할 때마다 방문한 페이지의 주소가 스택에 쌓여, '뒤로 가기' 버튼을 누르면 스택에서 주소를 꺼내 이전 페이지로 이동한다.
  • 수식 계산, 괄호 검사 등

1.2. 심화 지식

• 시간 복잡도: push, pop, peek, isEmpty 모든 핵심 연산이 스택의 가장 윗부분에서만 일어나므로 데이터의 양과 관계없이 O(1)의 시간 복잡도를 가진다.
• 구현 방식 비교:
  • 배열 기반: 구현이 간단하고 빠르지만, 스택의 크기가 고정되어 있어 처음에 정한 크기를 넘어서는 데이터를 저장할 수 없다(Stack Overflow).
  • 연결 리스트 기반: 크기가 동적으로 변하여 유연하지만, 각 데이터마다 다음 노드를 가리키는 포인터를 위한 추가 메모리가 필요하며, 배열보다 약간의 성능 오버헤드가 있을 수 있다.

1.3. C++ 구현

1. 배열 기반 스택 (Array-based Stack)

#include <iostream>
#include <stdexcept>

const int MAX_SIZE = 100; // 스택의 최대 크기

template <typename T>
class ArrayStack {
private:
    T arr[MAX_SIZE];
    int topIndex; // 가장 위 원소의 인덱스

public:
    ArrayStack() : topIndex(-1) {}

    // 스택에 원소를 추가
    void push(T item) {
        if (topIndex >= MAX_SIZE - 1) {
            throw std::overflow_error("Stack Overflow");
        }
        arr[++topIndex] = item;
    }

    // 스택에서 원소를 제거하고 반환
    T pop() {
        if (isEmpty()) {
            throw std::underflow_error("Stack is empty");
        }
        return arr[topIndex--];
    }

    // 스택의 최상단 원소를 확인
    T peek() {
        if (isEmpty()) {
            throw std::underflow_error("Stack is empty");
        }
        return arr[topIndex];
    }

    // 스택이 비어있는지 확인
    bool isEmpty() {
        return topIndex == -1;
    }
};

2. 연결 리스트 기반 스택 (List-based Stack)

(단일 연결 리스트를 내부적으로 사용하여 구현)

#include <iostream>
#include <stdexcept>

template <typename T>
struct Node {
    T data;
    Node* next;
};

template <typename T>
class ListStack {
private:
    Node<T>* topNode; // 스택의 최상단 노드

public:
    ListStack() : topNode(nullptr) {}

    ~ListStack() {
        while (!isEmpty()) {
            pop();
        }
    }

    // 스택에 원소를 추가
    void push(T item) {
        Node<T>* newNode = new Node<T>{item, topNode};
        topNode = newNode;
    }

    // 스택에서 원소를 제거하고 반환
    T pop() {
        if (isEmpty()) {
            throw std::underflow_error("Stack is empty");
        }
        T item = topNode->data;
        Node<T>* temp = topNode;
        topNode = topNode->next;
        delete temp;
        return item;
    }

    // 스택의 최상단 원소를 확인
    T peek() {
        if (isEmpty()) {
            throw std::underflow_error("Stack is empty");
        }
        return topNode->data;
    }

    // 스택이 비어있는지 확인
    bool isEmpty() {
        return topNode == nullptr;
    }
};

---

2. 큐 (Queue)

2.1. 기본 지식

• 개념: FIFO(First-In, First-Out), 즉 '가장 먼저 들어온 것이 가장 먼저 나간다'는 원칙을 따르는 자료구조. 은행 창구나 놀이공원 줄서기를 생각하면 쉽다.
• 핵심 연산:
  • enqueue(item): 큐의 가장 뒷부분(rear)에 데이터를 추가.
  • dequeue(): 큐의 가장 앞부분(front)에 있는 데이터를 제거하고 반환.
  • front(): 큐의 가장 앞부분에 있는 데이터를 제거하지 않고 확인.
  • isEmpty(): 큐가 비어있는지 확인.
• 사용 예시:
  • 프린터 대기열: 여러 문서의 인쇄 요청이 들어온 순서대로 처리된다.
  • 너비 우선 탐색(BFS): 그래프 탐색 시, 현재 정점과 인접한 정점들을 큐에 넣고 순서대로 방문한다.
  • 메시지 큐(MQ): 비동기적인 데이터 처리를 위해 메시지를 큐에 저장해두고 순차적으로 처리한다.

2.2. 심화 지식

• 시간 복잡도: enqueue, dequeue, front, isEmpty 모든 핵심 연산이 큐의 양 끝에서만 일어나므로 O(1)의 시간 복잡도를 가진다.
• 구현 방식 비교:
  • 배열 기반: dequeue 연산 시 모든 원소를 한 칸씩 앞으로 당기면 O(n)의 비효율이 발생한다. 이를 해결하기 위해 배열의 처음과 끝이 연결된 것처럼 사용하는 원형 큐(Circular Queue)로 구현해야 O(1) 성능을 보장할 수 있다.
  • 연결 리스트 기반: front와 rear 두 개의 포인터를 사용하여 양 끝에서의 삽입/삭제를 O(1)으로 쉽게 구현할 수 있다. 크기가 동적으로 변하는 장점이 있다.

2.3. C++ 구현

1. 배열 기반 원형 큐 (Circular Queue)

#include <iostream>
#include <stdexcept>

const int MAX_QUEUE_SIZE = 100;

template <typename T>
class ArrayQueue {
private:
    T arr[MAX_QUEUE_SIZE];
    int frontIndex;
    int rearIndex;
    int count; // 큐에 있는 원소의 개수

public:
    ArrayQueue() : frontIndex(0), rearIndex(-1), count(0) {}

    // 큐에 원소를 추가
    void enqueue(T item) {
        if (count >= MAX_QUEUE_SIZE) {
            throw std::overflow_error("Queue is full");
        }
        rearIndex = (rearIndex + 1) % MAX_QUEUE_SIZE;
        arr[rearIndex] = item;
        count++;
    }

    // 큐에서 원소를 제거하고 반환
    T dequeue() {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        T item = arr[frontIndex];
        frontIndex = (frontIndex + 1) % MAX_QUEUE_SIZE;
        count--;
        return item;
    }

    // 큐의 가장 앞 원소를 확인
    T front() {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        return arr[frontIndex];
    }

    // 큐가 비어있는지 확인
    bool isEmpty() {
        return count == 0;
    }
};

2. 연결 리스트 기반 큐 (List-based Queue)

#include <iostream>
#include <stdexcept>

// (스택 구현에 사용된 Node 구조체 재사용)
template <typename T>
struct Node {
    T data;
    Node* next;
};

template <typename T>
class ListQueue {
private:
    Node<T>* frontNode; // 큐의 가장 앞 노드
    Node<T>* rearNode;  // 큐의 가장 뒤 노드

public:
    ListQueue() : frontNode(nullptr), rearNode(nullptr) {}

    ~ListQueue() {
        while (!isEmpty()) {
            dequeue();
        }
    }

    // 큐에 원소를 추가
    void enqueue(T item) {
        Node<T>* newNode = new Node<T>{item, nullptr};
        if (isEmpty()) {
            frontNode = rearNode = newNode;
        } else {
            rearNode->next = newNode;
            rearNode = newNode;
        }
    }

    // 큐에서 원소를 제거하고 반환
    T dequeue() {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        T item = frontNode->data;
        Node<T>* temp = frontNode;
        frontNode = frontNode->next;
        if (frontNode == nullptr) { // 큐가 비게 되면 rear도 nullptr로
            rearNode = nullptr;
        }
        delete temp;
        return item;
    }

    // 큐의 가장 앞 원소를 확인
    T front() {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        return frontNode->data;
    }

    // 큐가 비어있는지 확인
    bool isEmpty() {
        return frontNode == nullptr;
    }
};

---

3. 단일 연결 리스트 (Singly Linked List)

3.1. 기본 지식

• 개념: 여러 개의 노드(Node)가 순차적으로 연결된 자료구조. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다. 리스트의 시작은 head 포인터가 가리킨다.
• 핵심 연산:
  • insert(item): 리스트의 특정 위치(주로 맨 앞 또는 맨 뒤)에 데이터를 삽입.
  • delete(item): 특정 값을 가진 노드를 리스트에서 삭제.
  • search(item): 특정 값을 가진 노드를 검색.

3.2. 심화 지식

• 시간 복잡도:
  • 맨 앞에 삽입/삭제: O(1)
  • 맨 뒤에 삽입/삭제: 맨 끝 노드를 찾기 위해 리스트를 순회해야 하므로 O(n). (단, tail 포인터를 유지하면 삽입은 O(1) 가능)
  • 탐색 및 중간 삽입/삭제: 특정 노드를 찾기 위해 평균적으로 n/2번 순회하므로 O(n).
• 장점:
  • 동적 크기: 배열과 달리 크기가 고정되어 있지 않고, 필요에 따라 노드를 추가/삭제하며 크기를 조절할 수 있다.
  • 쉬운 삽입/삭제: 특정 노드를 찾았다면, 포인터 몇 개만 조작하여 쉽게 삽입/삭제가 가능하다. 배열처럼 원소들을 이동시킬 필요가 없다.
• 단점:
  • 인덱스를 통한 접근 불가: 특정 인덱스의 원소에 바로 접근할 수 없으며, head부터 순차적으로 탐색해야 한다.
  • 추가 메모리 사용: 데이터 외에 다음 노드를 가리키는 포인터를 위한 추가적인 메모리 공간이 필요하다.

3.3. C++ 구현

#include <iostream>

template <typename T>
class SinglyLinkedList {
private:
    // (스택/큐 구현에 사용된 Node 구조체 재사용)
    struct Node {
        T data;
        Node* next;
    };
    Node* head; // 리스트의 시작 노드

public:
    SinglyLinkedList() : head(nullptr) {}

    ~SinglyLinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }

    // 리스트 맨 앞에 삽입
    void insertAtFront(T item) {
        Node* newNode = new Node{item, head};
        head = newNode;
    }

    // 리스트 맨 뒤에 삽입
    void insertAtBack(T item) {
        Node* newNode = new Node{item, nullptr};
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }

    // 특정 값 삭제
    void deleteItem(T item) {
        if (head == nullptr) return;

        // 삭제할 노드가 head인 경우
        if (head->data == item) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* current = head;
        while (current->next != nullptr && current->next->data != item) {
            current = current->next;
        }

        if (current->next != nullptr) {
            Node* temp = current->next;
            current->next = temp->next;
            delete temp;
        }
    }

    // 리스트 출력
    void display() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

---

4. 이중 연결 리스트 (Doubly Linked List)

4.1. 기본 지식

• 개념: 단일 연결 리스트를 확장한 형태로, 각 노드가 데이터, 다음 노드를 가리키는 포인터, 그리고 이전 노드를 가리키는 포인터로 구성된다.
• 장점: 단일 연결 리스트와 달리 양방향 탐색이 가능하다. 특정 노드에서 이전 노드로의 접근이 쉬워져 노드 삭제 연산이 더 효율적이다.

4.2. 심화 지식

• 시간 복잡도: 단일 연결 리스트와 대부분 동일하지만, 특정 노드가 주어졌을 때 그 노드를 삭제하는 연산은 O(1)에 가능하다. (단일 연결 리스트는 이전 노드를 찾기 위해 O(n)이 걸림)
• 장점:
  • 양방향 탐색: head에서 tail로, tail에서 head로 모두 탐색이 가능하다.
  • 효율적인 삭제: 삭제할 노드의 주소만 알면, 이전 노드를 찾기 위한 추가 탐색 없이 즉시 삭제가 가능하다.
• 단점:
  • 더 많은 메모리 사용: 이전 노드를 가리키는 포인터(prev)를 위한 메모리가 추가로 필요하다.
  • 구현 복잡성: 삽입/삭제 시 next 포인터뿐만 아니라 prev 포인터도 함께 관리해야 하므로 구현이 더 복잡하다.

4.3. C++ 구현

#include <iostream>

template <typename T>
class DoublyLinkedList {
private:
    struct Node {
        T data;
        Node* next;
        Node* prev;
    };
    Node* head; // 리스트의 시작 노드
    Node* tail; // 리스트의 끝 노드

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    ~DoublyLinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }

    // 리스트 맨 앞에 삽입
    void insertAtFront(T item) {
        Node* newNode = new Node{item, head, nullptr};
        if (head != nullptr) {
            head->prev = newNode;
        }
        head = newNode;
        if (tail == nullptr) {
            tail = newNode;
        }
    }

    // 리스트 맨 뒤에 삽입
    void insertAtBack(T item) {
        Node* newNode = new Node{item, nullptr, tail};
        if (tail != nullptr) {
            tail->next = newNode;
        }
        tail = newNode;
        if (head == nullptr) {
            head = newNode;
        }
    }

    // 특정 값 삭제
    void deleteItem(T item) {
        Node* current = head;
        while (current != nullptr && current->data != item) {
            current = current->next;
        }

        if (current == nullptr) return; // 삭제할 노드 없음

        if (current->prev != nullptr) {
            current->prev->next = current->next;
        } else { // head를 삭제하는 경우
            head = current->next;
        }

        if (current->next != nullptr) {
            current->next->prev = current->prev;
        } else { // tail을 삭제하는 경우
            tail = current->prev;
        }

        delete current;
    }

    // 리스트 정방향 출력
    void display() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " <-> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    // 리스트 역방향 출력
    void displayReverse() {
        Node* current = tail;
        while (current != nullptr) {
            std::cout << current->data << " <-> ";
            current = current->prev;
        }
        std::cout << "nullptr" << std::endl;
    }
};