알고리즘 - 큐(queue)

큐는 스택과 같이 데이터를 임시 저장하는 자료구조입니다.

스택과 다른점은 스택은 마지막에 넣은 데이터가 먼저 나오지만 큐는 먼저 넣은 데이터가 먼저 나옵니다.

 

큐에 데이터를 추가하는 작업은 enqueue, 데이터를 꺼내는 작업은 dequeue라고 합니다.

또한 맨 앞의 원소를 front, 맨 끝의 원소를 rear라고 합니다.

 

 

 

위 큐에서 115를 빼면 나머지 위 숫자들은 한칸씩 앞으로 당겨져야 합니다.

그렇게 되면 시간 복잡도 O(n)이 되고 데이터를 꺼낼 때마다 이렇게 처리하면 효율성이 떨어지게 됩니다.

이럴 때 사용하는 자료구조가 ring buffer입니다.

 

링 버퍼

 

왼쪽이 링버퍼고 오른쪽은 링 버퍼를 펼쳐 놓은 상태입니다.

6번 인덱스가 맨 앞이고, 2번 인덱스가 맨 뒤인 상태입니다.

 

24 추가

 

링버퍼에 24가 추가되면 2번 인덱스에 24가 들어가고 rear값은 1 증가해서 3이 됩니다.

 

41 제거

 

6번 인덱스에서 41를 빼면 front 값은 1이 증가한 7이 됩니다.

 

이렇게 원소의 자리를 옮기지 않고 front, rear값만 움직여서 enqueue와 dequeue를 할 수 있습니다.

 

---

fixed_queue.py

from typing import Any

class FixedQueue:

    class Empty(Exception):
        pass

    class Full(Exception):
        pass

    def __init__(self, capacity: int) -> None:
        self.no = 0     # 데이터의 개수
        self.front = 0  # 맨 앞 원소 커서
        self.rear = 0   # 맨 뒤 원소 커서
        self.capacity = capacity # 큐의 크기
        self.que = [None] * capacity  # 큐

    def __len__(self) -> int:
        return self.no

    def is_empty(self) -> bool:
        return self.no <= 0

    def is_full(self) -> bool:
        return self.no >= self.capacity

 

    def enque(self, value) -> None:	# 데이터를 넣음
        if self.is_full():
            raise FixedQueue.Full
        self.que[self.rear] = value
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:
            self.rear = 0

    def deque(self) -> Any:	# 데이터를 꺼냄
        if self.is_empty():
            raise FixedQueue.Empty
        value = self.que[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return value

 

enque와 deque에서 rear와 front를 0으로 초기화 시키는 부분이 있는데 

큐의 크기와 처음 혹은 끝 값이 같아지면 다음 원소가 들어갈 부분은 0이기 때문입니다.

 

    def peek(self) -> Any:
        if self.is_empty():
            raise FixedQueue.Empty
        return self.que[self.front]

    def find(self, value: Any) -> Any:
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value:
                return idx
            return -1

 

먼저 peek 부분이 스택과 다른데 스택에서는 다음으로 꺼낼 값이 가장 마지막에 있는 데이터입니다.

하지만, 큐에서는 다음으로 꺼낼 값이 가장 앞에 있는 데이터이기 때문에 front값을 봅니다.

 

find에서 인덱스를 구할 때 (i + self.front)를 하는 이유는

예를 들어, 현재 가장 앞에 있는 데이터의 인덱스가 5이면 (i = 0) + (front = 5)를 해야지 첫 값이 나오고

두 번째 값은 (i = 1) + (front = 5) 이렇게 해야 나오기 때문입니다.

그리고 self.capacity로 나누고 나머지 값을 넣는 이유는 i와 front 값의 합이 capacity값 보다 같거나

커지기 때문입니다.

 

    def count(self, value: Any) -> Any:	# 큐에 있는 value의 개수
        c = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value:
                c += 1
        return c

    def __contains__(self, value: Any) -> bool:	# 큐에 value가 있는지 확인
        return self.count(value)

    def clear(self):	# 큐의 모든 데이터를 비움
        self.no = self.front = self.rear = 0

    def dump(self) -> None:
        if self.is_empty():
            print('큐가 비어있습니다.')
        else:
            for i in range(self.no):
                print(self.que[(i + self.front) % self.capacity], end='')
                print()

 

---

fixed_queue_test.py

from enum import Enum
from fixed_queue import FixedQueue

Menu = Enum('Menu', ['enque', 'deque', 'peek', 'find', 'dump', 'exit'])


def select_menu():
    string = [f'({m.value}) {m.name}' for m in Menu]
    while True:
        print(*string, sep='  ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)


q = FixedQueue(64)

while True:
    print('ㅡ' * 20)
    print(f'현재 데이터의 개수: {len(q)} / {q.capacity}')
    menu = select_menu()

    if menu == Menu.enque:
        value = int(input('넣을 데이터를 입력하세요.: '))
        try:
            q.enque(value)
        except FixedQueue.Full:
            print('큐가 가득 차있습니다.')

    elif menu == Menu.deque:
        try:
            x = q.deque()
            print(f'꺼낸 데이터는 {x}입니다.')
        except FixedQueue.Empty:
            print('큐가 비어있습니다.')

    elif menu == Menu.peek:
        try:
            x = q.peek()
            print(f'가장 앞 데이터는 {x}입니다.')
        except FixedQueue.Empty:
            print('큐가 비어있습니다.')

    elif menu == Menu.find:
        value = int(input('검색할 데이터를 입력하세요.: '))
        if value in q:
            print(f'{q.count(value)}개 있고, 맨 앞 위치는 {q.find(value)}입니다.')
        else:
            print('검색값이 없습니다.')

    elif menu == Menu.dump:
        q.dump()

    else:
        break

 

---

결과

 

enque, find

 

enque와 find 결과 입니다.

 

 

peek, deque

 

peek, deque 결과입니다.