[자료구조] Stack, Queue, Priority Queue

Stack (스택)

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

• 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 후입 선출 (LIFO) 구조
• 입구와 출구가 단 하나
• 연산자
  • push(data) : 데이터 삽입
  • pop() : 가장 마지막 데이터를 반환 (제거O)
  • peek() : 가장 마지막 데이터를 반환 (제거X)
  • empty() : 비어있는지 확인
  • search(data) : 주어진 데이터를 찾아 위치를 반환 (없을 경우 -1 반환, 1부터 시작)

---

Queue (큐)

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

• 한 쪽 끝에서 데이터가 삽입되고, 다른 한 쪽 끝에서는 삭제되는 선입 선출 (FIFO) 구조
• 임시로 자료를 저장하거나 버퍼와 같은 경우에 주로 사용하는 자료구조 형태
• LinkedList를 사용해 구현 가능
• 연산자
  • offer(data) : 데이터 삽입
  • add(data) : 데이터 삽입
  • remove()  : 가장 처음 들어온 데이터를 반환 (제거O)
  • poll() : 가장 처음 들어온 데이터를 반환 (제거O)
  • element(): 가장 처음 들어온 데이터를 반환 (제거X)
  • peek() : 가장 처음 들어온 데이터를 반환 (제거X)
  • isEmpty() : 비어있는지 확인

---

Priority Queue (우선순위 큐)

// 우선순위가 낮은 순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

// 우선순위가 높은 순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder())

 

• 큐의 구조를 가지면서, 데이터가 들어온 순서대로 나가는 것이 아닌 우선순위가 높은 데이터가 먼저 나가는 자료구조
• 특정 기준으로 정렬하고 싶을 경우, 우선순위 큐에 저장할 객체는 반드시 Comparable Interface를 구현해야함
• 내부 요소는 Heap으로 구성되어있는 이진트리 구조로 이루어져 있음
• 연산자
  • add(data) / offer(data) : data 삽입 (add는 Collection 클래스에서, offer는 Queue클래스에서 가져옴)
  • poll() / remove() : 우선순위가 가장 높은 값을 삭제
  • remove(index) : index 순위에 해당하는 값 삭제
  • clear() : 모든 값을 삭제
  • peek() : 우선순위가 가장 높은 값 가져옴