23일차: 자료구조 (Stack, Queue)

❯ 자료구조

프로그래밍을 하다보면 다양한 데이터를 사용하게 된다.

데이터의 특징에 따라 체계적으로 정리하고 관리해야 데이터를 효율적으로 사용할 수 있다.

이렇게 데이터 묶음을 저장하고 사용하는 방법을 정의한 것을 자료구조라고 한다.

 

자료구조의 종류

위의 다양한 자료구조 중 자주 사용하는 자료구조는 Stack, Queue, Tree, Graph로 이 네가지에 대해 학습한다.

자료구조의 특성과 기능에 대해 알면 어떤 상황에서 어떠한 자료구조를 사용할수 있을지 알 수 있다.

 

특히, 학습을 위해 직접 해당 자료 구조를 사용자정의 클래스를 작성해보면서 기능을 익힐 예정이다.

❯ Stack

Stack 의 사전적 의미인 "쌓다. 쌓이다."처럼 데이터를 순서대로 쌓는 구조를 의미한다.

 

<특징>

• 가장 나중에 들어간 데이터가 가장 먼저 나온다.(LIFO, Lase In First Out) ex) 프링글스, 웹페이지 뒤로가기/앞으로가기 
• 입력과 출력이 하나의 방향에서 이루어진다. ex. 프링글스 통에서는 하나의 입구만 넣고 뺄 수 있다.
• 데이터는 한번에 하나씩만 넣고 뺄 수 있다.
• 데이터를 넣는것을 push, 꺼내는 것을 pop이라고 한다.

<장점>

• LIFO 구조를 가지므로, 스택에 저장된 데이터를 가져오는 속도가 매우 빠르다.(데이터 삽입, 삭제에 모든 데이터를 순회할 필요 없음)
• 자바에 Stack클래스가 구현되어있으므로 해당 클래스 바로 사용 가능 

<단점> - Java에서 제공하는 Stack 클래스 한정

• 자바의 Stack 클래스는 Vector 클래스를 상속받아 구현되므로 크기를 동적으로 조정하지 않는다.(크기가 자주 변하는 스택은 성능이 떨어질 수 있음)
• 자바의 Stack 클래스는 Vector를 상속받아 구현되므로, 중간에서 데이터 삽입/삭제가 가능하다.(스택의 의도된 동작을 방해할 수 있음) 

<코드 예시>

// 괄호를 포함한 계산기 구현하기

public class Calculator {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("수식을 입력하세요: ");
        String input = sc.nextLine();
        double result = evaluate(input);
        System.out.println("결과: " + result);
    }

    public static double evaluate(String expression) {
        Stack<Double> numbers = new Stack<>();
        Stack<Character> operators = new Stack<>();
        int len = expression.length();
        for (int i = 0; i < len; i++) {
            char ch = expression.charAt(i);
            if (Character.isDigit(ch)) {
                double num = ch - '0';
                while (i + 1 < len && Character.isDigit(expression.charAt(i + 1))) {
                    num = num * 10 + (expression.charAt(i + 1) - '0');
                    i++;
                }
                numbers.push(num);
            } else if (ch == '(') {
                operators.push(ch);
            } else if (ch == ')') {
                while (operators.peek() != '(') {
                    double result = applyOperation(operators.pop(), numbers.pop(), numbers.pop());
                    numbers.push(result);
                }
                operators.pop();
            } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                while (!operators.isEmpty() && hasPrecedence(ch, operators.peek())) {
                    double result = applyOperation(operators.pop(), numbers.pop(), numbers.pop());
                    numbers.push(result);
                }
                operators.push(ch);
            }
        }
        while (!operators.isEmpty()) {
            double result = applyOperation(operators.pop(), numbers.pop(), numbers.pop());
            numbers.push(result);
        }
        return numbers.pop();
    }

    public static double applyOperation(char operator, double b, double a) {
        switch (operator) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                if (b == 0) {
                    throw new UnsupportedOperationException("Cannot divide by zero");
                }
                return a / b;
        }
        return 0;
    }

    public static boolean hasPrecedence(char op1, char op2) {
        if (op2 == '(' || op2 == ')') {
            return false;
        }
        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) {
            return false;
        }
        return true;
    }
}

Queue

Queue 의 사전적 의미는 기다리는 줄, 대기행렬이라는 의미를 가진다. 이처럼 들어온 순서대로 나가는 구조를 의미한다.

 

<특징>

• 가장 먼저 들어간 데이터가 가장 먼저 나온다.(FIFO, First In First Out) ex) 인쇄 대기열
• 두개의 입출력 방향을 가진다.(한쪽으로 들어가고 다른 한쪽으로 나온다.)
• 데이터 넣는것을 enqueue, 꺼내는것을 dequeue 라고 한다.

