#java, #stack, #deque

Java 의 Stack λŒ€μ‹  Deque

(자료 좜처 : https://www.campingdelaplagebenodet.com/237-actualites/3019-fred-magic-spectacle-magie-loctudy.html)

πŸ€Ήβ€β™€οΈ

μžλ°”μ—μ„œ 자료ꡬ쑰 Stack 을 λŒ€μ‹ ν•΄μ„œ μ‚¬μš©ν•˜λŠ” Deque 에 λŒ€ν•΄μ„œ μ•Œμ•„λ³΄μž. 이 글은 κΈ°λŠ₯을 μ‚¬μš©ν•˜λŠ” 방식이 μ•„λ‹Œ β€˜μ™œ Stack λŒ€μ‹  Deque λ₯Ό μ‚¬μš©ν•΄μ•Ό ν•˜λŠ”κ°€?β€˜μ— λŒ€ν•΄μ„œ μ„€λͺ…ν•œλ‹€.

Stack

ν›„μž…μ„ μΆœ(Last In First Out, λ‚˜μ€‘μ— λ“€μ–΄κ°„ 값이 λ¨Όμ € λ‚˜μ˜¨λ‹€) 자료ꡬ쑰λ₯Ό κ΅¬ν˜„ν•œ μžλ°”μ˜ ν΄λž˜μŠ€λ‹€. μžλ°”μ˜ Stack 은 List Collection 의 Vector λ₯Ό 상속받은 μŠ€νƒ λ©”λͺ¨λ¦¬ ꡬ쑰의 클래슀λ₯Ό μ œκ³΅ν•œλ‹€. λ°°μ—΄ 기반 데이터 ꡬ쑰둜 인덱슀둜 μš”μ†Œμ— μ•‘μ„ΈμŠ€ ν•  수 μžˆλ‹€.

public class Application {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("첫 번째 μš”μ†Œ");
        stack.push("두 번째 μš”μ†Œ");
        System.out.println(stack.pop());
    }
}   
// μ‹€ν–‰ κ²°κ³Ό
// > Task :Application.main()
// 두 번째 μš”μ†Œ

Queue

μ„ μž…μ„ μΆœ(First In First Out, λ¨Όμ € λ“€μ–΄κ°„ 값이 λ¨Όμ € λ‚˜μ˜¨λ‹€) 자료ꡬ쑰λ₯Ό κ΅¬ν˜„ν•œ μžλ°”μ˜ μΈν„°νŽ˜μ΄μŠ€λ‹€. 인덱슀둜 μš”μ†Œμ— 접근이 λΆˆκ°€λŠ₯ν•˜λ‹€.

Deque

Queue μΈν„°νŽ˜μ΄μŠ€λ₯Ό ν™•μž₯ν•œ μΈν„°νŽ˜μ΄μŠ€λ‹€. 자료의 μž…μΆœλ ₯을 μ–‘ λμ—μ„œ ν•  수 μžˆλ‹€. 인덱슀둜 μš”μ†Œμ— μ•‘μ„ΈμŠ€, μ‚½μž…, 제거λ₯Ό ν—ˆμš©ν•˜μ§€ μ•ŠλŠ”λ‹€.

public class Application {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("첫 번째 μš”μ†Œ"); // "첫 번째 μš”μ†Œ"
        deque.add("두 번째 μš”μ†Œ"); // "첫 번째 μš”μ†Œ", "두 번째 μš”μ†Œ"
        deque.push("μ„Έ 번째 μš”μ†Œ"); // "μ„Έ 번째 μš”μ†Œ", "첫 번째 μš”μ†Œ", "두 번째 μš”μ†Œ"
        System.out.println(deque.pop());
        System.out.println(deque.pop());
    }
}
// μ‹€ν–‰ κ²°κ³Ό
// > Task :Application.main()
// μ„Έ 번째 μš”μ†Œ
// 첫 번째 μš”μ†Œ

Stack vs Deque

곡식 λ¬Έμ„œλŠ” μ΄λ ‡κ²Œ λ§ν•˜κ³  μžˆλ‹€.

λ”μš± μ™„μ „ν•˜κ³  μΌκ΄€λœ LIFO μŠ€νƒ μž‘μ—…μ€ Deque μΈν„°νŽ˜μ΄μŠ€ 및 ν•΄λ‹Ή κ΅¬ν˜„μ„ μ‚¬μš©ν•˜μ—¬ κ΅¬ν˜„ν•˜λŠ” 것이닀.

