큐 (queue)

출처:  Do it! 자료구조와 함께 배우는 알고리즘 입문- 파이썬편

 

큐는 스택과 같이 데이터를 임시 저장하는 자료구조이지만, 스택처럼 가장 나중에 넣은 데이터를 가장 먼저 꺼내지 않는다. 선입선출(가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조)이다. 

https://velog.io/@hyhy9501/3-1.-%ED%81%90Queue

인큐(enqueue) : 큐에 데이터 추가

디큐(dequeue):  데이터를 꺼냄

프런트(front):  데이터를 꺼내는 쪽

리어(rear):  데이터를 넣는 쪽 

링 버퍼로 큐 구현하기

링 버퍼 ring buffer는 디큐할 때 배열의 원소를 옮기지 않는 큐이다. 

직접 만들어서 허접 주의..

front 값은 5, rear 값은 2이다.

여기서 82를 인큐하면 맨끝의 다음에 위치한 que[rear]= que[2]에 82를 저장하고 rear 값을 2에서 3으로 움직인다. 

24를 디큐 하면 맨 앞 원소인 que[5]인 값 24 값을 꺼내고 front 값을 1증가시켜 6으로 만든다.

 

 

from typing import Any
class FixedQueue:
  class Empty(Exception):
    #비어있는 FixedQueue에서 디큐 또는 피크할때 내보내는 예외 처리
    pass

  class Full(Exception):
    #가득차 있는 FixedQueue에서 인큐할 때 내보내는 예외처리
    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

Empty: 비어있는 큐에 deque(), peek() 함수를 호출할 때 내보내는 예외처리 클래스

Full: 가득차 있는 큐에 enque() 함수를 호출할 때 내보내는 예외 처리 클래스 

__init__: 초기화 함수

• que:  큐의 배열로서 밀어넣는 데이터를 저장하는 list 배열
• capacity: 큐의 최대크기를 나타내는 int형 정수, 배열 que의 원소수와 일치
• front, rear: 맨앞, 맨 끝 원소를 나태는 인덱스, 가장 처음에 넣은 것(맨 앞 원소) -> front, 가장 나중에 넣은것(맨 뒤 원소의 다음 인덱스)-> rear
• no: 큐에 쌓여있는 데이터 갯수를 나타내는 int형 정수, 비어있으면 0, 가득차 있으면 capacity와 같은 값이다.

__len__:  추가한 데이터 개수 반환, no값 그대로 반환

is_empty():  큐가 비어있는지 판단, 비어 있으면 True, 아니면 False 반환

is_full() 큐가 가득차 있는지 판단, 가득차 있으면 True, 아니면 False

enque()

  def enque(self,x:Any)-> None:
    #데이터x를 인큐
    if self.is_full():
      raise FixedQueue.Full # 큐가 가득차 있는 경우 예외처리 발생
    self.que[self.rear]=x
    self.rear += 1
    self.no +=1
    if self.rear== self.capacity:
      self.rear=0

a) 82를 인큐할때 -> que[rear]인 que[2]에 인큐하는 데이터를 저장하고 rear과 no의 값을 1 증가시킨다. 

b) 17를 인큐->  인큐를 하기전 rear 값이 배열의 맨끝인 경우에는 rear를 1증가시키면 capacity값을 넘어선다. 

rear에 1을 증가시킨 뒤 rear값이 큐의 capacity 크기와 같은 경우, rear을 맨 앞 인덱스 0으로 되돌린다. 

deque()

  def deque(self,x:Any)->None:
    #데이터를 디큐
    if self.is_empty():
      raise FixedQueue.Empty #큐가 비어있는 경우 예외처리
    x= self.que[self.front]
    self.front +=1
    self.no -=1
    if self.front == self.capacity:
      self.front=0

    return x

 

a)  14를 디큐했을때 ->  인덱스 5에 위치한 14를 빼면 front 1증가, no는 1 감소

