Stack
스택은 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out) 구조입니다.
- top(peek) : 가장 최근에 저장된 데이터이자 먼저 삭제 될 데이터입니다. 그림상에서 요소 4가 해당됩니다.
- push : 데이터를 삽입하는것을 말하며 삽입 된 데이터는 삭제시 가장 먼저 삭제 될 데이터가 됩니다.
- pop : 데이터를 삭제할 때 사용하며 가장 최근에 저장된 데이터가 삭제됩니다.
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < 5; i++) {
stack.push(i + 1);
System.out.println(stack.peek());
} // 1, 2, 3, 4, 5 가 현재 들어가 있음
stack.pop(); // 1, 2, 3, 4
System.out.println(stack.peek()); // 4
System.out.println(stack.search(1)); // 4
System.out.println(stack.empty()); // falseQueue
선입선출(FIFO, First-In-First-Out) 방식을 따르는 자료구조로 먼저 저장된 데이터가 먼저 꺼내지는 형태입니다.
큐를 구현하기 위해 java.util 패키지에서 제공하는 Queue 인터페이스를 사용할 수 있습니다.
Queue<E> queue = new LinkedList<E>();
-
Enqueue : 데이터 삽입
-
Dequeue (JS의 shift) : 데이터 삭제
-
Front : Dequeue시 삭제되는 데이터 (가장 먼저 저장된 데이터)를 가르킵니다.
-
Rear : 추가될 새로운 요소의 위치를 가르킵니다.
-
offer(E e) : 큐의 맨 뒤에 지정된 요소를 추가합니다. 큐가 가득 차서 요소를 추가 할수 없는 경우 false를 반환합니다.
-
add() : 큐의 맨 뒤에 지정된 요소를 추가합니다. 큐가 가득 차서 요소를 추가 할수 없는 경우 IllegalStateException 예외를 발생시킵니다.
-
poll() : 큐의 맨 앞에서 요소를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다.
-
peek() : 큐의 맨 앞에서 요소를 반환합니다. 큐가 비어 있으면 null을 반환합니다.
-
clear() 큐의 모든 요소를 제거합니다.
remove
-> 큐의 첫번째 요소를 삭제(및 반환)한다.
만약 큐가 비어있으면 ⛔️예외가 발생⛔️한다.
poll
-> 큐의 첫번째 요소를 삭제(및 반환)한다.
만약 큐가 비어있으면 ⛔️null을 반환⛔️한다.
clear
-> 큐의 모든 요소를 삭제한다.
반환타입은 void이다.(반환은 하지 않는다.)
✔️ 우선순위 큐(Priority Queue) - Heap
큐(Queue) 데이터 구조를 기반으로 데이터를 ‘일렬로 늘어놓은 다음’ 그중에서 ‘가장 우선순위가 높은 데이터'를 '가장 먼저 꺼내오는 방식’으로 동작하는 클래스
우선순위 큐의 각 요소는 "값"과 "우선순위", 총 2개의 데이터를 가지고 있습니다.
따라서 선형큐와는 달리 우선순위가 높은 요소일수록 먼저 삭제되는 특징을 가지고 있으며 우선순위가 같은 데이터일 경우 삽입순서
Queue<Integer> pq = new PriorityQueue<>();
✔️ Deque
Deque는 양쪽 끝에 값을 추가 또는 삭제할 수 있는 특별한 자료구조이다.
즉, 스택과 큐를 하나로 합쳐놓은 것과 같은 기능
Deque<E> deque = new ArrayDeque<E>();
Deque<E> deque = new LinkedList<E>();
추가 : offerFirst(), offerLast(), addFirst(), addLast()
꺼내기(큐에서 제거됨) : pollFirst(), pollLast()
삭제 : removeFirst(), removeLast()
가져오기(큐에서 제거되지 않음) : getFirst(), getLast(), peekFirst(), peekLast()
