본문 바로가기
복습

[Java 복습] Deque와 Stack, Queue 자료 구조

쌈뽕코딩 2024. 5. 19. 22:14

목차

  • 스택 자료 구조
  • 큐 자료 구조
  • 디큐 자료 구조
  • Deque 구현체와 성능 테스트
  • Deque와 Stack, Queue

 

스택 자료 구조

 

스택(Stack) 구조
다음과 같은 1, 2, 3 이름표가 붙은 블록이 있다고 가정하자

 

 

이 블록을 다음과 같이 아래쪽은 막혀 있고, 위쪽만 열려있는 통에 넣는다고 생각해보자. 

위쪽만 열려있기 때문에 위쪽으로 블록을 넣고, 위쪽으로 블록을 빼야 한다. 쉽게 이야기해서 넣는 곳과 빼는 곳이 같다.

 

 

이번에는 넣은 블록을 빼자.

 

 

후입 선출(LIFO, Last In First Out)
여기서 가장 마지막에 넣은 3번이 가장 먼저 나온다. 

이렇게 나중에 넣은 것이 가장 먼저 나오는 것을 후입 선출이라 하고, 이런 자료 구조를 스택이라 한다.
전통적으로 스택에 값을 넣는 것을 push 라 하고, 스택에서 값을 꺼내는 것을 pop 이라 한다.

 

 

자바가 제공하는 스택 자료 구조를 사용해보자.

public class StackMain {

    public static void main(String[] args) {

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

        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack);

        // 다음 꺼낼 요소 확인(꺼내지 않고 단순 조회만)
        System.out.println("stack.peek() = " + 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);
    }
}
[1, 2, 3]
stack.peek() = 3
stack.pop() = 3
stack.pop() = 2
stack.pop() = 1
[]

 

 

주의! - Stack 클래스는 사용하지 말자
자바의 Stack 클래스는 내부에서 Vector 라는 자료 구조를 사용한다. 이 자료 구조는 자바 1.0에 개발되었는데, 

지금은 사용되지 않고 하위 호환을 위해 존재한다. 지금은 더 빠른 좋은 자료 구조가 많다. 

따라서 Vector 를 사용하는 Stack 도 사용하지 않는 것을 권장한다. 대신에 이후에 설명할 Deque 를 사용하는 것이 좋다.

 

 

 

큐 자료 구조

선입 선출(FIFO, First In First Out)
후입 선출과 반대로 가장 먼저 넣은 것이 가장 먼저 나오는 것을 선입 선출이라 한다. 

이런 자료 구조를 큐(Queue)라 한다.

 

 

전통적으로 큐에 값을 넣는 것을 offer 라 하고, 큐에서 값을 꺼내는 것을 poll 이라 한다.

 

 

컬렉션 프레임워크 - Queue

 

  • Queue 인터페이스는 List , Set 과 같이 Collection 의 자식이다.
  • Queue 의 대표적인 구현체는 ArrayDeque , LinkedList 가 있다.

참고로 LinkedList 는 Deque 와 List 인터페이스를 모두 구현한다.

public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

 

 

ArrayDeque 를 통해 Queue 를 사용해보자.

public class QueueMain {

    public static void main(String[] args) {

        Queue<Integer> queue = new ArrayDeque<>();
        //Queue<Integer> queue = new LinkedList<>();
        // 데이터 추가
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue);

        // 다음 꺼낼 데이터 확인(꺼내지 않고 단순 조회만)
        System.out.println("queue.peek() = " + 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);
    }
}
[1, 2, 3]
queue.peek() = 1
queue.poll() = 1
queue.poll() = 2
queue.poll() = 3
[]

 

 

 

 

Deque 자료 구조

"Deque"는 "Double Ended Queue"의 약자로, 이 이름에서 알 수 있듯이, Deque는 양쪽 끝에서 요소를 추가하거나
제거할 수 있다. Deque는 일반적인 큐(Queue)와 스택(Stack)의 기능을 모두 포함하고 있어, 매우 유연한 자료 구조
이다. 데크, 덱 등으로 부른다.

 

 

 

  • offerFirst( ) : 앞에 추가한다.
  • offerLast( ) : 뒤에 추가한다.
  • pollFirst( ) : 앞에서 꺼낸다.
  • pollLast( ) : 뒤에서 꺼낸다.

Deque 의 대표적인 구현체는 ArrayDeque , LinkedList 가 있다.

 

 

public class DequeMain {

    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        //Deque<Integer> deque = new LinkedList<>();
        
        // 데이터 추가
        deque.offerFirst(1);
        System.out.println(deque);
        deque.offerFirst(2);
        System.out.println(deque);
        deque.offerLast(3);
        System.out.println(deque);
        deque.offerLast(4);
        System.out.println(deque);

        // 다음 꺼낼 데이터 확인(꺼내지 않고 단순 조회만)
        System.out.println("deque.peekFirst() = " + deque.peekFirst());
        System.out.println("deque.peekLast() = " + deque.peekLast());

