[항해99 취업리부트 TIL] 3주차 1일

오늘 진행된 강의에서 학습한 내용은 무엇인가요?

보고서: 스택, 큐, 덱 비교 분석

1. 서론

본 보고서는 컴퓨터 과학에서 중요한 자료구조인 스택, 큐, 덱의 특징, 작동 방식, 활용 사례, 그리고 각 자료구조 간의 비교 분석을 제공합니다.

2. 스택

2.1. 개요

스택은 Last In, First Out (LIFO) 또는 First In, Last Out (FILO) 방식을 따르는 자료구조입니다. 즉, 가장 마지막에 삽입된 요소가 가장 먼저 제거되는 방식으로 작동합니다.

2.2. 특징

• LIFO/FILO 방식: 마지막에 들어간 데이터가 가장 먼저 나옵니다.
• push, pop, peek 연산:
  • push: 스택의 맨 위에 요소를 추가합니다.
  • pop: 스택의 맨 위 요소를 제거하고 그 값을 반환합니다.
  • peek: 스택의 맨 위 요소를 조회합니다.
• 활용 사례:
  • 후위 표기식 계산
  • 함수 호출 관리
  • 웹 브라우저 방문 기록 관리
  • 취소/재실행 기능 구현

2.3. 예시 코드 (Java)

import java.util.Stack;

public class StackExample {

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

        stack.push(1); // 스택에 1 추가
        stack.push(2); // 스택에 2 추가
        System.out.println(stack.peek()); // 스택의 맨 위 요소 조회: 2
        stack.pop(); // 스택의 맨 위 요소 제거
        System.out.println(stack.peek()); // 스택의 맨 위 요소 조회: 1
    }
}

3. 큐

3.1. 개요

큐는 First In, First Out (FIFO) 방식을 따르는 자료구조입니다. 즉, 가장 먼저 삽입된 요소가 가장 먼저 제거되는 방식으로 작동합니다.

3.2. 특징

• FIFO 방식: 가장 먼저 들어간 데이터가 가장 먼저 나옵니다.
• offer/enqueue, poll/dequeue, peek 연산:
  • offer/enqueue: 큐의 끝에 요소를 추가합니다.
  • poll/dequeue: 큐의 첫 번째 요소를 제거하고 그 값을 반환합니다.
  • peek: 큐의 첫 번째 요소를 조회합니다.
• 활용 사례:
  • 프린터 출력 대기열 관리
  • 네트워크 패킷 전송 관리
  • 작업 처리 큐 (job queue)

3.3. 예시 코드 (Java)

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

public class QueueExample {

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

        queue.offer("첫 번째 문서"); // 큐에 1 추가
        queue.offer("두 번째 문서"); // 큐에 2 추가
        System.out.println(queue.peek()); // 큐의 첫 번째 요소 조회: 1
        queue.poll(); // 큐의 첫 번째 요소 제거
        System.out.println(queue.peek()); // 큐의 첫 번째 요소 조회: 2
    }
}

4. 덱

4.1. 개요

덱은 Double-Ended Queue의 줄임말로, 앞뒤 양쪽 방향에서 데이터를 추가하거나 제거할 수 있는 자료구조입니다. 스택과 큐의 기능을 모두 포함하며, 더욱 유연한 활용이 가능합니다.

4.2. 특징 (계속)

• addFirst/offerFirst, addLast/offerLast, removeFirst/pollFirst, removeLast/pollLast 연산:
  • addFirst/offerFirst: 덱의 앞쪽에 요소를 추가합니다.
  • addLast/offerLast: 덱의 뒤쪽에 요소를 추가합니다.
  • removeFirst/pollFirst: 덱의 앞쪽 요소를 제거하고 그 값을 반환합니다.
  • removeLast/pollLast: 덱의 뒤쪽 요소를 제거하고 그 값을 반환합니다.
• 활용 사례:
  • 브라우저 뒤로가기/앞으로가기 기능 구현
  • 텍스트 편집기에서 취소/재실행 기능 구현
  • 게임에서 카드 덱 관리

4.3. 예시 코드 (Java)

import java.util.Deque;
import java.util.LinkedList;

public class DequeExample {

    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();

        // 데이터 넣기 (addLast, addFirst)
        deque.addLast("뒤쪽에서 첫 번째");
        deque.addFirst("앞쪽에서 첫 번째");
        deque.addLast("뒤쪽에서 두 번째");

        System.out.println("현재 덱: " + deque);

        // 데이터 빼기 (removeFirst, removeLast)
        System.out.println("removeFirst: " + deque.removeFirst());
        System.out.println("removeLast: " + deque.removeLast());

        System.out.println("현재 덱: " + deque);
    }
}

5. 비교 분석

특징	스택 (Stack)	큐 (Queue)	덱 (Deque)
정의	LIFO (Last In First Out) 자료구조	FIFO (First In First Out) 자료구조	양쪽 끝에서 삽입과 삭제가 가능한 자료구조
주요 연산	- 삽입(push) - 삭제(pop)	- 삽입(enqueue) - 삭제(dequeue)	- 앞쪽 삽입(push front) - 앞쪽 삭제(pop front) - 뒤쪽 삽입(push back) - 뒤쪽 삭제(pop back)
특징	- 최근에 삽입된 항목이 가장 먼저 삭제됨	- 가장 먼저 삽입된 항목이 가장 먼저 삭제됨	- 양쪽 끝에서 삽입과 삭제를 모두 수행할 수 있음
장점	- 구현이 간단함 - 메모리 효율적 사용	- 간단하고 직관적인 자료구조	- 다양한 삽입 및 삭제 작업 지원
- 스택과 큐의 장점 모두 포함
단점	- 요소 접근이 제한적임 - 중간에 있는 요소 접근 불편	- 중간에 있는 요소 접근 불편	- 복잡한 구현 필요 - 메모리 사용 증가
사용 사례	- 함수 호출 스택 - 후위 표기법 계산	- 작업 큐 - BFS (너비 우선 탐색)	- 양방향 탐색이 필요한 알고리즘
- 캐시 구현
복잡도	- 삽입: O(1) - 삭제: O(1)	- 삽입: O(1) - 삭제: O(1)	- 삽입: O(1) - 삭제: O(1)

이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

스택, 큐, 덱은 각각 서로 다른 특징과 장단점을 가지고 있으며, 다양한 문제 해결에 활용될 수 있습니다. 문제의 특성을 고려하여 적절한 자료구조를 선택하는 것이 중요합니다.

• 스택: LIFO/FILO 방식으로 데이터를 관리해야 하는 경우 적합합니다.
• 큐: FIFO 방식으로 데이터를 관리해야 하는 경우 적합합니다.
• 덱: 양방향으로 데이터를 관리해야 하거나, 더욱 유연한 기능이 필요한 경우 적합합니다.