- 후입선출(
LIFO
: Last In First Out): 나중에 넣은 객체가 먼저 빠져나가는 자료구조- 선입선출(
FIFO
: First In First Out): 먼저 넣은 객체가 먼저 빠져나가는 자료구조
컬렉션 프레임워크에는 LIFO 자료구조를 제공하는 스택
Stack
클래스와
FIFO 자료구조를 제공하는 큐Queue
인터페이스를 제공하고 있다.
![]()
JVM 스택 메모리
가 스택을 응용한 대표적인 예이다.스레드풀(ExecutorService)의 작업 큐
는 큐를 응용한 대표적인 예이다.Stack 클래스는 LIFO 자료구조를 구현한 클래스이다.
![]()
저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 된다.
Stack<E> stack = new Stack<E>();
public class Coin {
private int value;
public Coin(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
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
더욱 복잡하고 빠른 스택을 구현하고 싶다면
Deque 인터페이스를 구현한ArrayDeque
클래스를 사용하면 된다.Deque<Integer> st = new ArrayDeque<Integer>();
search()
메소드를 지원하지 않는다.Queue 인터페이스는 FIFO 자료구조에서 사용되는 메소드를 정의하고 있다.
![]()
Queue 인터페이스를 구현한 대표적인 클래스는 LinkedList
이다. LinkedList는 List 인터페이스를 구현했기 때문에 List 컬렉션이기도 하다.
다음 코드는 LinkedList 객체를 Queue 인터페이스 타입으로 변환한 것이다.
Queue<E> queue = new LinkedList<E>();
public class Message {
public String command;
public String to;
public Message(String command, String to) {
this.command = command;
this.to = to;
}
}
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를 보냅니다.
박님에게 카카오톡을 보냅니다.
"김"
→ "이"
→ "박"
"김"
→ "이"
→ "박"
더욱 복잡하고 빠른 큐를 구현하고 싶다면
Deque 인터페이스를 구현한ArrayDeque
클래스를 사용하면 된다.Deque<Integer> qu = new ArrayDeque<Integer>();
컬렉션 프레임워크의 대부분의 클래스들은 싱글 스레드 환경에서 사용할 수 있도록 설계되었다. 그렇기 때문에 여러 스레드가 동시에 컬렉션에 접근한다면 의도하지 않게 요소가 변경될 수 있는 불안전한 상태가 된다.
synchronizedXXX()
컬렉션 프레임워크는 비동기화된 메소드를 동기화된 메소드로 래핑하는 Collections의
synchronizedXXX()
메소드를 제공한다.
① 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>());
동기화된 컬렉션은 멀티 스레드 환경에서 하나의 스레드가 요소를 안전하게 처리하도록 도와주지만, 전체 요소를 빠르게 처리하지는 못한다.
하나의 스레드가 요소를 처리할 때 전체 잠금이 발생하여 다른 스레드는 대기 상태가 되기 때문에 멀티 스레드가 병렬적으로 컬렉션의 요소를 처리할 수 없다.
자바는 멀티 스레드가 컬렉션의 요소를 병렬적으로 처리할 수 있도록
java.util.concurrent
패키지의ConcurrentHashMap
과ConcurrentLinkedQueue
을 제공한다.
ConcurrentHashMap이
부분(segment) 잠금
을 사용하기 때문에
ConcurrentHashMap을 사용하면 스레드에 안전하면서도 멀티 스레드가 요소를 병렬적으로 처리할 수 있다.
Map<K, V> map = new ConcurrentHashMap<K, V>();
📌 전체 잠금 vs 부분 잠금
컬렉션에 10개의 요소가 저장되어 있을 경우,
- 1개를 처리할 동안 전체 10개의 요소를 다른 스레드가 처리하지 못하도록 하는 것을 전체 잠금,
- 처리하는 요소가 포함된 부분만 잠금하고 나머지 부분을 다른 스레드가 변경할 수 있도록 하는 것이 부분 잠금이다.
ConcurrentLinkedQueue는 락-프리(lock-free) 알고리즘을 구현한 컬렉션이다.
Queue<E> queue = new ConcurrentLinkedQueue<E>();
이것이 자바다
http://tcpschool.com/java/java_collectionFramework_stackQueue