즉, Stack λŒ€μ‹  Deque 의 κ΅¬ν˜„μ²΄μΈ ArrayDeque μ‚¬μš©μ„ μ œμ•ˆν•˜κ³  μžˆλ‹€. Java μ—μ„œ Vector λŠ” νŠΉμ • μƒν™©μ—μ„œ νš¨μœ¨μ μ΄μ§€ μ•ŠκΈ° λ•Œλ¬Έμ— Thread Safe μ•Šλ‹€κ³  ν•  수 μžˆλ‹€. κ·Έλ ‡κΈ° λ•Œλ¬Έμ— Vector λ₯Ό 상속받은 Stack 은 λ‹€μŒκ³Ό 같은 단점이 μ‘΄μž¬ν•œλ‹€.

  • 초기 μš©λŸ‰ 섀정을 μ§€μ›ν•˜μ§€ μ•ŠλŠ”λ‹€.
  • λͺ¨λ“  μž‘μ—…μ— Lock 이 μ‚¬μš©λœλ‹€.

    • 단일 μŠ€λ ˆλ“œ μ‹€ν–‰ μ„±λŠ₯이 μ €ν•˜ 될 수 μžˆλ‹€.
    • λ‹¨μˆœν•œ Iterator 의 탐색 μž‘μ—…μ—μ„œλ„ get() λ©”μ„œλ“œ μ‹€ν–‰ μ‹œ 맀번 Lock 이 λ°œμƒν•˜κ²Œ λ˜λ―€λ‘œ μ˜€λ²„ν—€λ“œκ°€ 컀진닀.
  • Stack 은 Vector μƒμ†λ°›μ•˜κΈ° λ•Œλ¬Έμ— 닀쀑 상속을 μ§€μ›ν•˜μ§€ μ•ŠλŠ”λ‹€.

Deque μΈν„°νŽ˜μ΄μŠ€λ₯Ό μ‚¬μš©ν•˜λ©΄ ν•„μš”ν•œ λͺ¨λ“  μŠ€νƒ μž‘μ—…μ„ μ œκ³΅ν•˜κΈ° λ•Œλ¬Έμ— νŽΈλ¦¬ν•˜λ‹€. λ˜ν•œ, μž‘μ—…μ— Lock 을 μ‚¬μš©ν•˜μ§€ μ•ŠκΈ° λ•Œλ¬Έμ— 단일 μŠ€λ ˆλ“œμ—μ„œλ„ λ¬Έμ œκ°€ λ°œμƒν•˜μ§€ μ•ŠλŠ”λ‹€. λ‹€λ§Œ, 닀쀑 μŠ€λ ˆλ“œ μ‹€ν–‰μ˜ 경우 λ¬Έμ œκ°€ 될 수 μžˆμ§€λ§Œ ArrayDeque 에 λŒ€ν•œ 동기화 λ°μ½”λ ˆμ΄ν„°λ₯Ό κ΅¬ν˜„ν•  수 μžˆλ‹€. λ°μ½”λ ˆμ΄ν„°λŠ” λ©”μ„œλ“œκ°€ μ‹€ν–‰λ˜κΈ° 전에 λ¨Όμ € μ‹€ν–‰λ˜λŠ” λ©”μ„œλ“œλ₯Ό λ§ν•˜λŠ”λ° 이에 λŒ€ν•œ μ˜ˆμ‹œλ₯Ό λ‹€λ£¨κΈ°μ—λŠ” λ‚΄μš©μ΄ λ°©λŒ€ν•΄μ§€λ―€λ‘œ κΆκΈˆν•˜λ‹€λ©΄ μ—¬κΈ°μ—μ„œ 확인해보면 λœλ‹€. μ΄λŠ” JCF 의 Stack ν΄λž˜μŠ€μ™€ μœ μ‚¬ν•˜κ²Œ μˆ˜ν–‰λ˜μ§€λ§Œ, Stack 클래슀의 초기 μš©λŸ‰ μ„€μ • λΆ€μ‘± 문제λ₯Ό ν•΄κ²°ν–ˆλ‹€. Stack 은 초기 μš©λŸ‰μ„ μ„€μ •ν•  수 μžˆλŠ” μƒμ„±μžκ°€ μ—†κΈ° λ•Œλ¬Έμ— λ°μ΄ν„°μ˜ μ‚½μž…μ΄ λ§Žμ•„μ§€λ©΄ 배열을 λ³΅μ‚¬ν•˜λŠ” 상황이 λΉˆλ²ˆν•˜κ²Œ λ°œμƒν•œλ‹€. ArrayDeque 은 μƒμ„±μžλ‘œ λ°°μ—΄μ˜ 초기 크기λ₯Ό 지정할 수 있고 μš©λŸ‰μ΄ μ΄ˆκ³Όν•˜λ©΄ κΈ°μ‘΄ μš©λŸ‰μ˜ 2배둜 λŠ˜λ €μ£Όκ±°λ‚˜ μ€„μ—¬μ£ΌλŠ” 둜직이 μ‘΄μž¬ν•œλ‹€.

