[Java] Stack, Queue, Deque

Collection 하위의 Vector 하위에 Stack

스택은 후입선출,LIFO(Last In First Out) 규칙을 지키는 자료구조이다.

스택의 대표적인 메서드

1. push() : 인자로 넘어간 값을 스택의 맨 뒤에 삽입한다.
2. pop() : 맨 뒤의 요소를 뽑아서 리턴
3. peek() : 맨 뒤의 요소를 리턴 단, 삭제하지않고 요소만 복사해서 리턴함.
4. empty() : 스택이 비어있는지 확인, 더 상위 개념의 isEmpty()사용을 추천.

컬렉션에서 상속받기 때문에 컬렉션에서 지원하는 메서드들도 사용가능 하다

가장 대표적으로 완전 탐색의 DFS알고리즘을 구현하는데 사용한다.

깊이 우선으로 탐색하고 노드의 끝을 발견했을때 가장 마지막의 넣은 노드부터 탐색을 마치며 진행하기 때문이다.

Collection 하위의 Queue 그리고 Deque

Queue

큐는 선입선출,FIFO(First In First Out)규칙을 지키는 자료구조이다.

큐의 대표적인 메서드

1. offer() : 인자로 넘어간 값을 큐의 맨 뒤로 삽입한다.

2. poll() : 맨 앞의 값을 뽑아서 리턴한다.

3. peek() : 맨 앞의 값을 복사해 리턴하되 삭제하지는 않는다.

4. element() : 맨 앞의 값을 복사해 리턴하되 삭제하지않고

   위의 두 메서드와는 다르게 큐가 비어있을때

   NoSuchElementException(그런 요소는 없어요 경고)을 리턴한다.

5. isEmpty() : 큐가 비어있는 지 확인한다.

Deque

큐에서 좀 더 개선 된 자료구조로 데크가 있다.

스택과 큐는 한 방향에서만 입려과 출력이 가능하지만 (스택 → 삽입, 삭제 모두 한 방향에서만 가능, 큐 → 삽입 앞, 삭제 뒤 각각 한 방향) 데크는 양방향에서 모두 삽입, 삭제가 가능하다.

데크의 대표적인 메서드

1. offerFirst(), offer() : 두 메서드로 양끝에서 삽입할 수 있다.
2. pollFirst(), poll() : 두 메서드로 양 끝에서 값을 리턴받고 삭제할 수 있다.
3. peekFirst(), peek() : 두 메서드로 양 끝에서 값을 복사해서 리턴 받을 수 있다.
4. isEmpty() : 큐가 비어있는 지 확인한다.

마찬 가지로 큐와 데크도 컬렉션에서 상속받기 때문에 컬렉션에서 지원하는 메서드들도 사용가능하다.

자바에서 큐와 데크는 구현체없이 인터페이스만 존재한다. LinkedList를 이용해 인스턴스를 생성하고 다형성을 이용해 큐와 데크로 객체 타입을 바꿔서 선언해 사용해야한다.

Queue<Integer> que = new LinkedList<>();
Deque<Integer> dq = new LinkedList<>();

가장 대표적으로 완전탐색의 BFS알고리즘을 구현하는데 사용한다.

너비 우선으로 탐색하고 그래프나 트리의 다음 레벨로 이동할 때 먼저 탐색한 순서대로 poll하면서 해당 노드와 연결된 다음 노드들을 탐색한다.

다음 이야기..
완전탐색, DFS, BFS가 궁금하다면?