자료구조 - 큐(Queue), 데크(Deque)

1. 큐(Queue)

---

1) 개념

- FIFO(First In First Out) 방식 : 은행의 번호표를 생각하면 된다. 먼저 온 데이터가 먼저 나간다. 

 

- 삽입(insert) : 스택에서의 삽입을 push라고 부른다면 큐에서는 enqueue라고 부른다. 

- 삭제(delete) : 큐에서는 dequeue라고 부른다.(데크(deque)와 용어가 똑같지만 큐에서는 삭제를 의미)

-  enqueue는 value를 큐의 오른쪽에 삽입하고 deque는 가장 왼쪽 값을 삭제 후 리턴한다. 

- 스택에서는 가장 top의 값과 index가 무엇인지 알아야했던 것과 달리 큐에서는 enqueue를 할 땐, 큐가 현재 어디까지 차 있는지의 index를 알아야 하고 deque를 할 땐 가장 밑에 있는 index(가장 먼저 들어온 값의 index)가 무엇인지를 알아야한다. 즉 큐에서는 삽입과 삭제 연산을 위해 알아야 할 index가 더 많다.

 

2) 클래스

이제 큐의 개념에 따라 클래스를 정의해보자. 

enqueue는 파이썬 list의 append를 활용할 것이고, dequeue에는 dequeue가 될 곳의 index를 관리하는 front index라는 변수가 필요하다. list의 pop함수를 사용하여 pop[0]을 하는 방법도 있지만 이 경우, list 맨 앞의 값이 pop되면 뒤에 있는 모든 값을 앞으로 한칸씩 당겨와야하므로 시간복잡도가 O(n)이 된다. 시간복잡도가 O(1)이 될 수 있도록 front_index라는 변수를 활용해 실질적으로 list에 값이 삭제된 건 아니고 front_index부터 Queue의 값을 읽을 수 있게 한 것이다.

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

    def enqueue(self,val):
        self.items.append(val)
        pass
    def len(self):
        return len(self.items)-self.front_index

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

    def dequeue(self):
        if self.front_index == len(self.items):
            print("Queue is empty")
            return None
        else: 
            x = self.items[self.front_index]
            self.front_index += 1
            return x
            
    def front(self):
        if self.isEmpty():
            print("There is no element in Queue")
            return None
        else:
            return self.items[self.front_index]

강의에서 교수님이 설명해주신대로 enqueue와 dequeue를 Queue Class를 구현해보았다. len 함수를 따로 정의하지 않자 Josephus를 해결할 때, 큐의 len를 계산할 수 없다고 오류가 떠서 len와 isEmpty, front함수까지 코드를 작성해봤다. 

 

cf. dequeue함수의 if문에 isEmpty를 활용해도 코드가 깔끔할 것 같다.

 

 

 

3) Josephus game

def Josephus(n,k):
    Q = Queue()
    for i in range(1,n+1):
        Q.enqueue(i)
    while Q.len() > 1:
        for i in range(1,k):
            Q.enqueue(Q.dequeue())
        Q.dequeue()
    return Q.dequeue()

위에서 구현한 Queue 클래스를 이용해 Josephus Game 문제를 해결하는 함수를 작성해봤다. 

이 문제의 해답으로 가장 효율적인 방법은 아니지만 Queue를 활용해 해결할 수 있는 대표적인 문제라고 해서 위와 같이 코드로 해결해봤다. 

Josephus(6,3)을 실행했을 때 진행과정은 아래 그림과 같다.

 

 

 

 

2. 덱(Deque)

---

1) 개념

- Stack과 Queue를 합친 새로운 자료구조

- 왼쪽과 오른쪽에서 모두 삽입, 삭제 가능

- Python에서는 collections라는 모듈에 deque란 클래스로 이미 덱이 구현되어 있음.

- 오른쪽 push = append, 왼쪽 push = appendleft

- 오른쪽 pop = pop , 왼쪽 pop = popleft

 

 

2) Palindrome 검사 코드 

- 왼쪽부터 읽어도, 오른쪽으로 읽어도 같은 문자열인지 검사하는 문제이다.

- 문자열 함수나, 반복문을 활용한 방법도 있지만 덱을 활용해서 해결해보자. 

deque에 문자열을 저장한 후 양쪽에서 하나씩 빼면서 같은지 비교하고 다르다면 palindrome이 아님을 출력하면 된다.

 

from collections import deque
def check_palindrome(s):
    dq = deque(s)
    palindrome = True
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            palindrome = False
        return palindrome

위 함수를 사용해 아래와 같이 'rear'이라는 문자열을 입력해보면 'True'값이 출력되는 것을 확인할 수 있다.

---

 

본 게시글은 한국외국어대학교 컴전학부의 신찬수 교수님의 유튜브 강의를 보고 학습한 내용을 작성한 학습기록입니다.

 

자료구조 과목 소개 - YouTube