[Python 자료구조 #연결리스트2] 원형연결리스트 : 연결된 큐

* 원형연결리스트의 응용 : 연결된 큐(linked queue)

• 맨 앞과 뒤에 있는 노드를 front와 rear가 가리키는 구조. 삽입은 후단(rear), 삭제는 전단(front)에서 이뤄짐
• front는 tail.link이다.
• 원형연결리스트에서는 tail(또는 rear)만을 변수로 저장한다. front를 변수로 하면 rear을 찾을 때 O(n)의 시간이 걸리므로 tail을 사용하는 것이 rear와 front에 바로 접근할 수 있다는 점에서 훨씬 효율적이다.

출처 : 파이썬으로 쉽게 풀어쓴 자료구조

class Node:  # 노드 클래스 생성
    def __init__(self, elem, link=None):
        self.data = elem
        self.link = link


class CircularLinkedQueue:
    def __init__(self):
        self.tail = None

    def isEmpty(self):
        return self.tail == None

    def clear(self):  # 큐 초기화
        self.tail = None

    def peek(self):
        if not self.isEmpty():
            return self.tail.link.data  # front의 data를 반환

    def enqueue(self, item):
        node = Node(item, None)
        if self.isEmpty():  # 큐가 공백상태면
            node.link = node  # 새 노드의 링크가 자기 자신을 가리킴
            self.tail = node  # tail은 새 노드를 가리킴
        else:  # 큐가 공백이 아니면
            node.link = self.tail.link  # 새 노드의 링크에 기존 tail이 가리키던 노드(front)의 링크를 이어받음
            self.tail.link = node  # tail이 가리키던 직전노드의 링크에 새 노드의 주소를 덮어씌움
            self.tail = node    # tail에 새 노드의 주소를 덮어씌움

    def dequeue(self):
        if not self.isEmpty():  # 큐가 공백이 아니면
            data = self.tail.link.data  # front의 data를 data라는 변수에 저장
            if self.tail.link == self.tail: # 만약 front의 주소가 tail이 가리키는 노드의 주소와 같다면(큐에 1개의 노드만 있는 경우)
                self.tail = None    # tail은 None값을 갖는다.
            else:   # 큐에 2개 이상의 노드가 있는 경우에
                self.tail.link = self.tail.link.link    # front는 front 다음 노드의 주소를 갖는다.
            return data # front의 data값을 반환한다.

    def size(self):
        if self.isEmpty():
            return 0
        else:
            count = 1
            node = self.tail.link
            while not node == self.tail:
                node = node.link
                count += 1
            return count

    def display(self, msg="CircularLinkedQueue:"):
        print(msg, end="")
        if not self.isEmpty():
            node = self.tail.link
            while not node == self.tail:
                print(node.data, end=" ")
                node = node.link
            print(node.data, end=" ")
        print()

연결된 큐 예시

q = CircularLinkedQueue()
for i in range(8):
    q.enqueue(i)
q.display()
for i in range(5):
    q.dequeue()
q.display()
for i in range(8, 14):
    q.enqueue(i)
q.display()
-------------------------------
CircularLinkedQueue:0 1 2 3 4 5 6 7       
CircularLinkedQueue:5 6 7 
CircularLinkedQueue:5 6 7 8 9 10 11 12 13