알고리즘

1주차 : 스택, 큐, 우선순위큐, 힙 java 정리

김긍수 2021. 2. 26. 15:35

이번주에는 스택, 큐, 우선순위큐, 힙, 연결리스트, 트리, 해쉬테이블에 대해 복습하였습니다.

이번 주 최종 정리로 스택, 큐, 우선순위큐, 힙의 클래스를 활용하는 방법을 정리해보았습니다.

 

1) 스택 Stack Class

스택은 후입선출(Last In first Out)의 구조를 가지고 있다.

stack class는 pop, push, empty, search, peek 함수를 제공합니다.

 

*배열과 달리 스택은 O(1)로 i번째 항목에 접근할 수 없습니다.

*하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 O(1)입니다.

 

어떻게 스택을 생성하나요?

stack을 생성하기 위해서 먼저 우리는 java.util.stack 패키지를 import 해야합니다.

Stack<E> stack = new Stack<E>();
push(Object element) 요소를 추가할 수 있어요.
peek() 스택의 최상단 요소를 리턴해줍니다. 
pop() 스택의 최상단 요소를 삭제하고 해당 요소를 반환합니다.
empty() 스택이 비어있다면, true를 반환하고 그렇지 않다면 false를 반환합니다.
search(Object element) 스택안에 해당 요소가 존재하는지 확인합니다.
만약 요소를 찾는다면 스택의 위치를 반환해주고
찾지 못하면 -1을 리턴합니다.

 

사용사례

  • 재귀 알고리즘
재귀적으로 함수를 호출해야하는 경우 임시데이터를 스택에 넣어줍니다.
재귀함수를 빠져나와 BackTrack을 할때, 스택에 넣어둔 임시데이터를 빼줘야합니다
스택은 이러한 일련의 행위를 직관적으로 가능하게 해줍니다
또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해 구현할 수 있게 해줍니다.
  • 웹브라우저 방문기록 (뒤로가기)
  • 실행취소
  • 역순 문자열 만들기
  • 수식의 괄호 검사
  • 후위 표기법 계산

2) 큐 Queue Interface

컴퓨터의 기본적인 자료구조로 먼저 삽입한 요소가 먼저 나오는 FIFO구조로 저장합니다.

대기열이라고 생각하면 됩니다.

add(Object element) 큐의 tail에 요소를 추가하기 위해 사용합니다.
우선순위큐의 경우 우선순위에 따라 추가됩니다.
remove() 큐 head에 있는 요소를 제거합니다. 큐가 비어있을 때 NoSuchElementException을 발생합니다.
poll() 큐 head에 있는 요소를 제거하고 해당 요소를 반환합니다. 큐가 비어있다면 null을 리턴합니다.
peek() 큐의 head에 있는 요소를 반환합니다. 큐가 비어있다면 null을 리턴합니다.
element() 이 메소드는 peek()과 유사하지만, 큐가 비어있을 때 NoSuch ElementException을 발생합니다.
size() 큐의 사이즈를 반환합니다.

 

2-1) LinkedList 큐

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

 

2-2) PriorityQueue 우선순위 큐

큐는 선입선출을 기초로 하지만 때때로 우리는 요소의 우선순위에 따라 처리하는 것이 필요합니다.

우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데, 힙으로 구현하는 것이 가장 효과적입니다.

Queue<E> pq = new PriorityQueue<>();

 

큐의 사용사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에서 사용합니다.

  • 너비 우선 탐백(BFS) 구현
- 처리해야할 노드의 리스트를 저장하는 용도로 큐를 사용합니다.
- 노드를 하나 처리할 때 마다 해당 노드와 인접한 노드들을 큐에 다시 저장합니다.
- 노드를 접근한 순서대로 처리할 수 있습니다.
  • 캐시구현
  • 우선순위가 같은 작업 예약(인쇄 대기열)
  • 선입선출이 필요한 대기열 (티켓 카운터)
  • 콜센터 고객 대기 시간
  • 프린터의 출력 처리
  • 프로세스 관리

3) Heap 힙

우선순위큐를 힙으로 구현합니다.

완전 이진 트리로 우선순위 큐를 위해 만들어진 자료구조입니다.

여러개의 값 중에서 최대값/최소값을 바로 찾아내도록 만들어진 자료구조입니다.

힙 트리에서는 중복된 값을 허용하고 부모노드는 자식노드보다 크거나 같아야합니다. (최대힙의 경우)

 

힙 삽입 시

1. 인덱스 순 가장 마지막 위치에 새로운 요소를 삽입합니다.

2. 부모노드와 key를 비교하여 부모노드 < 새로운 노드 라면 서로 교환합니다.

3. 교환 후 다시 부모노드와 비교하여 더이상 교환되지 않을 때까지 반복합니다.

 

힙 삭제 시

1. 힙은 최대값/최소값을 빠르게 찾아내도록 만들어진 자료구조입니다. 힙 삭제 시 최상단 root 노드가 삭제됩니다.

2. 삭제된 루트노드에 힙의 마지막 노드를 가져옵니다.

3. 삽입 노드와 자식노드를 비교하여 삽입노드 < 자식노드 인 경우 교환합니다. (두개의 자식노드가 있다면 둘 중 더 큰 노드와 교환합니다)