프로그래밍/Python 초보자가 작성하는 "C로 배우는 알고리즘"
[03-14] Queue [2/2] - Linked list를 사용해서 구현하기
더디게
2018. 5. 13. 23:10
1. 개요 & 알고리즘
Linked list로 Queue를 구현하는 경우, FIFO의 특성상 Doubly Linked List로 구현합니다. ("C로 배우는 알고리즘"1)
2. 동작 코드
기존 포스팅에서 사용했던 Doubly linked list 코드2를 기본으로, put()과 get()등을 추가합니다. 추가한 put()은 다음과 같습니다.
def put(self, data):
new_node = Node()
new_node.key = data
# Insert new_node in front of tail
self.tail.prev.next = new_node
new_node.prev = self.tail.prev
self.tail.prev = new_node
new_node.next = self.tail
return data
get()은 아래와 같이 추가했습니다.
def get(self):
t = self.head.next
if t == self.tail:
print("Queue underflow")
return False
data_temp = t.key
# Remove node
self.head.next = t.next
t.next.prev = self.head
return data_temp
3. 실행 코드
실행 코드는 앞선 포스팅3과 거의 같습니다 ("C로 배우는 알고리즘" 리스트 3-13 : QUEUE2.C에 대응)
# main() function
if __name__ == "__main__":
queue = QueueWithDoubleLinkedList()
print("Put 5, 4, 7, 8, 2, 1")
queue.put(5)
queue.put(4)
queue.put(7)
queue.put(8)
queue.put(2)
queue.put(1)
queue.print_queue()
print("Get")
data = queue.get()
queue.print_queue()
print("Getting value is ", data)
print("Put 3, 2, 5, 7")
queue.put(3)
queue.put(2)
queue.put(5)
queue.put(7)
queue.print_queue()
print("Initialize queue")
queue.clear_queue()
queue.print_queue()
print("Now queue is empty, get")
data = queue.get()
queue.print_queue()
print("Getting value is ", data)
5. 코드
반응형