스택, 큐, 덱, 우선순위 큐

Restricted Structure

• 정의) 스택, 큐, 덱을 묶어서 Restricted Structure라고 부름. 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있기 때문임.

스택

• 정의) 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조

• 특징)
• 삽입과 삭제가 한 쪽에서만 일어남
• 깊이 우선 탐색, 백트래킹에 효과적으로 쓰임
• 후입선출의 개념 자체가 재귀 함수 알고리즘과 일맥상통함

• 용어)
• 위치
• top : 삽입과 삭제가 일어나는 위치
• 연산
• push : top 위치에 새로운 데이터 삽입
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인
• peek : top 위치에 현재 있는 데이터를 단순 확인

• 시간복잡도)
• 제일 앞에 원소 추가 : O(1)
• 제일 앞의 원소 제거 : O(1)
• 최상단 원소 확인 : O(1)
• 최상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능 (배열을 이용해 스택을 구현한다면 가능하게 만들 수는 있음)

큐

• 정의) 삽입과 삭제과 선입선출로 이뤄지는 자료구조

• 특징)
• 너비 우선 탐색에서 자주 사용함
• 삽입과 삭제가 양방향에서 일어남

• 용어)
• 위치
• rear : 큐에서 가장 끝 데이터 가리키는 영역
• front : 큐에서 가장 앞의 데이터를 가리키는 영역
• 연산
• add : rear 부분에 새로운 데이터를 삽입
• poll : front 부분에 있는 데이터를 삭제하고 확인
• peek : front 부분에 있는 데이터를 단순 확인

• 시간복잡도)
• 제일 뒤에 원소 추가 : O(1)
• 제일 앞에 원소 제거 : O(1)
• 제일 앞/뒤의 원소 확인 : O(1)
• 제일 앞/뒤가 아닌 원소들의 확인/변경은 원칙적으로 불가능 (배열을 이용해 큐를 구현한다면 가능하게 만들 수는 있음)

우선순위 큐

• 정의) 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

• 특징)
• 연산 이름은 큐와 동일하지만, 내부 구조는 큐와 완전히 다름
• 큐 설정에 따라 front에 항상 우선순위가 가장 높은 값이 위치함
• 예를 들어 front에 항상 최소값이 위치하게 했다는 건,
작은 수가 더 높은 우선순위를 가지고
높은 우선순위를 가진 원소가 먼저 나오기에
작은 수가 먼저 나온단 의미임
• 일반적으로 힙(완전 이진 트리 → 뒤 챕터에서 다룰 예정)을 이용해 구현함
• 힙 구조 상 max 값이 최상단에 있는 건 확실하지만 데이터를 항상 정렬하고 있진 않음
따라서, 큐 내부를 출력해보면 데이터가 정렬되어 있진 않음
허나, poll을 몇 번을 하든 front에 max 값이 존재한다는 건 확실하게 보장됨

• 시간 복잡도)
• 제일 뒤에 원소 추가 : O(logN)
• 제일 앞에 원소 제거 : O(logN)
• 제일 앞의 원소 확인 : O(logN)

• 조건 변경하는 법 1) ex. 최대값이 우선순위 높게 (내림차순 정렬로 변경. 기본은 오름차순 정렬)

• 조건 변경하는 법 2) ex. 절대값 작은 게 우선순위 높게 + 절대값 같을 땐 음수가 우선순위 높게
1. compare 함수를 오버라이딩
2. 람다 사용
• 조건 변경 결과 ex
• 일반적인 pq.poll 시 나오는 순서 = [-2, -1, -1, -1, 1, 1, 1, 2]
• 구현한 pq.poll 시 나오는 순서 = [-1, -1, -1, 1, 1, 1, -2, 2]

덱(deque, 데큐) in Java

• 정의) Double-ended Queue 의 줄임말로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조

• 특징)
• 자바에서 덱은 인터페이스로 구현되어 있음. 덱의 여러 연산을 정의한 Deque 인터페이스가 있고, 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있음

• 시간복잡도)
• 제일 앞/뒤에 원소 추가 : O(1)
• 제일 앞/뒤의 원소 제거 : O(1)
• 제일 앞/뒤의 원소 확인 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능 (C++ STL deque에선 인덱스로 원소에 접근 가능)

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main