[자료구조 & 알고리즘] 3. 자바의 Queue, Stack, Deque

자바의 Queue, Stack, Deque

1. Queue

• 시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출(FIFO, First In First Out) 형식으로 데이터를 저장하는 자료구조

• 대기열이라고도 함.

• 큐의 뒤(Rear)에 데이터를 추가하는 것을 enqueue, 큐의 앞(Front)에서 데이터를 꺼내는 것을 dequeue라고 함.

• 자바의 컬렉션에 Queue는 인터페이스만 존재하고 구현체는 LinkedList를 사용함.

     - enqueue 메소드

          - add(value) : value를 맨 뒤에 넣음. 성공하면 true, 실패하면 예외 발생.

          - offer(value) : value를 맨 뒤에 넣음. 성공하면 true, 실패하면 false 반환.

     - dequeue 메소드

          - remove() : 맨 앞의 값을 반환 후 제거. 큐가 비어있다면 예외 발생.

          - poll() : 맨 앞의 값을 반환 후 제거. 큐가 비어있다면 null 반환.

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

 

2. Stack

• 시간 순서상 가장 최근에 저장한 데이터가 먼저 출력되는 후입선출(LIFO, Last In First Out) 형식으로 데이터를 저장하는 자료구조

• 스택의 위(Top)에 데이터를 추가하는 것을 push, 데이터를 꺼내는 것을 pop이라고 함.

• 자바의 컬렉션에 Stack 구현체 존재.

     - push(value) : value를 맨 위에 넣음.

     - pop() : 맨 위의 값을 반환 후 제거.

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

 

3. Deque

• Double-Ended-Queue

• 양쪽 끝에서 데이터를 처리할 수 있는 큐를 뜻함.

• 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택으로도 사용할 수도 있고, 큐로도 사용할 수 있음.

• 자바에서는 공식적으로 Stack 클래스 대신 ArrayDeque를 사용하도록 권장하고 있음.

     - Stack 클래스는 자바 1.0부터 존재하던 오래된 클래스.

     - 불필요한 동기화 처리 및 스레드 안전에 의한 성능 감소.

• 큐 역시도 일반적인 큐 형태로 사용한다면 LinkedList로 구현하는 것 보다, 내부적으로 배열을 사용하는 ArrayDeque가 성능이 더 좋음.

• 자바의 컬렉션에 Deque 인터페이스와 ArrayDeque 클래스가 존재.

     - add, offer, remove, poll 등을 first에서 수행할지, last에서 수행할지 자유롭게 정할 수 있음.

     - 큐로 사용할 시 offer, poll 사용

     - 스택으로 사용할 시 push, pop 사용

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