        // 데이터 꺼내기
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollLast() = " + deque.pollLast());
        System.out.println("deque.pollLast() = " + deque.pollLast());
        System.out.println(deque);
    }
}
[1]
[2, 1]
[2, 1, 3]
[2, 1, 3, 4]
deque.peekFirst() = 2
deque.peekLast() = 4
deque.pollFirst() = 2
deque.pollFirst() = 1
deque.pollLast() = 4
deque.pollLast() = 3
[]

 

 

 

 

Deque 구현체와 성능 테스트


Deque 의 대표적인 구현체는 ArrayDeque , LinkedList 가 있다. 이 둘 중에 ArrayDeque 가 모든 면에서 더 빠르다.

 

  • 100만 건 입력(앞, 뒤 평균)
    • ArrayDeque : 110ms
    • LinkedList : 480ms
  • 100만 건 조회(앞, 뒤 평균)
    • ArrayDeque : 9ms
    • LinkedList : 20ms


둘의 차이는 ArrayList vs LinkedList 의 차이와 비슷한데, 작동 원리가 하나는 배열을 하나는 동적 노드 링크를 사용하기

때문이다. ArrayDeque 는 추가로 특별한 원형 큐 자료 구조를 사용하는데, 덕분에 앞, 뒤 입력 모두 O(1)의 성능을 제공한다. 물론 LinkedList 도 앞 뒤 입력 모두 O(1)의 성능을 제공한다. 이론적으로 LinkedList 가 삽입 삭제가 자주 발생할 때 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근패턴, CPU 캐시 최적화 등을 고려할 때 배열을 사용하는 ArrayDeque 가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

 

 

 

Deque와 Stack, Queue


Deque 는 양쪽으로 데이터를 입력하고 출력할 수 있으므로, 스택과 큐의 역할을 모두 수행할 수 있다.
Deque 를 Stack 과 Queue 로 사용하기 위한 메서드 이름까지 제공한다.

 

Deque

 

 

 

Deque - Stack

 

  • push() 를 호출하면 앞에서 입력한다.
  • pop() 을 호출하면 앞에서 꺼낸다.

 

 

Deque - Queue

 

  • offer() 를 호출하면 뒤에서 입력한다.
  • poll() 을 호출하면 앞에서 꺼낸다.

 

Deque - Stack

public class DequeStackMain {

    public static void main(String[] args) {

        Deque<Integer> deque = new ArrayDeque<>();
        // Deque<Integer> deque = new LinkedList<>();

        // 데이터 추가
        deque.push(1);
        deque.push(2);
        deque.push(3);
        System.out.println(deque);

        // 다음 꺼낼 데이터 확인(꺼내지 않고 확인만)
        System.out.println("deque.peek() = " + deque.peek());

        // 데이터 꺼내기
        System.out.println("deque.pop() = " + deque.pop());
        System.out.println("deque.pop() = " + deque.pop());
        System.out.println("deque.pop() = " + deque.pop());
        System.out.println(deque);
    }
}
[3, 2, 1]
deque.peek() = 3
deque.pop() = 3
deque.pop() = 2
deque.pop() = 1
[]

 

Deque 에서 Stack 을 위한 메서드 이름까지 제공하는 것을 확인할 수 있다. 

자바의 Stack 클래스는 성능이 좋지 않고 하위 호환을 위해서 남겨져 있다. 

Stack 자료 구조가 필요하면 Deque 에 ArrayDeque 구현체를 사용하자.

 

Deque - Queue

public class DequeQueueMain {

    public static void main(String[] args) {

        Deque<Integer> deque = new ArrayDeque<>();
        // Deque<Integer> deque = new LinkedList<>();

        // 데이터 추가
        deque.offer(1);
        deque.offer(2);
        deque.offer(3);
        System.out.println(deque);

        // 다음 꺼낼 데이터 확인(꺼내지 않고 확인만)
        System.out.println("deque.peek() = " + deque.peek());

        // 데이터 꺼내기
        System.out.println("deque.poll() = " + deque.poll());
        System.out.println("deque.poll() = " + deque.poll());
        System.out.println("deque.poll() = " + deque.poll());
        System.out.println(deque);
    }
[1, 2, 3]
deque.peek() = 1
deque.poll() = 1
deque.poll() = 2
deque.poll() = 3
[]

 

Deque 에서 Queue 을 위한 메서드 이름까지 제공하는 것을 확인할 수 있다. 

Deque 인터페이스는 Queue 인터페이스의 자식이기 때문에, 단순히 Queue 의 기능만 필요하면 

Queue 인터페이스를 사용하고, 더 많은 기능이 필요하다면 Deque 인터페이스를 사용하면 된다.

그리고 구현체로 성능이 빠른 ArrayDeque 를 사용하자.

 

 

'복습' 카테고리의 다른 글

[Java 복습] 정렬 Comparable, Comparator  (0) 2024.05.20
[Java 복습] 직접 구현해보는 Iterator  (0) 2024.05.20
[Java 복습] Map 개념 뿌시기  (0) 2024.05.19
[Java 복습] Set 개념 뿌시기  (0) 2024.05.19
[Java 복습] 직접 구현해보는 Set (feat. hashCode)  (0) 2024.05.17

'복습' Related Articles

티스토리툴바