μŠ€λ ˆλ“œ μ•ˆμ •μ„±

데이터 ꡬ쑰가 Thread Safe ν•˜μ§€ μ•Šμ€ 경우 λ™μ‹œμ— μ•‘μ„ΈμŠ€ν•˜λ©΄ 경쟁 쑰건이 λ°œμƒν•  수 μžˆλ‹€. μ•„λž˜ μ˜ˆμ‹œλ₯Ό 톡해 μ‚΄νŽ΄λ³΄μž.

  • 첫 번째 μŠ€λ ˆλ“œκ°€ μ½”λ“œ A λ₯Ό μ‹€ν–‰ν•œλ‹€.
  • 두 번째 μŠ€λ ˆλ“œκ°€ μ½”λ“œ A λ₯Ό μ‹€ν–‰ν•œλ‹€. 두 μŠ€λ ˆλ“œ λͺ¨λ‘ 같은 object κ°€ λ‹΄κΈ΄λ‹€.
  • 첫 번째 μŠ€λ ˆλ“œκ°€ μ½”λ“œ B λ₯Ό μ‹€ν–‰ν•œλ‹€.
  • 두 번째 μŠ€λ ˆλ“œκ°€ μ½”λ“œ B λ₯Ό μ‹€ν–‰ν•œλ‹€. μ‹€μ œ μ μš©λ˜λŠ” 것은 μΈλ±μŠ€κ°€ 총 2 번 바뀐닀.
  • 첫 번째 μŠ€λ ˆλ“œκ°€ μ½”λ“œ C λ₯Ό μ‹€ν–‰ν•œλ‹€.
  • 첫 번째 μŠ€λ ˆλ“œκ°€ μ½”λ“œ C λ₯Ό μ‹€ν–‰ν•œλ‹€. 두 μŠ€λ ˆλ“œ λͺ¨λ‘ 같은 object κ°€ λ°˜ν™˜λœλ‹€.
public class MyDeque {
    transient Object[] elements;
    transient int head;
    transient int length;

    public Object pollFirst() {
        Object object = elements[head]; // μ½”λ“œ A
        if (object != null) {
            elements[head] = null;
            head = head + 1; // μ½”λ“œ B
            length = length - 1;
        }
        return object; // μ½”λ“œ C
    }
}

각각 λ©”μ„œλ“œλ₯Ό μ‹€ν–‰ν•  λ•Œλ§ˆλ‹€ λ‹€λ₯Έ 값이 λ°˜ν™˜λ˜μ–΄μ•Ό ν•˜μ§€λ§Œ μœ„μ™€ 같이 λ™μΌν•œ 객체가 λ°˜ν™˜λ˜λŠ” λ¬Έμ œκ°€ λ°œμƒν•˜λŠ” 것을 μ•Œ 수 μžˆλ‹€. μ΄λŸ¬ν•œ κ²½ν•© μƒνƒœλ₯Ό ν”Όν•˜κΈ° μœ„ν•΄μ„œ μ½”λ“œ Bμ—μ„œ 인덱슀 μž¬μ„€μ •μ„ μ™„λ£Œν•  λ•ŒκΉŒμ§€ μ½”λ“œ A λ₯Ό μ‹€ν–‰ν•˜μ§€ μ•Šμ•„μ•Ό ν•œλ‹€.

μ–΄λ–€ κ΅¬ν˜„μ²΄λ₯Ό μ‚¬μš©ν• κΉŒ?

