[JAVA] Map / Stack / Queue

Map

• Map은 Key-Value 의 쌍을 저장하는 자료구조
• Key는 유일, Value는 중복 가능
• 같은 Key로 저장하면 Value 교체
• 순서를 유지하지 않음
• HashMap, LinkedMap, TreeMap 등 다양한 구현체 제공 (HashMap이 가장 널리 쓰인다)

Map 인터페이스의 주요 메서드 - 자바 공식문서

HashMap의 기본 사용법

public static void main(String[] args) {
    Map<String, Integer> studentMap = new HashMap<>();

    //학생 성적 데이터 추가
    studentMap.put("studentA", 90);
    studentMap.put("studentB", 80);
    studentMap.put("studentC", 80);
    studentMap.put("studentD", 100);
    System.out.println(studentMap);
    System.out.println();
    
    //특정 학생의 값 조회
    Integer result = studentMap.get("studentD");
    System.out.println("result = " + result);
    System.out.println();
    System.out.println("keySet 활용");
    Set<String> keySet = studentMap.keySet();
    for (String key : keySet) {
        Integer value = studentMap.get(key);
        System.out.println("key = " + key + " , value =  " + value);
    }
    System.out.println();
    
    //키 값을 묶은 것
    System.out.println("enrtySet 활용");
    Set<Map.Entry<String, Integer>> enrtySet = studentMap.entrySet();
    for (Map.Entry<String, Integer> entry : enrtySet) {
        String key = entry.getKey();
        Integer value = entry.getValue();
        System.out.println("key = " + key + " , value =  " + value);
    }
    System.out.println();
    
    System.out.println("values 활용");
    Collection<Integer> values = studentMap.values();
    for (Integer value : values) {
        System.out.println("value = " + value);
    }
}
//출력결과
{studentB=80, studentA=90, studentD=100, studentC=80}

result = 100

keySet 활용
key = studentB , value =  80
key = studentA , value =  90
key = studentD , value =  100
key = studentC , value =  80

enrtySet 활용
key = studentB , value =  80
key = studentA , value =  90
key = studentD , value =  100
key = studentC , value =  80

values 활용
value = 80
value = 90
value = 100
value = 80

Key 조회

Set<String> keySet = studentMap.keySet();

• Map의 Key는 중복을 허용 ❌ 그러므로 Map의 모든 키를 조회하는 KeySet(); 을 호출하면 중복을 허용하지 않는 자료구조인 Set을 반환

Key 와 Value 조회

Set<Map.Entry<String, Integer>> enrtySet = studentMap.entrySet();

• entrySet(); 은 Key와 Value 쌍으로 이루어진 객체 Entry는 Map 내부에서 Key와 value 를 묶어 저장
• Map에 Key와 Value로 값을 저장하면 Map 내부에서 entry 객체를 만들어 보관
• 하나의 Map에 여러 entry 저장 가능

Value 조회

Collection<Integer> values = studentMap.values();

• Map의 값은 중복 ⭕ 그러므로 Set으로 반환 불가, 순서 보장하는 List도 애매
• 단순 값을 반환하는 Collection 사용

Map VS Set

Map의 Key가 Set과 같은 구조이다. Map과 Set은 거의 같지만 Value의 유무 차이만 존재

Set과 Map의 구현체도 거의 같다.

• HashSet → HashMap
  • HashSet의 구현 대부분은 HashMap의 구현을 가져다 사용 Map에서 Value만 비워두면 Set처럼 사용할 수 있다.
• TreeSet → TreeMap
• LinkedHastSet → LinkedHashMap

HashMap

• hash를 사용해 요소 저장
• Key값은 해시 함수를 통해 해시 코드로 변환되고 이 해시 코드는 값을 저장하고 검색하는데 사용된다.
• O(1) 의 복잡도
• 순서를 보장하지 않음

public static void main(String[] args) {
    HashMap<String, Integer> map = new HashMap<>();
    map.put("Z", 26);
    map.put("A", 1);
    map.put("M", 13);
    map.put("B", 2);
    System.out.println(map);
}
//출력결과
{A=1, B=2, Z=26, M=13}

LinkedHashMap

• 연결 리스트를 사용해 삽입순서, 최근 접근 순서에 따라 요소 유지
• HashMap과 같지만 입력 순서를 링크로 유지하기 때문에 조금 더 무거움
• 대부분 O(1) 의 복잡도
• 순서를 보장함

public static void main(String[] args) {
    LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
    map.put("Z", 26);
    map.put("A", 1);
    map.put("M", 13);
    map.put("B", 2);
    System.out.println(map);
}
//출력결과
{Z=26, A=1, M=13, B=2}

TreeMap

• 레드-블랙 트리 기반으로 한 구현
• 모든 키는 자연 순서, 생성자에 제공된 Comparator에 의해 정렬
• get, put, remove 와 같은 주요 작업은 O(log n) 의 복잡도
• 키는 정렬 순서로만 저장

public static void main(String[] args) {
    TreeMap<String, Integer> map = new TreeMap<>();
    map.put("Z", 26);
    map.put("A", 1);
    map.put("M", 13);
    map.put("B", 2);
    System.out.println(map);
}
//출력결과
{A=1, B=2, M=13, Z=26}

Stack

가장 마지막에 넣은 D가 먼저나오는 후입선출 이라 한다. 이런 자료구조를 Stack 이라 한다.

블럭을 넣을 땐 A → B → C → D

