[Datastructure] 큐, Queue

큐

스택은 후입선출법(LIFO)방식을 따르는 자료구조이다.
반면에 큐는 선입선출법(FIFO)방식을 따르는 자료구조이다.
회계를 배우면 2가지의 재고자산 매출원가 계산방식을 알 수 있다.(평균법과 선입선출법) 그래서 조금은 익숙한 개념이다.

큐의 연산 종류

1. enqueue: 큐에 rear 부분에 삽입한다.
2. dequeue: 큐의 front 부분의 값을 삭제하고 리턴한다.
3. front: 큐의 front 부분의 값을 리턴한다.

Function

class Queue():
    def __init__(self):
        self.items = []
        self.front_index = 0

    def enqueue(self, value):
        self.items.append(value)

    def dequeue(self):
        if self.front_index == len(self.items):
            print('queue empty)
            return None
        else:
            returnvalue = self.items[self.front_index]
            self.front_index += 1
            return returnvalue

    def front(self):
        if self.front_index == len(self.items):
            print('queue empty)
        else:
            returnvalue = self.items[self.front_index]
            return returnvalue

기본적으로

1. 생성자
2. enqueue
3. dequeue
4. front

이다.

1,2는 앞서 스택에서 다뤘으니 다를 바 없고,
dequeue를 보자.

dequeue

dequeue를 위해서는 1가지 조건이 필요한데, 큐가 현재 비어있으면 dequeue연산은 불가능하다는 것이다. 따라서 비어있는 큐를 체크할 수 있는 수단이 필요한데, 그것이 self.front_index이다.

만약 큐가 비어있지 않아 dequeue연산을 실행했다면, front_index가 큐의 front value의 인덱스값을 표현하므로 self.items[self.front_index] 를 리턴하면된다.

그리고 이제 front_index가 1 증가하므로 self.front_index += 1 을 해주면 된다.

Front

front연산은 dequeue를 이해했다면 단순하다. dequeue를 했을때, 실제 self.items의 value를 삭제하는 대신, self.front_index 를 증가시킴으로써 dequeue 한 값을 함수 상에서 없는 값 취급을 했다.

front연산은 삭제하지않고 리턴만하기 때문에 self.items[self.front_index]의 값을
리턴해주기만 하면 된다.

큐 사용의 예시

요세푸스 문제

요세푸스 문제, 출처:위키백과

전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다.  


n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.

이 순열은 역사가 요세푸스가 겪은 일화에서 유래하였다

요세푸스 문제는 큐를 이용해 풀 수 있는 유명한 문제이다.
입력으로 n과 k가 주어지고, n명중에서 k번째 사람을 계속 모임에서 제외한다.
이를 프로그래밍에서 구현하기 위해서는 1부터 k-1번째 사람에 대해서 어떻게 논리적으로 구현할 것인가가 중요한데, k번째 사람을 제외했다면 1부터 k-1번째 사람은 k번째 사람을 제외한 후 다음 연산에 포함되어야 한다.

이를 프로그래밍에서 구현하면

#큐함수는 위에것 그대로 사용
def joseph(n,k):
    josephuslst = Queue() #큐 초기화
    for i in range(1,n+1):
        josephuslst.enqueue(i)

    for num in range(n-1): #마지막사람은 리턴하면서 dequeue하므로 n-1명까지만.
        for i in range(1,k):
            josephuslst.enqueue(josephuslst.dequeue()) #1부터 k-1번째 수까지 dequeue하고 바로 enqueue
        josephuslst.dequeue() #k번째 수 dequeue
    josephuslst.dequeue()

Dequeue

큐의 종류 중, front와 rear 모두에서 삽입과 삭제가 가능한 큐를 Dequeue라고 부른다.
위의 dequeue연산과는 다르다, 구분하기위해 대문자로 쓴다.
왼쪽과 오른쪽에서 삽입삭제가 가능하므로 push2개, pop2개의 4가지의 연산을 해야한다.
파이썬에서는 collections라는 모듈에 deque란 클래스로 dequeue가 이미 구현되어 있다.

class deque():
    def __init__(self):
        self.items = []
        self.front_value = 0



    def push(self, value):
        self.items.append(value)

    def pushleft(self, value):
        self.items.insert(self.front_value,value)

    def pop():
        if len(self.items) == self.front_value:
            print('queue is empty')
            return None
        else:
            return self.items.pop()

    def popleft():
        if len(self.items) == self.front_value:
            print('queue is empty')
            return None
        else:
            x = self.items[self.front_value]
            self.front_value += 1
            return x

popleft함수와 push함수는 queue와 동일,
pushleft함수에는 insert를 이용해 현재 큐의 첫번째인덱스로 인식하고있는 self.front_value에 value를 넣는다.

pop의 경우, 동일하게 리스트가 현재 비어있으면 None리턴, 아닌경우, pop()함수를 이용해 리턴한다.

참고자료

개인적인 공부를 위한 글이며, 모든 저작권은 신천수 교수님께 있습니다.
자세한 강의 내용은 신천수 교수님 강의를 참고하시면 좋을 것 같습니다.
😇 신천수 교수님 자료구조 강의