2025 09 29 스파르타 코딩클럽 21일차

1. 스택(Stack)

개념과 특징

• LIFO (Last In, First Out) 구조 → 마지막에 들어온 데이터가 먼저
  나간다.
• 대표적 활용: 함수 호출(콜 스택), 실행 취소(Undo), 수식 계산 등

기본 연산

• push(item): 데이터 삽입
• pop(): 데이터 삭제 및 반환
• peek(): 최상단(top)의 데이터 확인 (삭제 X)
• isEmpty(): 비어있는지 확인

장단점

• 장점: 구현 단순, 빠른 연산 (O(1))
• 단점: 메모리 제한(배열 기반), 중간 요소 접근 불가

응용 예시

• 문자열 뒤집기
• 웹 브라우저 방문 기록 (뒤로/앞으로)
• DFS(깊이 우선 탐색)
• 괄호 유효성 검사

---

2. 큐(Queue)

개념과 특징

• FIFO (First In, First Out) 구조 → 먼저 들어온 데이터가 먼저 나간다.
• 대표적 활용: 대기열(프린터, 은행 번호표), 프로세스 스케줄링

기본 연산

• enqueue(item): 데이터 삽입 (뒤에서)
• dequeue(): 데이터 삭제 및 반환 (앞에서)
• peek(): front 데이터 확인
• isEmpty(): 비어있는지 확인

큐의 변형

• 원형 큐(Circular Queue): 공간 낭비 해결
• Deque(Double Ended Queue): 양쪽에서 삽입/삭제 가능
• Priority Queue: 우선순위에 따라 꺼내는 순서 결정

장단점

• 장점: 공정한 순서 보장, 구현 단순
• 단점: 배열 기반 구현 시 메모리 낭비 가능

응용 예시

• BFS(너비 우선 탐색)
• 운영체제 프로세스 스케줄링
• 네트워크 데이터 버퍼 관리

---

3. Stack vs Queue 비교

구분 Stack (스택) Queue (큐)

---

구조 LIFO (후입선출) FIFO (선입선출)
삽입 위치 Top (맨 위) Rear (뒤)
삭제 위치 Top (맨 위) Front (앞)
시간 복잡도 O(1) O(1)
주요 응용 재귀, 되돌리기, DFS 대기열, BFS, 스케줄링

---

4. 자바 설계 예시

Stack 구현 (ArrayList 활용)

class Stack {
    private List<Integer> list = new ArrayList<>();

    public void push(int value) {
        list.add(value);
    }

    public int pop() {
        if (list.isEmpty()) throw new RuntimeException("Stack is empty");
        return list.remove(list.size() - 1);
    }

    public int peek() {
        if (list.isEmpty()) throw new RuntimeException("Stack is empty");
        return list.get(list.size() - 1);
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}

Queue 구현 (LinkedList 활용)

class Queue {
    private LinkedList<Integer> list = new LinkedList<>();

    public void enqueue(int value) {
        list.addLast(value);
    }

    public int dequeue() {
        if (list.isEmpty()) throw new RuntimeException("Queue is empty");
        return list.removeFirst();
    }

    public int peek() {
        if (list.isEmpty()) throw new RuntimeException("Queue is empty");
        return list.getFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}