[알고리즘 기초] 06_Queue / Python

[알고리즘 기초] 06_Queue / Python

[알고리즘 기초] 06_Queue / Python

Queue

• Queue 의 특성
  • 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
    • 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조
  • 선입선출구조 (FIFO : First In First Out)
    • 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제 된다.
• 큐의 기본 연산
  • 삽입 : enQueue() ( Queue의 Rear 동작 )
  • 삭제 : deQueue() ( Queue의 Front 동작)
  • 생성 : createQueue()
  • 공백 확인 : isEmpty()
  • 포화 확인 : isFull()
  • 삭제 없이 원소 반환 : Qpeek()

 

1. 선형 큐

• 1차원 배열을 이용한 큐
  • 큐의 크기 = 배열의 크기
  • front : 저장된 첫 번째 원소의 인덱스
  • rear : 저장된 마지막 원소의 인덱스
• 상태 표현
  • 초기 상태 : front == rear == -1
  • 공백 상태 : front == rear (isEmapty() 상태)
  • 포화 상태 : rear == n-1 (n: 배열의 크기, n-1:배열의 마지막 인덱스)

• 초기 공백 큐 생성
  • 크기 n인 1차원 배열 생성
  • fornt 와 rear를 -1로 초기화

• 선형 큐 이용시의 문제점
  • 잘못된 포화상태 인식
    • 선형 큐를 이요하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불구하고, rear=n-1 인 상태 즉, 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게 됨
  • 해결 방법1
    • 매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시킴
    • 원소 이동에 많은 시간이 소요되어 큐의 효율성이 급격히 떨어짐
  • 해결 방법2 - 원형 큐
    • 1차 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용
    • 원형 큐의 논리적 구조

 

 

2. 원형 큐

• 원형 큐의 구조
  • 초기 공백 상태
    • front = rear = 0
  • Index의 순환
    • front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 그다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함
    • 이를 위해 나머지 연산자 mod를 사용함

 

 

3. 연결 큐

• 단순 연결 리스트(Linked List)를 이용한 큐
  • 큐의 원소 : 단순 연결 리스트의 노드
  • 큐의 원소 순서 : 노드의 연결 순서, 링크로 연결되어 있음
  • front : 첫 번째 노드를 가리키는 링크
  • rear : 마지막 노드를 가리키는 링크
• 상태 표현
  • 초기 상태 : front = rear = null
  • 공백 상태 : front = rear = null

 

 

4. 우선순위 큐 (Priority Queue)

• 우선순위 큐의 특성
  • 우선순의를 가진 항목들을 저장하는 큐
  • FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.
• 우선순위 큐의 적용 분야
  • 시뮬레이션 시스템
  • 네트워크 트래픽 제어
  • 운영체제의 테스트 스케줄링
• 우선순위 큐의 구현
  • 배열을 이용한 우선순위 큐
  • 리스트를 이용한 우선순위 큐
• 우선순위 큐의 기본 연산
  • 삽입 : enQueue
  • 삭제 : deQueue

 

 

5. BFS(Breadth First Search)

• 그래프를 탐색하는 방법에는 크게 두 가지가 있음
  • 깊이 우선 탐색(Depth First Search, DFS)
  • 너비 우선 탐색(Breadth First Search, BFS)
• 너비 우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했떤 정점을 시작점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함