블럭을 뺄땐 D → C → B → A

전통적으로 값을 넣을 땐 push, 값을 뺄땐 pop 이라 한다.

public static void main(String[] args) {
    Stack<String> stack = new Stack<>();
    stack.push("A");
    stack.push("B");
    stack.push("C");
    stack.push("D");
    System.out.println(stack);

    System.out.println("다음 꺼낼 요소 확인만 = " + stack.peek());

    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());
    System.out.println(stack);
}
//출력결과
[A, B, C, D]
다음 꺼낼 요소 확인만 = D
stack.pop() = D
stack.pop() = C
stack.pop() = B
stack.pop() = A
[]

push →  ┌─────┐  ← pop
        │  D  │  (top)
        ├─────┤
        │  C  │
        ├─────┤
        │  B  │
        ├─────┤
        │  A  │  (bottom)
        └─────┘

Stack 클래스는 사용하지 말 것. 자바 1.0 때 개발되어 오래됐기 때문에 지금은 더 빠르고 좋은 자료구조가 많다.. 대신 Deque를 사용하자

Queue

가장 먼저 넣은 데이터가 먼저 나오는 선입선출 구조 마치 줄을 서서 기다리는것 같다.

전통적으로 큐에 데이터를 넣는 것을 offer, 값을 꺼내는 것을 poll이라 한다.

public static void main(String[] args) {
    Queue<String> queue = new ArrayDeque<>();
    queue.offer("A");
    queue.offer("B");
    queue.offer("C");
    queue.offer("D");
    System.out.println(queue);

    System.out.println("다음 꺼낼 요소 확인만 = " + queue.peek());

    System.out.println("queue.poll() = " + queue.poll());
    System.out.println("queue.poll() = " + queue.poll());
    System.out.println("queue.poll() = " + queue.poll());
    System.out.println("queue.poll() = " + queue.poll());
    System.out.println(queue);
}
//출력결과
[A, B, C, D]
다음 꺼낼 요소 확인만 = A
queue.poll() = A
queue.poll() = B
queue.poll() = C
queue.poll() = D
[]

enqueue →  ┌─────┬─────┬─────┬─────┐  → dequeue
    (rear) │  D  │  C  │  B  │  A  │ (front)
           └─────┴─────┴─────┴─────┘

Dequq

양쪽 끝에서 요소를 추가하거나 제거할 수 있다. Dequq는 Queue와 Stack 기능을 모두 포함(양방향 Queue) 하고 있어 매우 유연한 자료구조 이다. 데크, 덱 이라고 불린다.

public static void main(String[] args) {
    Deque<String> deque = new ArrayDeque<>();
    deque.offerFirst("B");
    System.out.println(deque);

    deque.offerLast("C");
    System.out.println(deque);

    deque.offerFirst("A");
    System.out.println(deque);

    deque.offerLast("D");
    System.out.println(deque);

    System.out.println("안꺼내고 단순조회만 " + deque.peekFirst());
    System.out.println("안꺼내고 단순조회만 " + deque.peekLast());

    System.out.println("pollFirst() = " + deque.pollFirst());
    System.out.println("pollFirst() = " + deque.pollFirst());
    System.out.println("pollLast() = " + deque.pollLast());
    System.out.println("pollLast() = " + deque.pollLast());
    System.out.println(deque);
}
//출력결과
[B]
[B, C]
[A, B, C]
[A, B, C, D]
안꺼내고 단순조회만 A
안꺼내고 단순조회만 D
pollFirst() = A
pollFirst() = B
pollLast() = D
pollLast() = C
[]

addFirst ←  ┌─────┬─────┬─────┬─────┐  → addLast
removeFirst │  A  │  B  │  C  │  D  │    removeLast
            └─────┴─────┴─────┴─────┘
           (front)              (rear)

Deque의 구현체

대표적으로 ArrayDeque, LinkedList 가 있다. 둘 중 ArrayDeque 가 더 빠르므로 ArrayDeque를 사용하자

Deque의 특징

Deque는 Stack, Queue 의 역할 모두 수행할 수 있다.

public static void main(String[] args) {
    //Stack으로 사용 (LIFO)
    Deque<String> deque = new ArrayDeque<>();
    deque.push("A");
    deque.push("B");
    deque.push("C");
    while (!deque.isEmpty()) {
        System.out.print(deque.pop() + " ");
    }
}
//출력결과
C B A

• Deque 에서 Stack을 사용할 수 있게 메서드를 제공한다. 하지만 자바의 Stack은 성능이 좋지 않고 하위호환만을 위해 남겨놨기 때문에 Stack 자료구조가 필요하면 Deque의 ArrayDeque 구현체를 사용하자.

public static void main(String[] args) {
    //Stack으로 사용 (LIFO)
    Deque<String> deque = new ArrayDeque<>();
    deque.push("A");
    deque.push("B");
    deque.push("C");
    while (!deque.isEmpty()) {
        System.out.print(deque.pop() + " ");
    }

    //Queue로 사용 (FIFO)
    Deque<String> queue = new LinkedList<>();
    queue.offer("A");
    queue.offer("B");
    queue.offer("C");
    while (!queue.isEmpty()) {
        System.out.print(queue.poll() + " ");
    }
}
//출력 결과
A B C 

• Deque 에서 Queue를 사용할 수 있게 메서드를 제공한다. 성능이 빠른 ArrayDeque를 사용하자!

출처: 김영한의 실전 자바 - 중급 2편