Queue를 구현하고있는 대표적인 클래스 : LinkedList, AbstractQueue, PriorityQueue  등

 

<장점>

• 자료를 넣은 순서대로 처리 가능하므로, 처리해야할 작업이 여러개인 경우 효율적인 처리가 가능하다.
• 삽입과 삭제가 각각 양 끝에서 이루어지므로 다른 자료구조에 비해 상대적으로 속도가 빠르다.
• 자바에 Queue 클래스가 구현되어있으므로 해당 클래스 바로 사용 가능

<단점> - Java에서 제공하는 Queue 인터페이스 한정

• iterator() 메서드가 지원되지 않는다.(큐 데이터를 순회하려면 peek(), poll() 메서드를 통해 데이터를 차례로 가져와야함)
• remove(Object o) 메서드 동작이 불명확하다.(큐가 중복된 객체를 허용하는 경우 어떤 객체가 삭제되었는지 명확하지 않으므로 poll() 메서드를 사용하는것이 적절할 수 있음)

<코드예시>

// 5개의 선반을 가진 창고 구현하기
// 선반에 넣은 물건은 가장 먼저 넣은 물건부터 꺼낼 수 있음
// 선반이 비어있으면 물건을 그 선반에 보관하고 그렇지 않다면 다른 선반을 확인해서 물건을 보관함

public class Warehouse {
    private Queue<Integer>[] shelves; // Queue 배열 생성
    
    public Warehouse() {
        shelves = new Queue[5]; // 5개의 선반 생성
        for (int i = 0; i < 5; i++) {
            shelves[i] = new LinkedList<>(); // LinkedList로 Queue 생성
        }
    }
    
    public void store(int item) {
        boolean stored = false;
        for (Queue<Integer> shelf : shelves) { // 각 선반을 탐색
            if (shelf.size() < 3) { // 선반당 3개까지 보관 가능. 선반이 비어 있으면 물건 보관
                shelf.add(item);
                System.out.println(item + "이(가) " + (Arrays.asList(shelves).indexOf(shelf) + 1) + "번 선반에 보관되었습니다.");
                stored = true;
                break;
            }
        }
        if (!stored) { // 모든 선반이 차 있으면 보관 불가 메시지 출력
            System.out.println("보관할 수 있는 공간이 없습니다.");
        }
    }
    
    public int retrieve() {
        int item = -1; // 초기값 설정
        for (Queue<Integer> shelf : shelves) { // 각 선반을 탐색
            if (!shelf.isEmpty()) { // 물건이 있는 선반에서 꺼냄
                item = shelf.poll();
                System.out.println(item + "이(가) " + (Arrays.asList(shelves).indexOf(shelf) + 1) + "번 선반에서 꺼내졌습니다.");
                break;
            }
        }
        if (item == -1) { // 모든 선반이 비어 있으면 메시지 출력
            System.out.println("보관된 물건이 없습니다.");
        }
        return item;
    }
    
    public static void main(String[] args) {
        Warehouse warehouse = new Warehouse();
        Scanner scanner = new Scanner(System.in);
        
        while (true) {
            System.out.println("1. 물건 보관하기");
            System.out.println("2. 물건 꺼내기");
            System.out.println("3. 종료하기");
            System.out.print("원하는 작업의 번호를 입력하세요: ");
            int choice = scanner.nextInt();
            if (choice == 1) {
                System.out.print("보관할 물건의 번호를 입력하세요: ");
                int item = scanner.nextInt();
                warehouse.store(item);
            } else if (choice == 2) {
                warehouse.retrieve();
            } else if (choice == 3) {
                System.out.println("프로그램을 종료합니다.");
                break;
            } else {
                System.out.println("잘못된 입력입니다. 다시 입력해주세요.");
            }
            System.out.println();
        }
    }
}

---

오늘 배운 내용들과 이때까지 배운 내용들을 바탕으로 문제들을 풀어보게 되었다.

예전에 배운것들을 활용하는 내용이 많아서 복습에 도움이 돼서 좋았다.

코드를 작성하면서 조건의 배치 순서나 반복문의 위치에 따라 결과가 완전히 다르게 나타나는걸 볼 수 있었다.

전체 흐름을 보고 어떤 순서로 작업이 이루어야할지 단계적으로 생각하는 과정이 꼭 필요했다.

코드를 계속 실행시켜보고 발생하는 예외를 해결해나가는 과정도 재밌게 느껴졌다.

그렇지만 언젠가는 꼭! 한번만에 오류 없이 답을 작성할 수 있는 실력을 만들고싶다 :)