자료구조

본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

우선순위 큐

우선순위 큐의 소개

 

(designed by by Peacock Dream) 

 할머니, 할아버지와 내가 여행을 떠난다. 할머니는 연세가 드셨지만 걷는데에는 지장이 없으시고 할아버지는 걸음이 불편하셔서 휠체어를 타고 계신다. 드디어 우리는 아름다운 섬으로 떠나기 위해 배를 타려는데 갑자기 내 뒤에 폭탄이 떨어진다. 이때 누구를 먼저 배에 태울까? 

 당연히 걸음이 편찮으신 할아버지를 먼저 태우고 할머니, 그리고 내가 마지막으로 탄다. 이처럼 컴퓨터에서도 우선순위의 개념이 필요할 때가 있다. 예를 들면 네트워크 패킷 중에서 네트워크 관리와 관련된 패킷은 일반 패킷보다 우선순위를 가진다. 또 운영체제, 수치해석적 계산 등 우선순위를 갖을 수 있는 여러 분야에서 이용된다.

 우선순위 큐는 이러한 우선순위의 개념을 큐에 도입한 자료 구조이다.

 

큐 vs 우선순위 큐

큐는 선입선출(First In First Out : FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐에서는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다.

자료구조 삭제되는 요소
스택 가장 마지막에 들어온 데이터
가장 먼저 들어온 데이터
우선순위 큐 가장 우선순위가 높은 데이터

 

우선순위 큐의 구현방법

1) 배열을 사용하는 방법
2) 연결리스트를 사용하는 방법
3) 히프를 사용하는 방법
  • 봤어요 (0명)

댓글

댓글 본문
작성자
비밀번호
버전 관리
잘살겠습니다
현재 버전
선택 버전
graphittie 자세히 보기