[C++로 배우는 알고리즘과 자료구조] Day 4: 스택과 큐

스택 (Stack)

스택은 후입선출(LIFO, Last In First Out) 원칙을 따르는 자료구조입니다. 즉, 가장 나중에 삽입된 요소가 가장 먼저 제거됩니다. 스택은 주로 재귀적 알고리즘, 언어 구문 분석, 백트래킹 등에서 사용됩니다.

스택의 주요 연산:

1. push: 스택의 맨 위에 요소를 추가합니다.
2. pop: 스택의 맨 위 요소를 제거합니다.
3. top: 스택의 맨 위 요소를 반환합니다.
4. isEmpty: 스택이 비어 있는지 확인합니다.

스택 구현 예제

#include <iostream>
#include <vector>

class Stack {
public:
    void push(int value) {
        data.push_back(value); // 스택의 맨 위에 요소 추가
    }

    void pop() {
        if (!data.empty()) {
            data.pop_back(); // 스택의 맨 위 요소 제거
        }
    }

    int top() const {
        if (!data.empty()) {
            return data.back(); // 스택의 맨 위 요소 반환
        }
        throw std::runtime_error("스택이 비어 있습니다.");
    }

    bool isEmpty() const {
        return data.empty(); // 스택이 비어 있는지 확인
    }

private:
    std::vector<int> data; // 스택의 데이터를 저장할 벡터
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "스택의 맨 위 요소: " << stack.top() << std::endl; // 30 출력

    stack.pop();
    std::cout << "스택의 맨 위 요소: " << stack.top() << std::endl; // 20 출력

    return 0;
}

 

큐 (Queue)

큐는 선입선출(FIFO, First In First Out) 원칙을 따르는 자료구조입니다. 즉, 가장 먼저 삽입된 요소가 가장 먼저 제거됩니다. 큐는 주로 너비 우선 탐색(BFS), 캐시, 프린터 스풀 등에서 사용됩니다.

큐의 주요 연산:

1. enqueue: 큐의 맨 뒤에 요소를 추가합니다.
2. dequeue: 큐의 맨 앞 요소를 제거합니다.
3. front: 큐의 맨 앞 요소를 반환합니다.
4. isEmpty: 큐가 비어 있는지 확인합니다.

큐 구현 예제

#include <iostream>
#include <list>

class Queue {
public:
    void enqueue(int value) {
        data.push_back(value); // 큐의 맨 뒤에 요소 추가
    }

    void dequeue() {
        if (!data.empty()) {
            data.pop_front(); // 큐의 맨 앞 요소 제거
        }
    }

    int front() const {
        if (!data.empty()) {
            return data.front(); // 큐의 맨 앞 요소 반환
        }
        throw std::runtime_error("큐가 비어 있습니다.");
    }

    bool isEmpty() const {
        return data.empty(); // 큐가 비어 있는지 확인
    }

private:
    std::list<int> data; // 큐의 데이터를 저장할 리스트
};

int main() {
    Queue queue;
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    std::cout << "큐의 맨 앞 요소: " << queue.front() << std::endl; // 10 출력

    queue.dequeue();
    std::cout << "큐의 맨 앞 요소: " << queue.front() << std::endl; // 20 출력

    return 0;
}

 

스택과 큐의 활용 예제

스택 예제: 괄호 짝 맞추기

#include <iostream>
#include <stack>
#include <string>

// 주어진 문자열의 괄호 짝이 맞는지 확인하는 함수
bool isBalanced(const std::string& str) {
    std::stack<char> stack; // 스택 생성
    for (char ch : str) {
        if (ch == '(') {
            stack.push(ch); // 여는 괄호는 스택에 추가
        } else if (ch == ')') {
            if (stack.empty()) {
                return false; // 닫는 괄호가 스택에 없으면 짝이 맞지 않음
            }
            stack.pop(); // 여는 괄호와 짝이 맞는 닫는 괄호는 스택에서 제거
        }
    }
    return stack.empty(); // 스택이 비어있으면 짝이 맞음
}

int main() {
    std::string str = "(())()";
    if (isBalanced(str)) {
        std::cout << "괄호 짝이 맞습니다." << std::endl;
    } else {
        std::cout << "괄호 짝이 맞지 않습니다." << std::endl;
    }
    return 0;
}

 

큐 예제: 너비 우선 탐색 (BFS)

#include <iostream>
#include <vector>
#include <queue>

// 그래프를 나타내는 클래스
class Graph {
public:
    Graph(int vertices) : adjList(vertices) {}

    void addEdge(int src, int dest) {
        adjList[src].push_back(dest); // 간선 추가
    }

    void BFS(int start) const {
        std::vector<bool> visited(adjList.size(), false); // 방문 여부 저장
        std::queue<int> queue; // BFS를 위한 큐

        visited[start] = true; // 시작 노드 방문
        queue.push(start);

        while (!queue.empty()) {
            int vertex = queue.front();
            queue.pop();
            std::cout << vertex << " "; // 방문한 노드 출력

            for (int neighbor : adjList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // 인접 노드 방문
                    queue.push(neighbor);
                }
            }
        }
    }

private:
    std::vector<std::vector<int>> adjList; // 인접 리스트
};

int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    std::cout << "BFS 탐색 결과: ";
    graph.BFS(0); // 노드 0에서 BFS 시작

    return 0;
}

 

설명

1. 스택:
   • 스택은 후입선출(LIFO) 원칙을 따르는 자료구조입니다.
   • 스택의 주요 연산은 push, pop, top, isEmpty입니다.
   • 예제: 괄호 짝 맞추기 알고리즘
2. 큐:
   • 큐는 선입선출(FIFO) 원칙을 따르는 자료구조입니다.
   • 큐의 주요 연산은 enqueue, dequeue, front, isEmpty입니다.
   • 예제: 너비 우선 탐색(BFS) 알고리즘

이제 스택과 큐의 기본 개념과 활용 예제를 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 5: 해시 테이블"에 대해 학습하겠습니다.