카테고리 없음
우선순위 큐와 순환 큐 - 자료구조, 파이썬(python)
에르미타쥬
2019. 2. 7. 16:39
우선순위 큐의 각 원소들은 우선순위를 갖고 있다. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.
만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다.
즉, 우선순위가 다르다면 우선순위에 따라 원소들이 처리되지만 우선순위가 같은 경우 큐의 본래 특성인 선입 선출에 따라 큐가 처리된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #노드 클래스 생성 class Node: def __init__(self, data, pri): self.data = data self.next = None self.pri = pri #우선순위 큐 class Priority_Queue: def __init__(self, data, pri): self.head = Node(data, pri) def Enqueue(self,data, pri): node = self.head while node.next: node = node.next if node.pri < pri: node.next = Node(data,pri) else: #node.pri >= pri node = self.head while node.next.pri < pri: node = node.next temp = node.next new = Node(data, pri) new.next = temp node.next = new del new def Dequeue(self): node = self.head while node.next: if node.next.next is None: node.next = None break else: node = node.next def display(self): node = self.head while node: print(node.data) node = node.next | cs |
직선 큐는 한가지 치명적인 단점을 가지고 있다. Dequeue 연산을 수행했다고 가정해볼 때, 가장 첫 번째 있는 요소를 빼내고 나면
그 뒤에 있는 원소들을 하나식 하나씩 옮겨줘야 하고 그만큼 옮겨주는 연산이 필요하게 된다.
큐의 원소들이 많아질수록 부담은 커지게 된다.
이러한 단점을 해결하기 위해 큐의 맨 앞에 전단(front)와 큐의 맨 뒤에 후단(rear)을 배치하는 방법이 있다. 큐를 제거할 때
전단을 후단에 가깝게 옮겨주면, 나머지 데이터가 움직일 필요 없이 맨 앞의 데이터가 전단 밖으로 벗어나 삭제된다.
다만, 이러한 방법도 단점이 있다. 제거 연산시 후단은 움직이지 않기 때문에 전단을 후단 쪽으로 옮기면 큐의 용량자체가 줄어들게 된다.
이러한 단점까지 보완한 게 순환 큐이다. 순환 큐란 배열의 처음과 끝을 이어놓은 구조이다. 물론 물리적으로는 일직선이지만, 논리적으로는 원형으로 보이는 것.
이런 구조는 어디가 배열의 시작이고 끝인지 알 수 없음. 전단과 후단이 저 원형내부를 계속 돌아가며 움직이는 것. 전단으로 젝
연산을 진행하더라도 더하는 연산으로 후단을 옮겨준다면 큐의 용량을 보존할 수 있다.
이 사진자료는 http://logonluv.blogspot.com/2015/02/datastructure-queue.html 를 참고했다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #순환큐 구현 class circular_Queue: def __init__(self, max): self.max = max self.list = [None] * self.max self.size = self.rear = self.front = 0 def next_idx(self, idx): return (idx + 1) % self.max def enqueue(self, item): if self.next_idx(self.rear) == self.front: print('큐가 꽉 찼습니다') else: self.rear = self.next_idx(self.rear) self.list[self.rear] = item self.size += 1 def dequeue(self): if self.size == 0: print('큐가 비었습니다') else: self.front = self.next_idx(self.front) self.list[self.front] = None self.size -= 1 def peek(self): self.front = self.next_idx(self.front) print(self.list[self.front]) def display(self): current = self.front while current != self.rear: current = self.next_idx(current) print(self.list[current]) | cs |