[프로그래머스 강의] 14강 큐

---

'어서와! 자료구조와 알고리즘은 처음이지?'

---

큐(Queue)

 

✔  자료를 보관할 수 있는 선형 구조 

✔ 데이터 삽입 시에는 한 쪽 끝에서 밀어 넣어야 한다. → 인큐(enqueue) 연산

✔ 데이터 꺼낼 시에는 반대쪽에서 꺼내야 한다. → 디큐(dequeue) 연산

✔ 선입선출(FIFO, First-In First-Out) 특징을 가진다. 

 

큐의 추상적 자료구조 구현

1. 배열(Array)를 이용하여 구현한다.

    →  파이썬 리스트와 메서드를 이용

 

2. 연결 리스트(Linked list)를 이용하여 구현한다.

   →  양 방향 연결리스트를 이용

 

연산의 정의

1. size() - 현재 큐에 들어있는 데이터 원소의 수를 구한다.

2. inEmpty() - 현재 큐가 비어있는지를 판단한다.

3. enqueue(x) - 데이터 원소 x를 큐에 추가한다.

4. dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거한다. (또한, 반환)

5. peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환한다. (제거하지 않음)

 

배열로 구현한 큐

class ArrayQueue:

    # 빈 큐를 초기화
    def __init__(self):
        self.data = []

    # 큐의 크기를 리턴
    def size(self):
        return 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]

 

배열로 구현한 큐의 연산 복잡도

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

 

[ 문1. 양방향 연결 리스트로 구현하는 큐 ]

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError('Index out of range')

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount


class LinkedListQueue:

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

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

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

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

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

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

def solution(x):
    return 0