원형큐, 큐, 덱 [백준 10866, 18258]

연관문제

https://www.acmicpc.net/problem/10866

https://www.acmicpc.net/problem/18258

 

큐

큐는 선입선출(FIFO: First In, First Out) 방식으로 작동하는 자료구조 이다.

front, rear 이렇게 두 포인터로 관리 하되, front는 삭제(출력), rear는 삽입(입력)만 담당한다.

enqueue(삽입), dequeue(삭제), is_full, is_empty, len 등을 제공한다.

 

아래 그림과 같이 F,R 포인터를 따로 두어 삽입과 삭제를 관리하며, F,R 이 같은 위치인지 아닌지에 따라 비어있는지를 체크한다.

 

큐가 차고 비워지는 순서

 

 

그런데, 단점이.. 배열로 큐를 구현시 삽입과 삭제를 반복하다보면 갈 F와R이 0이 아니라 리스트 맨 끝에 있음에도 불구하고 큐가 비어버리며, 공간을 낭비하게 되는데 이를 해결하기 위해 원형큐를 사용한다.

 

원형 큐

원형 큐는 큐의 변형으로, 배열의 처음과 끝이 연결된 구조를 가진다.

배열이 꽉 차더래도 포인터를 이동시켜서 메모리의 효율적인 사용이 가능하다.

 

enque

rear를 움직이고, 그 자리에 값을 넣는다. 이때, 모듈러 연산을 이용하여 배열 크기와 넘치지 않게 한다.

def enque(self, val):
        if(self.is_full()): raise Exception('가득 차 있습니다')
        self.back = (self.back + 1) % self.size
        self.arr[self.back] = val

원형 큐가 차는 순서

deque

front를 움직이고, 그 움직인 자리를 비워준다. 이 때 enque와 마찬가지로 모듈러 연산을 이용하여 배열 사이즈를 넘지 않게 한다.

def deque(self):
        if(self.is_empty()): raise Exception('비어 있습니다')
        self.front = (self.front + 1) % self.size
        val = self.arr[self.front]
        self.arr[self.front] = None
        return val

원형 큐가 비워지는 순서

 

is_full, is_empty

que가 비어있음을 확실히 하기 위해 front, rear가 같으면 비어있다고 보고, rear가 front 직전에 있으면 큐가 꽉 찬 상태로 본다.

이 때, 서로 충돌 나는 일이 없게끔 enque deque 시에 미리 확인하고 다음 작업에 들어가도록 한다.

원형 큐가 꽉 찼을 때

전체 소스

class MyQueue():
    def __init__(self):
        self.arr = []
        self.size = 1000000
        self.front = 0
        self.back = 0
        self.arr = [None for _ in range(self.size)]

    def is_full(self):
        return self.front == (self.back + 1) % self.size
    
    def is_empty(self):
        return self.front == self.back
    
    def enque(self, val):
        if(self.is_full()): raise Exception('가득 차 있습니다')
        self.back = (self.back + 1) % self.size
        self.arr[self.back] = val

    def deque(self):
        if(self.is_empty()): raise Exception('비어 있습니다')
        self.front = (self.front + 1) % self.size
        val = self.arr[self.front]
        self.arr[self.front] = None
        return val
    
    def peek(self):
        if(self.is_empty()): raise Exception('비어 있습니다')
        temp = (self.front + 1) % self.size
        val = self.arr[temp]
        return val
    
    def len(self):
        return abs(self.front - self.back)

 

 

덱

덱은 양쪽 끝에서 삽입과 삭제가 가능한 큐 이다. 

처음에 이걸 구현할 때 이해를 잘 못한 것들이 있는데, 그림으로 덱의 삽입 및 삭제 과정을 보도록 하자
일단 덱이든, 큐든 값이 들어있는 공간은 빈칸 없이 연속적으로 들어가 있어야 한다.

 

rear 에서 증가

일반 큐와 같이 먼저 포인터 이동후 값을 넣어준다.

front 에서 증가

일반 큐와 같이 먼저 포인터 이동후 값을 넣어주면 안된다. 이렇게 하면 중간에 비는 부분이 생기게 된다.

값을 먼저 넣고 포인터 이동 후 나중에 참조할 때 현 위치의 -1 을 바라보게 한다.

 

 

 

전체 소스

class MyDeque():
    def __init__(self):
        self.arr = []
        self.size = 1000000
        self._front = 0
        self._back = 0
        self.len = 0
        self.arr = [None for _ in range(self.size)]

    def is_full(self):
        return self.len >= self.size - 1
    
    def is_empty(self):
        return self.len == 0
    
    def push_front(self,val):
        #삽입 후 이동 (중요)
        if(self.is_full()): 
            return
        self.arr[self._front] = val
        self._front = (self._front - 1) % self.size
        self.len += 1
    
    def pop_front(self):
        #이전 위치 참조 (중요)
        if(self.is_empty()): 
            return -1
        self._front = (self._front + 1) % self.size
        val = self.arr[self._front]
        self.arr[self._front] = None
        self.len -= 1
        return val

    def front(self):
        #이전 위치 참조 (중요)
        if(self.is_empty()): 
            return -1
        front = (self._front + 1) % self.size
        val = self.arr[front]
        return val
    
    def push_back(self,val):
        #이동 후 삽입
        if(self.is_full()): 
            return
        self._back = (self._back + 1) % self.size
        self.arr[self._back] = val
        self.len += 1

    def pop_back(self):
        #참조 후 반환
        if(self.is_empty()): 
            return -1
        val = self.arr[self._back]
        self.arr[self._back] = None
        self._back = (self._back - 1) % self.size
        self.len -= 1
        return val
    
    def back(self):
        #참조 후 반환
        if(self.is_empty()): 
            return -1
        val = self.arr[self._back]
        return val