1. Stack
- 삽입과 삭제 연산이 후입선출(Last-in first-out)로 이루어지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징을 가지고 있다.
- 새 값이 스택에 들어가면 top이 새 값을 가리킨다. 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 된다. (단방향 입출력 구조: 데이터의 들어오는 방향과 나가는 방향이 같다. > 데이터를 하나씩만 넣고 뺄 수 있다)
- 깊이 우선 탐색(DFS: Depth First Search), 백트래킹 종류의 로직에 효과적이다.
- 재귀 함수의 동작 흐름과 같은 구조이다
[용어 설명]
1) push() : top 위치에 새로운 데이터를 삽입하는 연산
2) pop() : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
3) peek() : top 위치에 현재 있는 데이터를 단순 확인하는 연산
4) clear() : 스택의 모든 내용을 제거하는 메서드
5) empty() : 스택이 비어있는지 여부 반환하는 메서드로 비어있을 경우 true, 비어있지 않을 경우 false를 반환한다
6) search() : 메서드의 인자를 스택에서 검색하여 해당 위치를 반환하다. 인자가 여러개일 경우 마지막 위치를 반환하고, 여기서 위치는 인덱스가 아닌 바져나오는 순서를 뜻한다. 찾는 값이 스택에 없을 경우 -1을 반환한다
- 스택의 선언은 Stack<T> 스택 이름 = new Stack<>(); 형태로 선언할 수 있는데, 이때 데이터 타입은 클래스나 래퍼 클래스로 선언할 수 있다.
// Integer형 스택 선언
Stack<Integer> stackInt = new Stack<>();
// String형 스택 선언
Stack<String> stackStr = new Stack<>();
// Boolean형 스택 선언
Stack<Boolean> stackBool = new Stack<>();
[예제]
import java.util.Stack;
public class Main{
Stack<Integer> st = new Stack<>();
//push() > 값 추가
st.push(1);
st.push(2);
st.push(3);
//pop() > 값 제거 (후입선출이기 때문에 마지막 push()했던 값인 3부터 차례대로 제거)
st.pop();
//peek() > 값 확인 (제일 마지막에 들어간 값 확인됨)
System.out.println(st.peek()); //2
st.pop();
st.pop();
}
2. Queue
- 삽입과 삭제 연산이 선입선출(First-in First-out) 로 이루어지는 자료구조이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나가기 때문에 삽입과 삭제가 양방향에서 이루어진다.
- 새 값 추가는 큐의 rear에서 이루어지고, 삭제는 큐의 front에서 이루어진다.
[용어 설명]
1) rear : 큐에서 가장 끝 데이터를 가리키는 영역
2) front : 큐에서 가장 앞의 데이터를 가리키는 영역
3) add( ) : rear부분에 새로운 데이터를 삽입하는 연산으로 삽입 성공 시 true, 실패 시 Exception발생
4) offer() : 새로운 데이터를 삽입하는 연산으로 삽입 성공 시 true, 실패 시 false 반환
5) poll() : front부분에 있는 데이터를 삭제하고 확인하는 연산으로 공백일 시 null을 반환
6) peek() : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산으로 공백일 시 null을 반환
7) remove() : 큐에 해당 값이 존재하면 해당 값 삭제 후 true 반환, 존재하지 않으면 false 반환
8) element() : 데이터를 확인할 때 사용하는 연산으로 공백일 시 Exception(NoSuchElementException) 발생
9) clear() : 큐에 있는 데이터 초기화
10) size() : 큐의 사이즈 반환(int)
11) contains() : 큐에 해당 원소가 존재하는지의 여부 확인하는 메서드로 값이 존재할 떄 true, 존재하지 않을 대 false 반환
- 너비 우선 탐색(BFS: Breadth First Search)에서 자주 사용된다.
- 우선순위 큐(priority queue) : 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 큐 설정에 따라 frotn에 항상 최댓값 또는 최솟값이 위치한다. 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현한다.
- 자바에서 스택은 Stack 클래스로 구현하여 제공하고 있지만 큐는 Queue 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하지 않는다. 그래서 큐를 인스턴스화 하려면 Queue 인터페이스를 구현하는 클래스 중 하나를 사용해야 한다.
//LinkedList<> 가장 많이 사용되는 구현체 중 하나
Queue<Integer> queue = new LinkedList<>();
//PriorityQueue<> 우선순위큐
Queue<Integer> queue = new PriorityQueue<>();
[예제]
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.add(1); // 요소 추가
queue.add(2);
queue.add(3);
System.out.println(queue.poll()); // 출력 후 제거
System.out.println(queue.peek()); // 출력 (제거하지 않음)
}
}
'Programming Language > Java Algorithm' 카테고리의 다른 글
[개념] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) (0) | 2024.09.12 |
---|---|
[개념] 정렬 알고리즘 (0) | 2024.09.12 |