14강 요약

LIFO 입출력인 스택과 반대로 FIFO 입출력 형식인 큐(QUEUE)는 먼저 들어온 순서대로 출력된다. 즉 한쪽 방향으로 들어오고 나온다. 코딩테스트 문제를 풀면서도 스택은 본적이 몇번 있어도 큐는 잘 없던것 같다. 하지만 자주 사용되니 확실히 짚고 넘어가면 유익할듯 하다.

큐의 자료구조

1. 배열(Array)을 이용하여 구현

• Python 리스트와 메서드를 이용

2. 연결리스트(LinkedList)을 이용하여 구현

• 양방향 연결리스트 이용(단 여러형식의 연결리스트 가능)

큐의 메서드

size() - 현재 큐에 들어 있는 원소의 수
isEmpty() - 현재 큐가 비어 있는지
enqueue(x) - 데이터 원소 x를 큐에 추가
dequeue() - 큐에 맨앞에 저장된 데이터 원소 제거
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 sefl.data.pop(0)

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

스택(배열)과 거의 비슷하다. dequeue와 peek이 다른데 스택과 다르게 출력 방향이 다르기 때문에 0번 인덱스를 출력한다.

문제

양방향 연결리스트 큐

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 + 1:
            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

GitHub

https://github.com/ds02168/Study_Algorithm/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/14%EA%B0%95