[Programmers] 10. 기본 자료구조: 큐 (Queue) (1): 큐 기본

illstandtall·2021년 4월 29일

programmers python 연결리스트 자료구조 큐

Programmers dev course

목록 보기

11/34

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

자료구조 4. 큐 (Queue)

한 쪽에서는 데이터를 넣기만 하고, 반대쪽 끝에서는 꺼내기만 합니다.
들어오는 순서대로 데이터를 입력하고 꺼낼 수 있고, 따라서 선입선출 (FIFO: First in First Out) 자료구조입니다.

큐에서 발생하는 오류

비어있는 큐에서 데이터를 꺼내려 할 때 (큐 언더플로우: Queue Underflow)
꽉찬 큐에 데이터를 넣으려 할 때 (큐 오버플로우: Queue Overflow)

큐의 연산

size(): 현재 큐에 들어있는 데이터 원소 개수를 반환합니다.
isEmpty(): 현재 큐가 비어있는지를 판단합니다.
비어있으면 True를, 비어있지 않으면 False를 반환합니다.
enqueue(x): 큐에 데이터 x를 추가합니다.
dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거하며, 반환합니다.
- 시간 복잡도: $O(N)$ - 배열로 큐를 구현하면, 맨 앞 원소를 꺼내기 위해 모든 원소들을 하나씩 앞으로 밀어야하기 때문에 시간 복잡도는 리스트의 길이에 비례합니다.
  - 따라서 큐를 양방향(이중)연결리스트로 구현한다면, 시간을 많이 줄일 수 있습니다.
peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환합니다.
<참고> 배열로 구현한 큐 연산의 시간 복잡도

연산	복잡도
size()	$O(1)$
isEmpty()	$O(1)$
enqueue()	$O(1)$
dequeue()	$O(N)$
peek()	$O(1)$

큐 구현

배열을 이용한 구현: Python 리스트와 함수 이용

class ArrayQueue:
    def __init__(self):
        self.data = []

    def size(self):
        return self.len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]

양방향(이중)연결리스트 이용하여 구현: 양방향 연결리스트

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class LinkedListQueue:
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.nodeCount

    def isEmpty(self):
        return self.data.nodeCount == 0

    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.data.nodeCount+1, node)

    def dequeue(self):
        return self.data.popAt(1)

    def peek(self):
        return self.data.getAt(1).data