🐧 Java 코딩테스트에 자주 나오는 자료구조

😁 Stack

Stack<Integer> stack = new Stack<>();

stack.push(1) // 값 추가
stack.pop() // 값 삭제
stack.clear() // 값 전체삭제
stack.size() // 크기 반환
stack.isEmpty() // 비어있으면 true, 아니면 false
stack.contains(1) // 1을 포함하고 있으면 true, 아니면 false
stack.peek() // Stack top 출력 (제거 X), 비어있으면 null 반환

😁 Queue

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

queue.add(1) // 값 추가
queue.offer(2) // 값 추가
queue.poll() // 첫 번째 값 반환, 비어있으면 null 반환
queue.remove() // 첫 번째 값 제거
queue.clear() // 값 모두 삭제
queue.peek() // 첫 번째 값 출력 (제거 X)
queue.size() // 큐에 포함된 요소의 개수를 반환
queue.isEmpty() // 큐가 비어있는지 여부를 반환

Queue(큐)는 자료를 저장하는 자료구조 중 하나로, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First-In-First-Out) 구조를 가지고 있습니다. 자바에서는 java.util.Queue 인터페이스를 통해 큐를 구현할 수 있습니다.

• add(E e) 또는 offer(E e): 큐에 요소를 추가합니다.
• remove() 또는 poll(): 큐에서 가장 앞에 있는 요소를 제거하고 반환합니다.
• element() 또는 peek(): 큐에서 가장 앞에 있는 요소를 반환합니다. 제거는 하지 않습니다.

보통 코테에서는 Deque를 사용해서 푸는 것이 대부분.

Deque - 코테용

코테에서는 Deque(Double Ended Queue)를 사용한다.
큐 뿐만 아니라 스택의 기능도 모두 수행할 수 있기 때문. Deque은 큐의 처음과 깥 양쪽에서 삽입 삭제가 모두 가능하다.

add vs offer

• add : 요소를 컬렉션에 추가, 큐의 경우 큐가 가득 차 있을 때 이 메서드를 사용하면 예외가 발생할 수 있다.
• offer : 요소를 큐에 추가, 큐가 가득 차 있을 때는 예외를 발생시키지 않고, false를 반환

remove vs poll

• remove : 큐에서 요소를 제거 후 반환, 큐가 비어있는 경우 예외 발생
• poll : 큐에서 요소 제거 후 반환, 큐가 비어있는 경우 null반환

일반적으로 offer, poll을 사용하는 것이 안정적 !!!

Deque - 내장 메서드

//Deque를 ArrayDeque로 초기화
Deque<Integer> deque = new ArrayDeque();

deque.offerFirst(1);  // 앞에 요소 추가
deque.offerLast(2);  // 뒤에 요소 추가

int removedFirst = deque.pollFirst(); // 앞에 데이터 삭제
int removedLast = deque.pollLast(); // 뒤에 데이터 삭제 

요소 추가 메서드

• offerFirst(E e): 덱의 맨 앞에 요소를 추가하고, 성공 여부를 반환합니다.
• offerLast(E e): 덱의 맨 뒤에 요소를 추가하고, 성공 여부를 반환합니다.
  요소 제거 메서드
• pollFirst(): 덱의 맨 앞에 있는 요소를 제거하고 반환하며, 비어있을 때는 null 반환.
• pollLast(): 덱의 맨 뒤에 있는 요소를 제거하고 반환하며, 비어있을 때는 null 반환.
  요소 조회 메서드
• peekFirst(): 덱의 맨 앞에 있는 요소를 반환하며, 비어있을 때는 null 반환.
• peekLast(): 덱의 맨 뒤에 있는 요소를 반환하며, 비어있을 때는 null 반환.
  기타 메서드:
• size(): 덱에 포함된 요소의 개수를 반환합니다.
• isEmpty(): 덱이 비어있는지 여부를 반환합니다.
• clear(): 덱의 모든 요소를 제거합니다.

PriorityQueue

PriorityQueue<Integer> pq = new PriorityQueue<>();
// 기본은 낮은 숫자가 우선순위를 갖는다.
// 높은 숫자가 우선되게 하려면 () 안에 Collections.reverseOrder() 작성

pq.add(1) // 값 추가
pq.offer(1) // 값 추가
pq.poll() // 첫 번째 값 반환, 비어있으면 null 반환
pq.remove() // 첫 번째 값 제거
pq.clear() // 값 모두 삭제
pq.peek() // 첫 번째 값 출력 (제거 X)

😁 HashSet

• HashSet : 중복을 허용하지 않는 구조, 순서가 없고 정렬도 안함
• LinkedHashSet : 중복을 허용하지 않는 구조, 삽입된 순서대로 순서를 관리
• TreeSet : 중복을 허용하지 않는 구조, 이진탐색트리 형태로 데이터를 저장하므로 정렬한다.

HashSet<Integer> set = new HashSet<>();

set.add(1) // 값 추가
set.remove(1) // 값이 1인 데이터 삭제
set.removeAll(set2) // set의 데이터 중 set2에 들어있는 데이터를 모두 삭제
set.retainAll(set2) // set의 데이터 중 set2에 들어있지 않은 데이터를 모두 삭제
set.clear() // 모든 데이터 삭제
set.size() // 크기 반환
set.contains(1) // 값 1이 있으면 true, 없으면 false

// 값 출력
// 방법 1: get 메소드가 없으므로 원소에 접근하려면 이터레이터 사용
Iterator iter = set.iterator();
while (iter.hasNext())
	System.out.println(iter.next());

// 방법 2: for-each문으로 원소에 접근
for (String item: set)
	System.out.println(item);

😁 HashMap

• HashMap : <key, value> : 특정 규칙 없이 출력된다.
• LinkedHashMap: <key, value> : 키값이 입력 순으로 정렬되어 출력된다.
• TreeMap: <key, value> : 키값이 알파벳 순으로(오름차순)으로 정렬된 상태로 출력된다.

HashMap<Integer, String> map = new HashMap<>();
HashMap<String, String> map = new HashMap<>();

map.put(1, "사과")
map.put(2, "바나나")
map.put(1, "포도") // key 1이 이미 존재하면 key 1의 value가 "포도"로 대체

map.remove(1) // key 값으로만 요소 삭제 가능
map.clear() // 전체 삭제

map.containsKey(1) // key 값 중 1이 있으면 true, 없으면 false
map.containsValue("사과") // value 중 "사과"가 있으면 true, 없으면 false

// 값 출력
// 방법 1
for (Integer i: map.keySet())
	System.out.println(i + map.get(i)); // 1 사과

// 방법 2: key와 value가 모두 필요할 때 주로 사용
for (Entry<Integer, String> entry: map.entrySet())
	System.out.println(entry.getKey() + entry.getValue()); // 1 사과