Stack , Queue

Queue

먼저 추가된 데이터가 먼저 나오는 FIFO(First In First Out) 동작을 갖는다( Stack과 반대 )

Queue의 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행, 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행

입력된 순서대로 처리할때 사용

프린터에서 여러문서를 순서대로 인쇄할때 사용됨

 

Stack 

마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 특징이 있는데, 이러한 자료의 구조를 LIFO(Last In First Out) 구조라고 한다. 
브라우저의 뒤로가기, 앞으로 가기 기능 구현할때 Stack이 활용

자바의 Stack클래스는 Vector클래스를 상속(extends)받기에 Thread-Safe 하다는 특징을 가지고 있다.

자바 공식 문서에 보면 애초부터 상속을 잘못하여 잘못 설계된 Stack 클래스보다 Deque 클래스를 사용하여 구현할 것을 권장하고 있다.

Deque(덱)

양방향으로 넣고 꺼낼수 있는 향상된 큐(queue) 자료구조 쯤으로 이해하면 된다.

상황에 따라서 큐처럼, 스택 처럼 사용할수 있다.

 

우선순위 큐( Priority Queue )

우선순위의 개념을 큐에 도입한 자료 구조

( 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나간다 )

요소들을 우선순위에 따라 정렬하여 처리하는 자료 구조

 

내부적으로 힙(Heap) 자료구조를 사용하여 요소들을 관리

( 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적 )

 

1 ~ 7 을 PriorityQueue에 순서대로 넣으면, Heap에 의해 

우선순위( 작은순서, 큰순서 )에 따라 아래와같이 2가지 형태로 저장됨

 

 

 

https://haservi.github.io/posts/algorithms/priority-queue/

Java Priority Queue(우선순위 큐) 원리 및 사용 방법