스택 / 큐 / 덱
: 모두 배열에서 발전된 형태의 구조
스택(Stack) - 클래스
- 스택(Stack)은 삽입과 삭제 연산이 후입 선출(LIFO : Last-in First-out) 자료 구조
- 깊이 우선 탐색 (DFS : Depth First Search), 백트래킹 종류의 코딩테스트에 효과적
- 후입 선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통
- 스택(stack)은 Vector 클래스를 상속받아 구현된 클래스이다.
- Java의 초기 버전부터 존재했고, 스택으로서의 기능을 제공하기 위해 만들어짐
- 때문에 스택(Stack)은 Vector의 모든 기능과 함께 스택의 특징도 제공하고 있음
- 그러나, *JAVA 컬렉션 프레임워크는 보편적으로 인터페이스를 더 선호한다.
스택(Stack)클래스는 Vector를 상속받아 구현한 것이기 때문에, Java에서 스택 구현 시 일반적인 인터페이스인 java.util.Deque(덱) 인터페이스 사용이 권장된다.
스택(Stack) 용어
- 위치를 나타낼 때
- top : 삽입과 삭제가 일어나는 위치
- 연산
- push() : top 위치에 새로운 데이터를 삽입하는 연산
- pop() : top 위치에 현재있는 데이터를 삭제하고 확인하는 연산
- peek() : top 위치에 현재 있는 데이터를 단순 확인하는 연산(보기만 하는 것)
<스택 연산 과정>
큐(Queue) - 인터페이스
- 큐(Queue)는 삽입과 삭제 연산이 선입 선출(FIFO : First-in First-out)로 이루어지는 자료구조
- 스택과 달리 먼저 들어온 데이터가 먼저 나간다.
- 따라서 삽입과 삭제가 양방향에서 이루어진다.
- 너비 우선 탐색(BFS : Breadth First Search)에서 자주 사용된다.
- 컴퓨터 버퍼에서 주로 사용된다
큐(Queue) 용어
- rear : 큐(Queue)에서 가장 끝 데이터를 가리키는 영역
- front : 큐(Queue)에서 가장 앞의 데이터를 가리키는 영역 (가장 먼저 들어온 것)
- add() : rear 부분에 새로운 데이터를 삽입하는 연산
- poll() : front 부분에 있는 데이터를 삭제하고 확인하는 연산
- peek() : 큐(Queue)의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산 (단순 확인)
=> 큐(Queue)는 가장 끝에 있는(rear)부분의 요소를 확인할 수 있는 peek()과 같은 메서드를 제공하지 않는다.
(그래서 백준 문제 풀 때 rear 부분의 값을 출력하라는 경우에는 ArrayDeque을 다운캐스팅 하여 peekLast()를 이용해 문제를 풀었다.)
<큐 연산 과정>
🪄잠깐!
- 우선순위 큐(Priority Queue)
- 우선순위 큐도 있다.
우선순위 큐(Priority Queue)는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다.- 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
=> 즉, 트리구조를 예를들어 제일 상단의 노드가 max가 오도록 설정한 것 뿐이지 하단의 노드들이 정렬이 되는 것은 아님- 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현하는데, 힙은 트리 종류 중 하나이므로 추후에 다룰 예정!(링크 첨부하도록 하겠음)
| 큐 인터페이스를 구현하는 주요 클래스(구현체)
- LinkedList
- 이중연결 리스트로 구현된 클래스로, 큐의 동작을 지원하면서도 리스트의 다른 기능들도 제공
- ArrayDeque
- 가변 크기 배열을 사용하여 큐를 구현한 클래스, 배열을 기반으로 동작하기 때문에 큐의 끝에 요소를 추가하거나 삭제 하는데 있어 상대적으로 빠른 속도를 보여줌.
(스택으로도 사용 가능)- PriorityQueue
- 우선순위 큐를 구현한 클래스
'Queue' 인터페이스를 구현하면서 요소를 우선순위순으로 관리
따라서, 가장 높은 우선순위의 요소가 먼저 나오게 된다.
덱(Deque)
- Deque은 "Double Ended Queue"의 약자
- 큐(Queue)와 스택(Stack)의 특성을 모두 가진 자료 구조이다.
- 큐의 front(앞)와 rear(뒤) 양쪽에서 요소의 추가와 제거가 가능하도록 한다.
- 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱은 셸프(shelf)라고 한다.
<덱 자료구조>
| 덱 인터페이스를 구현하는 주요 클래스(구현체)
- LinkedList
- 이중연결 리스트로 구현된 클래스
- 요소의 삽입, 삭제에 뛰어난 유연성 제공
- 중간 삽입 및 삭제에 강점을 가짐
- 그러나, ArrayDeque보다는 성능면에서 약간 떨어질 수 있음
- ArrayDeque
- 가변 크기 배열을 사용하여 큐를 구현한 클래스
- 큐의 처음과 끝 모두에서 빠른 삽입과 삭제를 지원
(빠른 성능)
- 데이터 삽입
- addFirst(e), offerFirst(e): Deque의 맨 앞에 요소를 추가
- addLast(e), offerLast(e), add(e), offer(e) : Deque의 맨 뒤에 요소를 추가
- 데이터 추출
- getFirst(), peekFirst(), peek() : Deque의 맨 앞에 있는 요소를 반환합니다.
- getLast(), peekLast(): Deque의 맨 뒤에 있는 요소를 반환합니다.
- 데이터 제거
- removeFirst(), pollFirst(), poll(), remove() : Deque의 맨 앞에서 요소를 제거하고 반환합니다.
- removeLast(), pollLast(): Deque의 맨 뒤에서 요소를 제거하고 반환합니다.
| 내가 푼 문제
백준 : 10828(스택) / 10845(큐) / 10866(덱) -> 링크 첨부 예정
출처 :
Do it 알고리즘 코딩테스트 자바편
자료구조 덱-Benjamin.log
Chat gpt
