Stack
스택은 자료의 입출력이 후입선출(LIFO)의 형태로 일어나는 자료구조를 말한다.
// Integer형 스택 선언
Stack<Integer> stackInt = new Stack<>();
// String형 스택 선언
Stack<String> stackStr = new Stack<>();
// Boolean형 스택 선언
Stack<Boolean> stackBool = new Stack<>();
위와 같은 형식으로 스택을 선언해준다.
관련 연산
init()
스택을 초기화한다.
empty()
스택이 비어있으면 true, 비어있지 않으면 false를 반환한다.
push(x)
데이터를 스택에 추가하고 해당 값을 반환한다.
import java.util.Stack;
class StackExample{
public static void main(String[] args){
Stack<Integer> sta = new Stack<>();
sta.push(1);
sta.push(2);
System.out.println(sta); //[1, 2, 3] 출력
}
}peek()
스택의 가장 위 요소인 top 요소를 반환하며 스택에선 변화가 없다. 비어있는데 호출할 시 NoSuchElementException이 발생한다.
import java.util.Stack;
class StackExample{
public static void main(String[] args){
Stack<Integer> sta = new Stack<>();
sta.push(1);
sta.push(2);
System.out.println(sta.peek()); //2 출력
}
}Queue
스택은 나중에 들어온 데이터가 먼저 나가는 구조라면 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조이다. 이런 특성을 선입선출(LIFO) 라고 한다.
import java.util.Queue;
import java.util.LinkedList;
Queue<자료형> 변수명 = new LinkedList<>();
Queue 변수명 = new LinkedList();위와 같은 선언을 통해 큐 자료구조를 사용할 수 있다.
관련 연산
add(x), offer(x)
큐에 해당 값을 삽입할 때 사용한다.
add(x): 삽입 성공시 true, 실패하면 Exception 발생offer(x): 삽입 성공시 true, 실패하면 false 반환
remove(), remove(x), poll()
모두 큐에서 값을 삭제할 때 사용한다.
remove(): 큐의 first에 위치한 값을 삭제한다. 반환 값으로 삭제된 값을 가진다. 공백큐라면NoSuchElementException이 발생한다.remove(x): 반환 값은boolean이며, 해당 값이 존재하면 삭제 후 true를 반환하고 존재하지 않으면 false를 반환한다.poll(): 삭제된 값을 반환 값으로 가지며 공백 큐이면 null을 반환한다.
size()
큐의 사이즈를 반환한다.
clear()
큐를 초기화할 때 사용한다.
element(), peek()
큐의 front에 위치한 값을 반환한다.
element(): 큐의 head에 위치한 값을 반환 값으로 가지며, 공백 큐일 때NoSuchElementException이 발생한다.peek(): 큐의 head에 위치한 값을 반환 값으로 가지며, 공백큐이면 null을 반환한다.
Priority Queue
일반적인 큐의 구조인 FIFO 구조를 가지면서 데이터가 들어온 순서대로 나가는 것이 아니라 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
PriorityQueue 사용을 위해서는 Comparable 인터페이스를 구현해야한다.
Comparable 인터페이스를 구현하면 compareTo 메서드를 오버라이드하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue가 우선순위가 높은 데이터를 먼저 처리한다.
PriorityQueue를 사용할땐 Heap을 이용해 구현하는 것이 일반적이다.
데이터를 삽입할 때 최대/최소 힙으로 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다.
import java.util.PriorityQueue;
import java.util.Collections;
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();
//높은 숫자가 우선 순위
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());관련 연산
add(x), offer(x)
add(x): 삽입 성공시 true, 실패하면 Exception 발생offer(x): 삽입 성공시 true, 실패하면 false 반환
삽입 실행시, 아래와 같은 구조로 데이터가 삽입된다.
먼저 7이 들어오면 마지막에 넣고, 부모와 비교해 더 작으면 값을 교환한다.
부모 노드와 계속해서 비교한 뒤 부모 노드보다 값이 크다면 교환되지 않고 그자리에 있는다.
그림 출처 : https://coding-factory.tistory.com/603
remove(), poll(), clear()
remove(): 데이터가 없다면 예외 발생poll(): 삭제된 값을 반환하고, 데이터가 비어있다면 null 반환clear(): 초기화
삭제 연산 실행시, 아래와 같은 구조로 데이터가 삭제된다.
마지막 노드와 루트 노드 자리를 바꾼다. 최소힙이기 때문에 루트 노드인 8과 자식 노드끼리 비교해 더 작은 숫자를 루트노드로 바꿔준다.
8 을 자식 노드인 16과 비교해 자식 노드가 더 작다면 자리를 바꿔준다. 하지만 이때 8이 더 작기 때문에 변경되지 않는다.
그림 출처 : https://coding-factory.tistory.com/603
peek(), element()
peek(): 첫번째 값을 반환하고 제거하진 않음. 비어있다면 null 반환element(): 첫번째 값 반환하고 제거하진 않음. 비어있다면 예외 발생
