class Node:
def __init__(self, value = None, next = None):
self.data = value
self.next = next
def __str__(self):
return str(self.data)
#우선순위 큐
class Priority_que:
def __init__(self, head = None ):
self.node = Node(head)
self.head = self.node
#제일 앞의 큐를 뽑아낸다
def Dequeue(self):
self.head = self.head.next
#데이터를 받아서 순위에 따라 배치한다
def Enqueue(self,data):
insert_data = Node(data)
comp = self.head
pre = Node()
if insert_data.data < comp.data:
self.head = insert_data
insert_data.next = comp
else:
while True:
if comp.data >= insert_data.data:
pre.next = insert_data
insert_data.next = comp
break
elif comp.data < insert_data.data:
if comp.next == None:
comp.next = insert_data
break
else:
pre = comp
comp = comp.next
#우선순위 큐를 출력한다
def PrintLL(self):
node_print = self.head
while True :
if node_print.next == None:
print(node_print.data)
break
else:
print(node_print.data , "->", end=" ")
node_print = node_print.next
#큐를 만든다
k=Priority_que(5)
#여러 숫자로 큐를 만든다
k.Enqueue(4)
k.Enqueue(7)
k.Enqueue(8)
k.Enqueue(4)
k.Enqueue(7)
k.Enqueue(8)
k.Enqueue(4)
k.Enqueue(7)
k.Enqueue(8)
k.Enqueue(10)
#만든 큐를 출력한다
k.PrintLL()
#큐를 뽑아낸다
k.Dequeue()
k.PrintLL()
k.Dequeue()
k.Dequeue()
k.PrintLL()
1. class Node:
우선 받은 data 값과 next 값을 초기화 해 줄수있다.
2. Priority_que:
노드를 가리키는 self.node와 제일 처음노드 self.head를 초기값으로 가진다.
2-1 Dequeue
제일 첫 머리의 큐를 밖으로 보내기 때문에 self.head 값을 next값으로 바꾸어 준다.
2-2 Enqueue
먼저 넣으려는 노드를 만들고 그 전의 값을 저장하기위해 노드를 하나더 만든다. 그리고 제일 첫값을 비교값으로 만든다. 우선 if문으로 비교하는 데이터값보다 넣으려는 값이 더 작다면 그 값을 제일 앞에 오게 만들어 준다.
그것이 아니라면 while문 안에서 우선 조건을 모두 만족시키지 않으면 pre값에는 현재 비교값 그리고 비교값에는 다음비교값을 넣어서 한칸 이동시켜준다. 그리고 만약 비교값이 넣어주려는 노드값보다 크면 pre값의 next에 삽입값을 넣어주고 삽입값의 next에 비교값을 넣어준다. 그리고 만약 모든 비교값보다 삽입값이 더 크다면 제일 뒤의 값의 next에 삽입값을 넣어준다.
2-3 PrintLL
제일 마지막 값까지 계속 출력시켜준다
'파이썬으로 구현한 알고리즘' 카테고리의 다른 글
| Regular Expression으로 전화번호 Search 구현하기 (0) | 2017.11.16 |
|---|---|
| Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기 (0) | 2017.11.16 |
| Boyer-Moore Algorithm 구현하기 (0) | 2017.11.11 |
| KMP Algorithm 구현하기 (0) | 2017.11.11 |
| Linked list 구현하기 (0) | 2017.09.25 |