[HUFS/자료구조] #5 큐와 덱

큐(Queue)

후입선출인 스택과 달리 선입선출(FIFO) 구조의 자료구조이다

 

삽입(enqueue)과 삭제(dequeue)의 위치가 정해져 있다 (rear/front)

큐의 ADT(추상자료형)

큐는 일상생활에서 광범위하게 사용된다

ex) 서비스센터 콜, 프린터 인쇄 작업, 실시간 스트리밍 버퍼링, 각종 대기열 등

 

큐의 구현

앞서 본 직선 형태의 큐가 선형 큐이다

 

선형 큐의 삽입은 간단하지만 삭제는 한 칸씩 당기기에 비효율적 O(n)

배열을 원형으로 사용하는 원형 큐는 front와 rear가 시계방향으로 돌아간다

 

공백상태(front=rear)에서 삽입은 rear+1 삭제는 front+1

원형 큐의 공백/포화/오류 상태 (공백과 오류를 구분하기 위해 한 칸은 꼭 비워 둠)

클래스 형태 파이썬 리스트로 원형 큐를 구현해보자!

 

원형 큐는 리스트의 길이를 미리 결정해야 한다 / 포화상태 체크

원형 큐의 삽입/삭제 연산

원형 큐의 출력 (front가 rear보다 인덱스 값이 커질 수 있기에 else문 계산식 적용)

원형 큐 테스트 프로그램

큐를 응용해 너비우선탐색을 해보자

 

위치 정보를 큐에 하나씩 삽입하며 상-하-좌-우 순서로 이동

너비우선탐색 알고리즘

너비우선탐색 테스트 프로그램

파이썬은 queue모듈로 큐와 스택 클래스를 제공한다!

 

import해서 사용해주면 된다

덱(Deque)

덱(double-ended queue)은 전단과 후단에서 모두 삽입/삭제가 가능하다!

 

덱 ADT(추상자료형) Front/Rear를 선택해 삽입/삭제

큐, 스택과 유사한 기능 구현이 가능하다

원형 큐와의 차이점(추가된 연산들)

즉, 만들어 둔 원형 큐를 상속받아 일부 기능을 추가해 덱을 구현할 수 있다!

 

원형 큐의 상속(재사용) 및 명칭 변경

원형 덱의 추가 메소드

원형 덱 테스트 프로그램

우선순위 큐

선출선입 개념을 가진 큐에 실생활의 우선순위의 개념을 도입한 우선순위(Priority) 큐는

입력 순서와 관련없이 우선순위가 높은 데이터가 먼저 출력된다

 

우선순위 큐의 ADT(추상자료형)

우선순위 순으로 삭제된다 (여기서는 숫자 큰 순서)

파이썬 클래스를 활용한 배열로 우선순위 큐 구현

우선순위 큐의 삭제연산 구현 (여기서는 최대값)

시간복잡도 정리 (정렬 리스트는 삽입과 동시에 정렬 연산을 하기에 O(n))