b)17을 디큐->  디큐하기전에 front가 배열의 맨끝인 경우, front를 1증가 시키면 그 값이 capacity와 같아져서 배열 인덱스를 넘는다. 이럴 경우 front를 1 증가시키기고 front값을 0으로 되돌린다. 

peek() 함수

  def peek(self)-> Any:
    #큐에서 데이터를 피크(맨 앞 데이터를 들여다봄)
    if self.is_empty():
      raise FixedQueue.Empty #큐가 비어있는 경우 예외 처리 발생
    return self.que[self.front]

peek는 다음 디큐에서 꺼낼 데이터를 들여다봄. que[front] 값을 반환할 뿐 데이터를 꺼내지는 않음. 비어있을 때는 FixedQueue.Empty를 내보냄

 

find()함수

  def find(self,value:Any)-> Any:
    #큐에서 value를 찾아 인덱스를 반환(없으면-1 반환)
    for i in range(self.no):
      idx= (i+self.front) % self.capacity
      if self.que[idx]== value: 
        return idx #검색 성공
    return -1 #검색 실패

큐의 배열에서 value와 같은 데이터가 포함되어 있는 위치를 알아냄. 스캔은 큐의 맨 앞 원소(front)부터 시작함. 스캔할 때 주목하는 인덱스 idx를 구하는 식은(i+front) % capacity로 구한다. 

여기서 capacity는 8,  front는 5이므로 (i+5)/8 한값의 나머지를 구하면, 다음과 같이 idx값이 나온다. 

i	0	1	2	3	4
idx	5	6	7	0	1

검색에 성공하면 찾은 원소의 인덱스를 반환하고, 실패하면 -1을 반환한다. 

 

count() 함수

큐에있는 데이터(value)의 갯수를 구하여 반환

  def count(self,value:Any)-> bool:
    #큐에서 value의 갯수 반환
    c= 0
    for i in range(self.no): #큐 데이터를 선형 검색
      idx= (i+self.front) % self.capacity
      if self.que[idx]== value: #검색 성공
        c += 1 #들어 있음
    return c

 

__contains__()함수

 큐에 데이터(value)가 있는지 판단한다. 들어있으면 True, 없으면 False를 반환한다. 내부의 count() 함수를 호출한다.

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

 

clear() 함수

큐에 들어있는 모든 데이터 삭제

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

 

dump() 함수

큐에 들어있는 모든 데이터를 맨 앞부터 맨 끝쪽으로 순서대로 출력, 큐가 비어있으면 '큐가 비어있습니다' 출력

  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()

 

양방향 대기열 덱(deque)

맨 앞과 맨 끝 양쪽에서 데이터를 넣고 꺼낼 수 있는 자료구조이다.

파이썬에서는 collections.deque 컨테이너로 제공된다.

맨 앞과 맨 끝 양쪽에서 데이터를 모두 삽입, 삭제할 수 있는 자료구조로, 2개의 포인터를 사용하여 양쪽에서 삽입, 삭제가 가능하며 큐와 스택을 합친 형태이다.

 

링 버퍼의 활용

만약 데이터를 12개를 받고, 배열에는 최근에 입력한 10개만 남을수 있게 하는 코드, 노란색 부분 버림:

ex) 14, 13, 12, 15 13, 32, 46, 65, 32,23, 55, 30

n = int(input('정수를 몇 개 저장할까요?:'))
a = [None] * n #입력받은 값을 저장하는 배열

cnt = 0 #정수를 입력받은 개수
while True:
  a[cnt % n] = int(input((f'{cnt+1}번쨰 정수를 입력하세요:')))
  cnt += 1

  retry = input(f'계속 할까요?(Y .. Yes/N...No): ')
  if retry in {'N','n'}: #N이나 n을 입력하면 더 이상 값을 받지 않음
    break

i = cnt-n
if i<0:i=0

while i < cnt:
  print(f'{i+1}번쨰 = {a[i%n]}')
  i +=1