[Java] 컬렉션 프레임워크 ⑥

[ LIFO와 FIFO 컬렉션 ]

• 후입선출(LIFO: Last In First Out): 나중에 넣은 객체가 먼저 빠져나가는 자료구조
• 선입선출(FIFO: First In First Out): 먼저 넣은 객체가 먼저 빠져나가는 자료구조

컬렉션 프레임워크에는 LIFO 자료구조를 제공하는 스택 Stack 클래스와
FIFO 자료구조를 제공하는 큐 Queue 인터페이스를 제공하고 있다.

• JVM 스택 메모리가 스택을 응용한 대표적인 예이다.
  • 스택 메모리에 저장된 변수는 나중에 저장된 것부터 제거된다.
• 스레드풀(ExecutorService)의 작업 큐는 큐를 응용한 대표적인 예이다.
  • 작업 큐는 먼저 들어온 작업부터 처리한다.

1. Stack

Stack 클래스는 LIFO 자료구조를 구현한 클래스이다.

✅ Stack 주요 메소드

✅ Stack 객체 생성 방법

저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 된다.

Stack<E> stack = new Stack<E>();

✅ 예제 | Stack을 이용한 동전케이스

• Coin (동전 클래스)

public class Coin {
    private int value;

    public Coin(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }
}

• StackExample (Stack을 이용한 동전케이스)

import java.util.Stack;

public class CoinExample {
    public static void main(String[] args) {
        Stack<Coin> coinBox = new Stack<Coin>();

        coinBox.push(new Coin(100));
        coinBox.push(new Coin(50));
        coinBox.push(new Coin(500));
        coinBox.push(new Coin(10));

        while (!coinBox.isEmpty()) {
            Coin coin = coinBox.pop();
            System.out.println("꺼내온 동전: " + coin.getValue() + "원");
        }

    }
}

• 실행 결과

꺼내온 동전: 10원
꺼내온 동전: 500원
꺼내온 동전: 50원
꺼내온 동전: 100원

• 삽입 순서: 100 → 50 → 500 → 10
• 출력 순서: 10 → 500 → 50 → 100

✅ ArrayDeque 사용

더욱 복잡하고 빠른 스택을 구현하고 싶다면
Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 된다.

Deque<Integer> st = new ArrayDeque<Integer>();

• ArrayDeque 클래스는 Stack 클래스와는 달리 search() 메소드를 지원하지 않는다.

2. Queue

Queue 인터페이스는 FIFO 자료구조에서 사용되는 메소드를 정의하고 있다.

✅ Queue 주요 메소드

✅ LinkedList 객체를 Queue 인터페이스 타입으로 변환

Queue 인터페이스를 구현한 대표적인 클래스는 LinkedList이다. LinkedList는 List 인터페이스를 구현했기 때문에 List 컬렉션이기도 하다.

다음 코드는 LinkedList 객체를 Queue 인터페이스 타입으로 변환한 것이다.

Queue<E> queue = new LinkedList<E>();

✅ 예제 | Queue를 이용한 메시지 큐

• Message (Message 클래스)

public class Message {
    public String command;
    public String to;

    public Message(String command, String to) {
        this.command = command;
        this.to = to;
    }
}

• QueueExample (Queue를 이용한 메시지 큐)

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

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

        messageQueue.offer(new Message("sendMail", "김"));
        messageQueue.offer(new Message("sendSMS", "이"));
        messageQueue.offer(new Message("sendKakaotalk", "박"));

        while (!messageQueue.isEmpty()) {
            Message message = messageQueue.poll();
            switch (message.command) {
                case "sendMail":
                    System.out.println(message.to + "님에게 메일을 보냅니다.");
                    break;
                case "sendSMS":
                    System.out.println(message.to + "님에게 SMS를 보냅니다.");
                    break;
                case "sendKakaotalk":
                    System.out.println(message.to + "님에게 카카오톡을 보냅니다.");
                    break;
            }
        }
    }
}

• 실행 결과

김님에게 메일을 보냅니다.
이님에게 SMS를 보냅니다.
박님에게 카카오톡을 보냅니다.

• 삽입 순서: "김" → "이" → "박"
• 출력 순서: "김" → "이" → "박"

✅ ArrayDeque 사용

더욱 복잡하고 빠른 큐를 구현하고 싶다면
Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 된다.

Deque<Integer> qu = new ArrayDeque<Integer>();

