24.12.27 TIL 스택과 큐

1. 스택(Stack)

1) 스택이란?

스택은 LIFO (Last In, First Out) 구조를 가지는 자료구조로, 가장 나중에 삽입된 데이터가 가장 먼저 제거됩니다.

2) 주요 연산

• push: 스택에 데이터를 삽입
• pop: 스택에서 데이터를 제거하고 반환
• peek: 스택의 최상단 데이터를 확인

3) 구현

스택은 배열(Array)이나 연결 리스트(Linked List)를 사용해 구현할 수 있습니다. Java에서는 Stack 클래스를 사용하거나, Deque를 활용할 수 있습니다.

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

        // Remaining elements
        System.out.println("Stack: " + stack); // [10, 20]
    }
}

5) 스택의 활용 사례

• 함수 호출의 순서를 저장하는 호출 스택
• 괄호 검증 문제
• DFS (Depth First Search) 구현

---

2. 큐(Queue)

1) 큐란?

큐는 FIFO (First In, First Out) 구조를 가지는 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 제거됩니다.

2) 주요 연산

• enqueue: 큐에 데이터를 삽입
• dequeue: 큐에서 데이터를 제거하고 반환
• peek: 큐의 첫 번째 데이터를 확인

3) 구현

큐는 배열(Array)이나 연결 리스트(Linked List)를 사용해 구현할 수 있습니다. Java에서는 Queue 인터페이스와 이를 구현한 LinkedList, ArrayDeque 등을 사용합니다.

4) 큐 예제 코드

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

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

        // Enqueue
        queue.add(10);
        queue.add(20);
        queue.add(30);

        // Peek
        System.out.println("Front element: " + queue.peek()); // 10

        // Dequeue
        System.out.println("Removed element: " + queue.poll()); // 10

        // Remaining elements
        System.out.println("Queue: " + queue); // [20, 30]
    }
}

5) 큐의 활용 사례

• BFS (Breadth First Search) 구현
• 프로세스 스케줄링
• 데이터 스트림 처리

---

3. 스택과 큐의 차이점

특징	스택	큐
구조	LIFO (Last In, First Out)	FIFO (First In, First Out)
데이터 삽입/제거	하나의 끝에서 삽입 및 제거	앞에서 제거, 뒤에서 삽입
사용 사례	DFS, 괄호 검증	BFS, 프로세스 관리

---

4. 마무리

스택과 큐는 간단하지만 많은 알고리즘과 문제 해결의 기본이 되는 자료구조입니다. 특히, 문제에서 "순서"와 관련된 요구 사항이 있을 때, 두 자료구조를 활용하면 적합한 해결책을 쉽게 떠올릴 수 있었습니다. 앞으로 다양한 문제에서 스택과 큐를 활용해 보고 싶습니다.