알고리즘 풀이를 위한 자료구조: 스택(Stack)과 큐(Queue)

728x90

스택(Stack)

스택(Stack)이란?

스택(Stack)은 데이터를 넣고 빼는데 있어서 Last-In, First-Out (LIFO) 방식을 따르는 자료구조입니다.
즉, 가장 마지막에 넣은 데이터가 가장 먼저 빠져나가는 것을 말합니다.
스택은 컴퓨터 과학에서 매우 중요한 자료구조 중 하나이며, 다른 자료구조들과의 연계를 통해 다양한 문제를 효과적으로 해결할 수 있습니다.

스택(Stack)의 구현

스택은 배열(Array)을 통해 구현될 수 있습니다.
스택에 데이터를 삽입하는 연산을 push라 하며, 데이터를 삭제하는 연산을 pop이라고 합니다. 또한, 스택의 가장 상단에 위치한 데이터를 top이라고 합니다.

public class Stack {
    private int[] stack;
    private int top; // 가장 최근에 삽입된 데이터의 위치를 가리킴

    public Stack(int size) {
        stack = new int[size];
        top = -1;
    }

    public void push(int data) {
        stack[++top] = data;
    }

    public int pop() {
        if (isEmpty()) {
            return -1; // 스택이 비어있으면 -1을 리턴
        }
        return stack[top--];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int peek() {
        if (isEmpty()) {
            return -1; // 스택이 비어있으면 -1을 리턴
        }
        return stack[top];
    }
}

스택(Stack)의 활용

스택은 함수 호출의 관리, 수식의 계산, 미로 찾기 등 다양한 문제에서 활용될 수 있습니다.
예를 들어, 괄호 매칭 문제를 해결하기 위해 스택을 사용할 수 있습니다. 이 문제는 입력으로 주어진 문자열에 포함된 괄호들이 올바르게 매칭되어 있는지 확인하는 문제입니다.
이때, 스택을 사용하여 '(' 문자를 만나면 스택에 push하고 ')' 문자를 만나면 스택에서 pop하여 '('와 매칭되는지 확인할 수 있습니다.

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
            stack.pop();
        } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
            stack.pop();
        } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.isEmpty();
}

큐(Queue)

큐(Queue)란?

큐(Queue)는 데이터를 넣고 빼는데 있어서 First-In, First-Out (FIFO) 방식을 따르는 자료구조입니다.
즉, 가장 먼저 넣은 데이터가 가장 먼저 빠져나가는 것을 말합니다.
큐도 스택과 마찬가지로 컴퓨터 과학에서 매우 중요한 자료구조 중 하나이며, 다양한 문제를 해결하는 데에 사용됩니다.

큐(Queue)의 구현

큐는 배열(Array)을 통해 구현될 수 있습니다.
큐에 데이터를 삽입하는 연산을 enqueue라 하며, 데이터를 삭제하는 연산을 dequeue라고 합니다.
또한, 큐에서 가장 먼저 삽입된 데이터를 front, 가장 마지막에 삽입된 데이터를 rear라고 합니다.

public class Queue {
    private int[] queue;
    private int front; // 가장 먼저 삽입된 데이터의 위치를 가리킴
    private int rear; // 가장 마지막에 삽입된 데이터의 위치를 가리킴
    private int size; // 큐의 크기

    public Queue(int size) {
        queue = new int[size];
        front = 0;
        rear = -1;
        this.size = 0;
    }

    public void enqueue(int data) {
        queue[++rear] = data;
        size++;
    }

    public int dequeue() {
        if (isEmpty()) {
            return -1; // 큐가 비어있으면 -1을 리턴
        }
        int data = queue[front];
        front++;
        size--;
        return data;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == queue.length;
    }

    public int peek() {
        if (isEmpty()) {
            return -1; // 큐가 비어있으면 -1을 리턴
        }
        return queue[front];
    }
}

큐(Queue)의 활용

큐는 프린터의 출력 처리, 우선순위가 있는 작업 처리 등 다양한 문제에서 활용될 수 있습니다.
예를 들어, 최단 경로 문제를 해결하기 위해 너비 우선 탐색(BFS) 알고리즘을 사용할 때, 큐를 사용하여 방문할 노드들을 저장하고 순서대로 처리할 수 있습니다.

public void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(start); // 시작 노드를 큐에 삽입
    start.visited = true;

    while (!queue.isEmpty()) {
        Node node = queue.poll(); // 큐에서 노드를 꺼냄
        System.out.print(node.value + " ");

        // 인접한 노드들 중 방문하지 않은 노드들을 큐에 삽입
        for (Node neighbor : node.neighbors) {
            if (!neighbor.visited) {
                neighbor.visited = true;
                queue.offer(neighbor);
            }
        }
    }
}

스택(Stack)과 큐(Queue)의 차이점과 선택 기준

스택(Stack)과 큐(Queue)의 차이점

스택과 큐는 모두 데이터를 저장하는 자료구조이지만, 그 처리 방식이 다릅니다.
스택은 LIFO 방식을 따르며, 가장 나중에 추가된 데이터가 가장 먼저 제거됩니다.
반면에 큐는 FIFO 방식을 따르며, 가장 먼저 추가된 데이터가 가장 먼저 제거됩니다.
이 차이점은 다음과 같은 상황에서 중요한 역할을 합니다.

데이터 삽입/삭제 순서

스택은 가장 최근에 삽입된 데이터를 먼저 제거하기 때문에, 최근에 삽입된 데이터가 먼저 처리되어야 하는 경우에 적합합니다.
예를 들어, 함수 호출 시 스택을 사용하여 함수의 호출 순서와 반환 순서를 관리할 수 있습니다.
반면에 큐는 가장 먼저 삽입된 데이터를 먼저 제거하기 때문에, 먼저 처리해야 하는 데이터를 우선 처리해야 하는 경우에 적합합니다.
예를 들어, 너비 우선 탐색(BFS) 알고리즘을 사용할 때, 큐를 사용하여 방문할 노드들을 저장하고 순서대로 처리할 수 있습니다.

자료구조의 용도

스택은 데이터 삽입/삭제를 빠르게 처리할 수 있기 때문에, 주로 데이터 저장 및 관리에 사용됩니다.
반면에 큐는 데이터의 처리 순서를 관리하는 데에 주로 사용됩니다.

선택 기준

스택과 큐는 각각의 특성을 가지고 있기 때문에, 자료구조를 선택할 때에는 문제의 조건과 목적에 따라 선택해야 합니다.
예를 들어, 데이터의 삽입/삭제가 빈번하게 일어나는 경우에는 스택을 사용하는 것이 적합합니다.
반면에 처리해야 할 데이터의 순서를 관리해야 하는 경우에는 큐를 사용하는 것이 적합합니다.

마무리

이번 글에서는 알고리즘 풀이를 위한 자료구조인 스택과 큐에 대해 자세히 알아보았습니다.
스택과 큐는 각각의 특성을 가지고 있기 때문에, 자료구조를 선택할 때에는 문제의 조건과 목적에 따라 선택해야 합니다.
앞으로도 다양한 알고리즘 문제를 해결하기 위해 이러한 자료구조들을 잘 활용해보시길 바랍니다.