---

[ 동기화된 컬렉션 ]

컬렉션 프레임워크의 대부분의 클래스들은 싱글 스레드 환경에서 사용할 수 있도록 설계되었다. 그렇기 때문에 여러 스레드가 동시에 컬렉션에 접근한다면 의도하지 않게 요소가 변경될 수 있는 불안전한 상태가 된다.

• Vector와 Hashtable은 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드 환경에서 안전하게 요소를 처리할 수 있지만,
• ArrayList와 HashSet, HashMap은 동기화된 메소드로 구성되어 있지 않아 멀티 스레드 환경에서 안전하지 않다.

✅ 비동기화된 메소드 동기화된 메소드로 래핑하기 - synchronizedXXX()

컬렉션 프레임워크는 비동기화된 메소드를 동기화된 메소드로 래핑하는 Collections의 synchronizedXXX() 메소드를 제공한다.

• 매개값으로 비동기화된 컬렉션을 대입하면 동기화된 컬렉션을 리턴해준다.
• ArrayList, HashSet, HashMap을 싱글 스레드 환경에서 사용하다가 멀티 스레드 환경으로 전달해야 할 상황이 생길 때를 대비한 것이다.

① ArrayList를 Collections.synchronizedList() 메소드를 사용해서 동기화된 List로 변환

List<T> list = Collections.synchronizedList(new ArrayList<T>());

② HashSet을 Collections.synchronizedSet() 메소드를 사용해서 동기화된 Set으로 변환

Set<E> set = Collections.synchronizedSet(new HashSet<E>());

③ HashMap을 Collections.synchronizedMap() 메소드를 사용해서 동기화된 Map으로 변환

Map<K, V> map = Collections.synchronizedMap(new HashMap<K, V>());

---

[ 병렬 처리를 위한 컬렉션 ]

동기화된 컬렉션은 멀티 스레드 환경에서 하나의 스레드가 요소를 안전하게 처리하도록 도와주지만, 전체 요소를 빠르게 처리하지는 못한다.

하나의 스레드가 요소를 처리할 때 전체 잠금이 발생하여 다른 스레드는 대기 상태가 되기 때문에 멀티 스레드가 병렬적으로 컬렉션의 요소를 처리할 수 없다.

ConcurrentHashMap, ConcurrentLinkedQueue

자바는 멀티 스레드가 컬렉션의 요소를 병렬적으로 처리할 수 있도록 java.util.concurrent 패키지의 ConcurrentHashMap과 ConcurrentLinkedQueue을 제공한다.

• ConcurrentHashMap은 Map 구현 클래스이고, ConcurrentLinkedQueue는 Queue 구현 클래스이다.

✅ ConcurrentHashMap

ConcurrentHashMap이 부분(segment) 잠금을 사용하기 때문에
ConcurrentHashMap을 사용하면 스레드에 안전하면서도 멀티 스레드가 요소를 병렬적으로 처리할 수 있다.

• ConcurrentHashMap 객체 생성 방법은 다음과 같다.

Map<K, V> map = new ConcurrentHashMap<K, V>();

• 다른 Map 구현 객체와 마찬가지로 Map 인터페이스의 메소드를 호출하면 된다.

📌 전체 잠금 vs 부분 잠금

컬렉션에 10개의 요소가 저장되어 있을 경우,

• 1개를 처리할 동안 전체 10개의 요소를 다른 스레드가 처리하지 못하도록 하는 것을 전체 잠금,
• 처리하는 요소가 포함된 부분만 잠금하고 나머지 부분을 다른 스레드가 변경할 수 있도록 하는 것이 부분 잠금이다.

✅ ConcurrentLinkedQueue

ConcurrentLinkedQueue는 락-프리(lock-free) 알고리즘을 구현한 컬렉션이다.

• 락-프리 알고리즘은 여러 개의 스레드가 동시에 접근할 경우, 잠금을 사용하지 않고도 최소한 하나의 스레드가 안전하게 요소를 저장하거나 얻도록 해준다.
• ConcurrentLinkedQueue 객체 생성 방법은 다음과 같다.

Queue<E> queue = new ConcurrentLinkedQueue<E>();

• 다른 Queue 구현 객체와 마찬가지로 Queue 인터페이스의 메소드를 호출하면 된다.

---

[ 참고자료 ]

이것이 자바다
http://tcpschool.com/java/java_collectionFramework_stackQueue