linked_queue

linked_queue

Linked List는 노드들이 위와 같이 여러 구조로 연결한 것입니다.

활용

*삽입

자료를 삽입하려면 추가할 장소로 가서 기존의 링크를 끊은 후에 추가할 위치의 prev와 next를 연결하는 힙니다. 시간 복잡도는 다이렉트이기에 O(1)입니다.

*제거

자료를 삭제하려면 삭제 하고 싶은 부분의 prev와 next를 연결시키면 되고 이것 또한 O(1)입니다.

*자료 검색

자료를 검색하려면 맨 앞 부분인 head부터 tail까지 가야하므로 노드를 순차적으로 검색하고 시간 복잡도는 O(n)입니다.

CODE

##class Node를 짜는 것입니다.

class Node:
    def __init__(self, data, next_=None): #data를 할당하고 그 다음에 올 인자를 초기화
        self.data = data # 할당
        self.next = next_ #초기화
#연결형 큐 클래스를 작성해보겠습니다.

class LinkedQueue:

    def __init__(self): #첫 함수는 항상 국룰
        self._size = 0 # 길이는 0으로 초기화
        self.head = Node(None) # head에 처음엔 아무 것도 없는 더미
        self.tail = self.head # tail도 head와 마찬가지

    def offer(self, data): #offer함수는 push함수와 동일한 데이터 넣는 것입니다.
        node = Node(data) #node에 data 넣기
        self.tail.next = node# tail다음에 Node 
        self.tail = self.tail.next # tail 다음에 node 담김
        self._size += 1 #길이 1 증가

    def poll(self): # 데이터 빼기
        if self._size == 0: # 길이가 0이라면
            raise RuntimeError("Empty") # 비어있다는 문구 출력

        ret = self.head.next #head를 넘어 다음 노드
        self.head.next = ret.next # head의 다음 노드는 ret할당
        ret.next = None # ret는 비어있다[데이터가 잘 빠짐]
        self._size -= 1# 데이터의 길이가 하나 줄어든다
        if self.head.next is None: # head다음에 노드가 없다면
            self.tail = self.head # tail이랑 head가 같은 관계
        return ret.data # 그냥 data출력

    def peek(self): #처음에 빠지는 데이터 추출
        if self._size == 0: # 아무것도 없다면
            raise RuntimeError("Empty") #비어있다는 말을 출력
        return self.head.next.data # head다음에 데이터를 반환

    def size(self): #길이 알려주는 함수
        return self._size # 길이 반환

    def clear(self):# 초기화
        self.head.next = None # head 다음 노드 없다
        self.tail = self.head # head 와 tail이 같다
        self._size = 0 # 사이즈는 0
if __name__ =='__main__': #main.py
    q = LinkedQueue() # LinkedQueue()를 계속 쓸 수 없으니 q로 할당
    for elem in [5,3,6,8,9,10]: #[5,3,6,8,9,10]하나씩 빠진다
        print(f"q.offer({elem})") #offer함수 적용
        q.offer(elem)#데이터 넣기

    print(f"q.size(): {q.size()}") #길이 확인[ 데이터 삽입이 잘 되었나?]
    while q.size() > 0: #q,size가 0보다 크다면
        print(f"q.peek(): {q.peek()}") #peek를 구해서 처음에 빠지는 숫자 확인
        print(f"q.pop(): {q.poll()}") #데이터 빼기

    print(f"q.size(): {q.size()}") #길이 확인을 통해서 데이터가 잘 빠졌나 확인