Algorithm 5일차

알고리즘에서 스택 자료구조를 활용할 수 있다.

스택은 마지막에 삽입한 자료를 가장 먼저 꺼내는 LIFO 자료구조이다.
java.util.Stack 클래스로 스택을 사용할 수 있다.

Stack의 주요 메서드는 아래와 같다.

1. push(Element e) : 스택에서 자료를 저장한다.
2. pop() : 스택에서 가장 늦게 삽입된 자료를 꺼낸다. 꺼낸 자료는 스택에서 삭제된다.
3. isEmpty() : 스택이 비었으면 true, 아니면 false를 반환한다.
4. size() : 스택의 크기를 반환한다.
5. peek() : 스택에서 가장 늦게 삽입된 자료를 확인한다.

알고리즘에서 큐 자료구조를 활용할 수 있다.

큐는 삽입한 자료 순서로 자료를 꺼내는 FIFO 자료구조이다.
java.util.Queue 인터페이스로 큐를 사용할 수 있다. (Queue queue = new ArrayDeque();)
LinkedList보다 ArrayDeque를 사용하면 30% 정도의 시간을 개선할 수 있다.

Queue의 주요 메서드는 아래와 같다.

1. offer(Element e) : 큐에서 자료를 저장한다.
2. poll() : 큐에서 가장 빨리 삽입된 자료를 꺼낸다. 꺼낸 자료는 큐에서 삭제된다.
3. isEmpty() : 큐가 비었으면 true, 아니면 false를 반환한다. (first == rear)
4. size() : 큐의 크기를 반환한다.
5. peek() : 큐에서 가장 늦게 삽입된 자료를 확인한다.

알고리즘에서 우선순위 큐 자료구조를 활용할 수 있다.

우선순위 큐는 큐의 특성을 가지고 있되, 마치 정렬을 해주는 효과를 주는 자료구조이다.
java.util.PriorityQueue 클래스로 우선순위 큐를 사용할 수 있다.

PriorityQueue의 주요 메서드는 Queue와 같다. PriorityQueue는 아래와 같이 사용한다.

import java.util.Comparator;
import java.util.PriorityQueue;

public class ATest {

	public static void main(String[] args) {
		// 오름차순
		PriorityQueue<Integer> orderPQ = new PriorityQueue<> ();
		orderPQ.offer(5);
		orderPQ.offer(2);
		orderPQ.offer(3);
		for (int i = 0; i < 3; i++) {
			System.out.print(orderPQ.poll() + " ");
		}
		System.out.println();
		
		// 내림차순
		PriorityQueue<Integer> reversePQ = new PriorityQueue<>(new Comparator<Integer> () {
			@Override
			public int compare(Integer o1, Integer o2) {
				return -(o1 - o2);
			}	
		});
		
		reversePQ.offer(5);
		reversePQ.offer(2);
		reversePQ.offer(3);
		for (int i = 0; i < 3; i++) {
			System.out.print(reversePQ.poll() + " ");
		}
	}
}

출력결과는 아래와 같다.

2 3 5
5 3 2

Comparator를 직접 구현하면 사용자 객체도 정렬 가능하다. 아래 예시를 살펴보자.

import java.util.PriorityQueue;

public class ATest {
	
	static class Data {
		private int n1;
		private int n2;
		
		public Data(int n1, int n2) {
			this.n1 = n1;
			this.n2 = n2;
		}

		@Override
		public String toString() {
			return "Data [n1=" + n1 + ", n2=" + n2 + "]";
		}
	}
	
	public static void main(String[] args) {
		// n1으로 오름차순 후, n2로 내림차순
		PriorityQueue<Data> PQ = new PriorityQueue<>((o1, o2) -> { // lambda 표현
				if (o1.n1 - o2.n1 == 0) {
					return -(o1.n2 - o2.n2);
				}
				
				return o1.n1 - o2.n1;
			}
		);
		
		PQ.offer(new Data(3, 1));
		PQ.offer(new Data(3, 2));
		PQ.offer(new Data(2, 1));
		
		for (int i = 0; i < 3; i++) {
			System.out.println(PQ.poll());
		}
	}
}

출력 결과는 아래와 같다.

Data [n1=2, n2=1]
Data [n1=3, n2=2]
Data [n1=3, n2=1]