[알고리즘] 스택(Stack)과 큐(Queue)

Federico-15·2024년 10월 18일
queuestack스택알고리즘자바큐

알고리즘

목록 보기
1/2
post-thumbnail

스택(Stack)과 큐(Queue)에 대해서 포스팅하겠습니다. 본 포스팅은 자바를 기반으로 설명합니다.

1. 스택(Stack)이란?

먼저, 스택을 형상화한 그림부터 보겠습니다.

스택(Stack)은 LIFO (Last In First Out) 구조를 따르는 자료구조로, 마지막에 추가된 요소가 가장 먼저 제거되는 방식입니다. 즉, 후입선출 방식으로 작동합니다. 쉽게 말해, 스택은 책을 쌓아 올리듯이 데이터를 쌓고, 가장 나중에 쌓은 책부터 꺼내는 것과 같은 개념입니다.

1-1. 스택의 기본연산

스택은 주로 두 가지 연산으로 이루어집니다:

  • pop : 스택의 맨 위에 새로운 데이터를 추가하는 연산
  • push : 스택의 맨 위에 있는 데이터를 제거하는 연산

이 외에도 스택의 상태를 확인하는 연산이 있습니다:

  • peek : 스택의 맨 위에 있는 데이터를 제거하지 않고 확인하는 연산
  • isEmpty : 스택이 비어 있는지 확인하는 연산

1-2. 스택의 동작 방식

  1. push 연산으로 스택에 데이터를 쌓습니다.
  2. pop 연산으로 스택에서 가장 최근에 추가된 데이터를 제거합니다.

1-3. 스택의 활용 예시

  • 함수 호출: 함수 호출 시, 호출된 함수의 정보를 스택에 저장하고, 함수가 종료되면 해당 정보가 스택에서 제거됩니다. 이를 호출 스택(Call Stack)이라고 합니다.

  • 괄호 검사: 중첩된 괄호의 짝이 맞는지 검사할 때 스택을 사용하여 괄호의 쌍을 확인할 수 있습니다.

  • 백트래킹(Backtracking): DFS(깊이 우선 탐색)와 같은 알고리즘에서 스택을 사용하여 재귀적 탐색을 수행할 수 있습니다.

1-4. 스택의 예시 코드 (자바)

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 스택에 요소 추가 (push)
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // 스택에서 가장 위의 요소 확인 (peek)
        System.out.println("Top element: " + stack.peek());  // 출력: 30

        // 스택에서 가장 위의 요소 제거 (pop)
        System.out.println("Popped element: " + stack.pop());  // 출력: 30
        System.out.println("Popped element: " + stack.pop());  // 출력: 20

        // 스택의 남은 요소
        System.out.println("Remaining elements: " + stack);  // 출력: [10]
    }
}

위 코드를 통해 push, pop, peek 연산이 어떻게 동작하는지 확인할 수 있습니다.

스택은 데이터가 쌓였다가 제거되는 순서가 중요한 경우에 매우 유용하며, 다양한 알고리즘과 문제 해결에 자주 활용됩니다.

2. 큐(Queue) 란?

먼저, 큐를 형상화한 그림부터 보겠습니다.

큐(Queue)는 FIFO (First In First Out) 구조를 따르는 자료구조로, 먼저 추가된 데이터가 먼저 제거되는 방식입니다. 즉, 선입선출 방식으로 작동합니다. 줄을 서는 상황을 생각하면 쉽게 이해할 수 있는데, 먼저 줄을 선 사람이 먼저 처리되는 것과 같은 개념입니다.

2-1. 큐의 기본연산

큐는 주로 세 가지 연산으로 이루어집니다:

  • offer: 큐의 끝에 새로운 데이터를 추가하는 연산 (또는 add).
  • poll: 큐의 앞에 있는 데이터를 제거하는 연산 (또는 remove).
  • peek: 큐의 앞에 있는 데이터를 제거하지 않고 확인하는 연산.

이 외에도 큐의 상태를 확인하는 연산이 있습니다:

  • isEmpty: 큐가 비어 있는지 확인하는 연산.

2-2. 큐의 동작 방식

  1. offer 연산으로 큐의 끝에 데이터를 추가합니다.
  2. poll 연산으로 큐의 앞에 있는 데이터를 제거합니다.

2-3. 큐의 활용 예시

  • 프린터 대기열: 프린터는 먼저 들어온 작업부터 순차적으로 처리하기 때문에 큐 구조로 관리됩니다.

  • 프로세스 관리: 운영 체제에서 프로세스를 처리할 때, 먼저 들어온 작업부터 처리하는 구조로 큐를 사용합니다.

  • BFS (너비 우선 탐색): 그래프 탐색 알고리즘에서 큐를 사용하여 한 레벨씩 차례대로 탐색할 수 있습니다.

2-4. 큐의 예시 코드 (자바)

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 큐에 요소 추가 (offer)
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        // 큐에서 맨 앞의 요소 확인 (peek)
        System.out.println("Front element: " + queue.peek());  // 출력: 10

        // 큐에서 맨 앞의 요소 제거 (poll)
        System.out.println("Polled element: " + queue.poll());  // 출력: 10
        System.out.println("Polled element: " + queue.poll());  // 출력: 20

        // 큐의 남은 요소
        System.out.println("Remaining elements: " + queue);  // 출력: [30]
    }
}

위 코드를 통해 큐에서 offer, poll, peek 연산이 어떻게 동작하는지 확인할 수 있습니다. offer로 데이터를 추가하고, poll로 데이터를 제거하며, peek으로 맨 앞에 있는 데이터를 확인할 수 있습니다.

큐는 데이터가 처리된 순서가 중요한 경우에 많이 사용되며, 대기열이나 너비 우선 탐색(BFS) 등에서 자주 활용되는 자료구조입니다.

profile
Federico-15
한 방 있는, 묵직한 개발자

0개의 댓글