λ©€ν‹°μŠ€λ ˆλ“œ ν™˜κ²½κ³Ό 상관없이 μžλ°”μ—μ„œμ˜ Stack 은 λŒ€λΆ€λΆ„μ˜ μ‘°κ±΄μ—μ„œ μ„±λŠ₯ μ €ν•˜λ₯Ό μΌμœΌν‚€κΈ° λ•Œλ¬Έμ— μ‚¬μš©μ„ μ§€μ–‘ν•œλ‹€. λŒ€μ‹ μ— Deque 의 κ΅¬ν˜„μ²΄λ₯Ό μ‚¬μš©ν•œλ‹€. 일반적으둜 μ‚¬μš©ν•˜λŠ” Deque 의 κ΅¬ν˜„μ²΄λŠ” ArrayDeque κ³Ό LinkedList κ°€ μžˆλ‹€. λ‘˜μ˜ 차이점을 μ‚΄νŽ΄λ³΄μž.

  • ArrayDeque 은 Deque μΈν„°νŽ˜μ΄μŠ€μ˜ κ΅¬ν˜„μ²΄μ΄λ©° 크기가 μž¬μ„€μ •μ„ ν•  수 μžˆλ‹€.
  • LinkedList λŠ” List 의 κ΅¬ν˜„μ²΄λ‹€.
  • LinkedList λŠ” null μš”μ†Œλ₯Ό μΆ”κ°€ν•  수 μžˆμ§€λ§Œ ArrayDeque 은 λΆˆκ°€λŠ₯ν•˜λ‹€.
  • LinkedList λŠ” λ°˜λ³΅μ€‘μ— ν˜„μž¬ μš”μ†Œλ₯Ό μ œκ±°ν•˜λŠ” 것이 효율적이고, ArrayDeque 은 μ–‘μͺ½ λμ—μ„œ μΆ”κ°€, μ œκ±°κ°€ νš¨μœ¨μ μ΄λ‹€.
  • LinkedList λŠ” ArrayDeque 보닀 더 λ§Žμ€ λ©”λͺ¨λ¦¬λ₯Ό μ†Œλͺ¨ν•œλ‹€.
  • λ©”λͺ¨λ¦¬ μ†Œλͺ¨λŸ‰μ΄ 적을 λ•ŒλŠ” iterate 효율이 쒋은 ArrayDeque λ₯Ό μ‚¬μš©ν•˜κ³  μŠ€νƒμ˜ μ‚¬μ΄μ¦ˆκ°€ μ»€μ§€κ±°λ‚˜ μ‹¬ν•œ 변동이 μ˜ˆμƒλ  λ•ŒλŠ” 즉각적인 λ©”λͺ¨λ¦¬ 곡간 확보λ₯Ό μœ„ν•΄ LinkedList λ₯Ό μ‚¬μš©ν•œλ‹€.

λ©€ν‹°μŠ€λ ˆλ“œ ν™˜κ²½

λ©€ν‹°μŠ€λ ˆλ“œ ν™˜κ²½μ—μ„œλŠ” μŠ€λ ˆλ“œλ‘œλΆ€ν„° μ•ˆμ „ν•œ Deque 을 μ‚¬μš©ν•΄μ•Ό ν•œλ‹€. 이 κ²½μš°μ—λŠ” 각각 LinkedBlockingDeque 와 ConcurrentLinkedDeque λ₯Ό μ‚¬μš©ν•˜λ©΄ λœλ‹€. λ‘˜μ€ Thread-Safe ν•˜λ‹€λŠ” 곡톡점이 μžˆμ§€λ§Œ, λ™μ‹œ 잠금 λ™μž‘ μΈ‘λ©΄μ—μ„œ 차이점이 μžˆλ‹€. LinkedBlockingDequeλŠ” 잠금 λ©”μ»€λ‹ˆμ¦˜μ„ μ‚¬μš©ν•˜μ—¬ ν•œ λ²ˆμ— 단일 μŠ€λ ˆλ“œμ—μ„œλ§Œ 데이터λ₯Ό μž‘λ™ν•  수 μžˆλ„λ‘ ν•  λ•Œ μ‚¬μš©ν•œλ‹€. ConcurrentLinkedDequeλŠ” 각각의 μŠ€λ ˆλ“œκ°€ 곡유 데이터에 μ•‘μ„ΈμŠ€ ν•  수 μžˆλ„λ‘ ν•  λ•Œ μ‚¬μš©ν•œλ‹€. λ˜ν•œ 데이터λ₯Ό μž‘λ™ν•  λ•Œ μ„±λŠ₯에 영ν–₯을 λ―ΈμΉ  수 μžˆλ‹€λŠ” 차이점이 μžˆλ‹€.

κ²°λ‘ 

λŒ€λΆ€λΆ„μ˜ μƒν™©μ—μ„œλŠ” Deque 을 μ‚¬μš©ν•  λ•Œ LinkedList λ³΄λ‹€λŠ” ArrayDeque 을 μ‚¬μš©ν•˜λ©΄ λœλ‹€. λ˜ν•œ λ©€ν‹°μŠ€λ ˆλ“œ ν™˜κ²½μ—μ„œ λ‹¨μΌμŠ€λ ˆλ“œλ₯Ό μ‚¬μš©ν•  κ³„νšμ΄λΌλ©΄ LinkedBlockingDequeλ₯Ό μ‚¬μš©ν•˜κ³  λ©€ν‹°μŠ€λ ˆλ“œλ₯Ό μ‚¬μš©ν•  κ³„νšμ΄λΌλ©΄ ConcurrentLinkedDequeλ₯Ό μ‚¬μš©ν•˜λ©΄ λœλ‹€.

μ°Έκ³