[CS 스터디 : JAVA] (2) Stack & Queue & Heap

1️⃣  Stack

: 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 구조

: 후입선출 > 가장 마지막에 들어온 원소가 가장 첫 번째로 나옴

: 스택의 가장 마지막으로 들어온 원소(맨 윗 원소)를 top이라고 함 

: java.util.AbstractCollection 상속받음

 

스택의 구조

 

→ 선언 방식

-- java.util.Stack 패키지 임포트

 

 

→ Stack의 특징

  (1) LIFO 구조

  (2) 재귀 함수를 호출할 때 사용 > 잘못된 재귀 호출 시(깊은 재귀에 빠져버릴 때) 나는 에러가 StackOverflowError(스택 꽉 차 있음)

  (3) 통용되는 메서드명이 존재함 > top, push, pop 등

  (3) java.util.Stack 패키지에서 다양한 메서드를 제공(java.util.AbstractCollection을 상속하므로 isEmpty, size 등 사용 가능)

 

메서드 기능	메서드 명	반환 타입
stack이 비어있는지 확인	empty()	boolean
top 원소 접근	peek()	E
top 원소 삭제	pop()	E
현재 top 위 위치에 원소 삽입	push(E item)	E
원소 위치 반환	search(Object o)	int

 

✅ add(AbstractCollection) vs. push(Stack) 

 -- add는 boolean 형태 반환, push는 삽입한 원소 반환 

 

(4) 사용 : 그래프의 DFS, 재귀 알고리즘, 역순 문자열 만들기

---

 

 

 

 

 

2️⃣ Queue

: 놀이공원 앞에 줄을 지어 있는 사람들이 놀이기구 타는 것과 같은 구조

: 선입선출 > 가장 첫 번째로 들어온 원소가 가장 첫 번째로 나옴

: 데이터가 들어오는 것을 enqueue, 나가는 것을 dequeue 라고 함

: 상속받는 패키지가 없음

 

Queue의 구조

 

→ 선언 방식

-- 자바에서 Queue는 LinkedList를 활용하여 생성해야 하므로 java.util.LinkedList, java.util.Queue를 모두 import해야만 사용 가능

-- Queue<Element> queue = new LinkedList<>(); 형태

 

 

→ Queue의 특징

  (1) FIFO 구조

  (2) 큐의 한 쪽 끝은 삭제 연산만 수행(dequeue 부분)

  (3) 다른 한 쪽 끝은 삽입 연산만 수행(enqueue 부분)

  (3) java.util.Queue 패키지에서 다양한 메서드를 제공

메서드 기능	메서드 명	반환 타입
원소 삽입	add(E a)	boolean
첫 번째 원소 접근	element()	E (queue가 null일 시, error)
	peek()	E (queue가 null일 시, null 반환)
첫 번째 원소 삭제	poll()	E (queue가 null일 시, null 반환)
	remove()	E (queue가 null일 시, error)

 (4) 사용 : BFS 

---

 

 

 

 

 

3️⃣  Heap

: 완전 이진 트리의 일종

: 우선순위 큐를 구현하는데에 많이 이용됨

: 데이터의 최댓값과 최솟값을 빠르게 찾기 위해 고안됨

: 최대힙과 최소 힙으로 나뉨

 

 

최대힙 : 부모 노드 값이 자식 노드의 값보다 크거나 같고, 완전 이진 트리 형태이다.
최소힙 : 부모 노드 값이 자식 노드의 값보다 작거나 같고, 완전 이진 트리 형태이다.

 

힙의 형태

 

→ 선언 방식

-- java.util.PriorityQueue 패키지 import 사용

-- java.util.AbstractCollection 패키지 상속 

-- default는 최소힙이며 최대힙을 구현하고 싶을 때는 Comparator 내부클래스를 사용함

 

 

 

→ Heap의 특징

  (1) 최댓값과 최솟값을 빠르게 찾아낼 수 있음

  (2) 힙은 데이터가 최솟값 또는 최댓값으로 계속해서 정렬이 되어야 할 때, 데이터의 삽입과 삭제가 자주 일어날 때 사용

  (3) 힙의 삽입 : 힙에 새로운 요소가 들어오면 힙의 마지막 노드에 삽입한 다음 부모 노드와 값을 비교하며 자기의 자리로 찾아감

 

힙의 삽입

 

  (4) 힙의 삭제 : 최대힙에서의 삭제 연산은 최댓값을 삭제하는 것으로 루트노드 자리에는 힙의 마지막 노드를 가져오고 재구성한다

 

힙의 삭제

 

(5) 자바에서 java.util.PriorityQueue에서 다양한 메서드를 지원한다

 

패키지 메서드

 

(6) AbstractCollection을 상속받으므로 isEmpty() 등도 사용 가능