[03-14] Queue [2/2] - Linked list를 사용해서 구현하기

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. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_14.py

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. http://steadyandslow.tistory.com/105 [본문으로]
3. http://steadyandslow.tistory.com/112 [본문으로]