[Java] 자료구조(2)_스택, 큐, 덱, 힙

큐(Queue)

• 선입 선출(FIFO) 구조로 제일 먼저 삽입된 애가 제일 먼저 나오게 되는 구조이다.
• 큐의 제일 뒤쪽에 데이터를 추가하는 것은 enqueue, 큐 앞에서 데이터를 빼내는 것을 dequeu라고 한다.
• Queue 클래스의 구현 클래스에는 LinkedList<>(), ArrayDeque<>()이 있고, 이들 중 ArrayDeque이 더 빠른 편이라고 한다.

import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayDeque;

Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new ArrayDeque<>();

queue1.add(1); //큐에 값 추가(성공 - true / 실패 시 Exception 발생)
queue2.offer(2); // 큐에 값 추가(성공 - true / 실패 시 false 반환)

queue1.remove();  //큐 제일 앞 쪽 값 제거(공백 큐 일 경우 "NoSuchElementException")
queue1.remove(2); //값을 지정해서 삭제도 가능함.
queue1.poll();    //큐 제일 앞 쪽 값 제거(공백 큐 일 경우 null반환)
queue1.peek();    
//값을 반환하지 않고 제일 앞 쪽에 있는 값만 보여줌
//공백이면 null을 반환

queue.isEmpty();
queue.clear(); 
queue.size();
queue.contains(value);

---

스택(Stack)

• 가장 나중에 들어온 데이터가 가장 먼저 빠져나가는 후입선출(LIFO) 구조이다.
• 스택의 제일 위에 값을 넣는 것을 push, 빼내는 것을 pop한다고 함.
• Stack 클래스를 사용하는 것보다 Deque를 사용하는 것을 권장한다. 그냥 이런게 있다- 정도만 알고 Deque 사용 법만 조금 익히면 좋을 듯 하다.

import java.util.Stack;

Stack<Integer> stk1 = new Stack<>();
Deque<Integer> stk2 = new ArrayDeque<>();
Deque<Integer> stk3 = new LinkedList<>();

stk1.push(value);
stk1.pop();

stk1.peek();
stk1.size();
stk1.isEmpty();
stk1.clear();

---

덱(Deque)

• 덱은 양쪽으로 삽입, 삭제가 가능한 자료구조에 해당
• 스택과 큐 모두의 성질을 가지기 때문에 스택 구현이든 큐 구현이든 덱으로 해결이 가능함
• 큐처럼 사용할 때는 add, remove / 스택처럼 사용할 때는 push, pop 을 그냥 사용하면 될 것 같다.

import java.util.Deque;

Deque<Integer> deque1 = new ArrayDeque<>();
Deque<Integer> deque2 = new LinkedList<>();

deque1.addFirst(1); // 앞에 값 삽입
deque1.addLast(2);  // 뒤에 값 삽입
deque1.add(3);      // addLast와 동일, 뒤에 값 삽입

deque2.offerFirst(1);  // 앞에 값 삽입
deque2.offerLast(2);   // 뒤에 값 삽입
deque2.offer(3);       // offerLast와 동일, 뒤에 값 삽입

deque1.push(4);        // 앞에 값 삽입

deque1.remove();  // 앞의 값 제거
deque1.removeFirst();  // 앞의 값 제거
deque1.removeLast();  // 뒤의 값 제거

deque1.poll();  //앞의 값 제거
deque1.pollFirst();  // 앞의 값 제거
deque1.pollLast(); // 뒤의 값 제거

deque1.pop(); //앞의 값 제거

deque1.peek();    // 제일 앞에 있는 값
deque1.peekLast();    // 제일 뒤에 있는 값

deque2.isEmtpy();
deque2.size();
deque2.clear();

---

우선순위 큐 (Priority Queue)

• 들어온 순서에 상관 없이 우선순위에 따라 정렬되는 큐에 해당되는 자료구조
• 일반적으로 List자료구조나 Set자료구조를 우선순위 큐의 생성자 인자로 받아서 넘기는 방식도 사용함.
• 기본적으로 min heap 이기 때문에 숫자는 오름차순, 단어는 사전 순으로 정렬이 됨.

List<Integer> lst = List.of(1, 3, 5, 2, 7, 4);
Queue<Integer> pq = new PriorityQueue<>(lst);

// 오름차순 정렬
Queue<Integer> pq1 = new PriorityQueue<>(Collections.reverseOrder());

// 우선순위 커스터마이징
Queue<int[]> pq1 = new PriorityQueue<>(new Comparable<int[]>(){
				@Override
				public int compare(int[]o1, int[]o2){
					return o1[0] - o2[0];
				}				
});

---

Comparable<T> 클래스 vs Comparator<T> 클래스

Comparable

• 객체의 순서를 정하기 위한 인터페이스임
• 클래스에서 해당 인터페이스를 구현하면 클래스끼리의 비교가 가능해진다.
• 메서드 : int compareTo(T o) → 현재 객체와 매개변수로 받은 객체를 비교함

import java.util.*;

class Student implemets Comparable<Student> {
	private String name;
	private int score;
	
	public Student(String name, int score){
			this.name = name; 
			this.score = score;
	}
	
	@Override
	public int compareTo(Student o1){
			return Integer.compare(this.score, o1.score);
	}
}

Comparator

• 외부에서 별도로 정렬 기준을 정해줄 때 사용함.
• 클래스가 comparable 인터페이스를 구현하지 않았을 때 주로 사용함.

import java.util.*;

Class Student{
	private String name;
	private int score;
	
	public Student(String name, int score){
		this.name = name;
		this.score = score; 
	}
}

public class Comp{
	public static void main(String[] args){
			List<Student> ls = new ArrayaList<>();
			
			Comparator<Student> scoreComp = new Comparator<Student>(){
				@Override
				puvlic int compare(Student s1, Student s2){
					return s1.score - s2.score;
				}
			}	
	}
}

compareTo는 Integer, String 클래스에서는 이미 정의가 되어 있다!

• Integer를 바로 비교하는데 사용하거나 String을 바로 비교하는데 사용이 가능하다.

String str1 = "apple";
String str2 = "banana";
System.out.println(str.compareTo(str2));
Integer num1 = 10;
Integer num2 = 20;
System.out.println(num1.compareTo(num2));