[자료구조]Queue(큐) & Deque(데큐)

Date: 2022.12.07 Updated: 2022.12.07

카테고리: DataStructure

1. Queue(큐)

1) 큐(Queue)의 정의

순차적 자료구조중 하나로, Stack과는 다르게 먼저 들어간 데이터가 먼저 나오는 자료구조이다.

FIFO(First In First Out)

큐를 사용하는 대표적인 예

은행의 대기표 시스템

2) 큐의 연산

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

3) Python Code

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

기본적으로

생성자 init
삽입 연산 enqueue
삭제 연산 dequeue
front

(1) 삽입 연산(enqueue)

원리는 stack과 동일하다. append를 하면 리스트의 마지막 자리로 요소가 추가된다.

(2) 삭제 연산(dequeue)

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

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

(3) front

front 연산은 dequeue를 했을 때, 실제 self.items의 value를 삭제하는 대신, self.front_index를 증가시킴으로써 dequeue한 값을 함수 상에서 얻는 값 취급을 했다. front연산은 삭제하지않고 리턴만하기 때문에 self.items[self.fornt_index]를 리턴해주기만 하면 된다.

2. 큐 사용의 예시

1) 요세푸스 문제

요세푸스 문제

전산학이나 수학에서 요세푸스 문제(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()

2) 원형 큐(Circular Queue)

배열로 구성된 선형 큐(Linear Queue)의 경우 데이터의 삽입/삭제 시 데이터들을 앞으로/뒤로 당겨주는 과정이 필요해 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이러한 선형 큐의 단점을 극복한 구조가 원형 큐이다.

(1) 멤버 변수 & 초기화

class CircularQueue:
  rear = 0
  front = 0
  MAX_SIZE = 100
  queue = list()
  
  def __init__(self):
    self.rear = 0
    self.front = 0
    self.queue = [ 0 for i in range(self.MAX_SIZE)

공백 상태

원형 큐가 비어져 있을때는 rear == front 이다.

포화 상태

앞에서 공백 상태를 front==rear로 구분하기 때문에 포화상태의 경우 한 칸이 비어있다. 따라서, 배열에 한 칸을 비움으로써 공백 상태와 포화 상태를 구분한다.

def is_Empty(self):
  if self.rear == self.front:
    return True
  return False
def is_full(self):
	if (self.rear+1)%self.MAX_SIZE == self.front:
    	return True
    return False

삽입 & 삭제

read에 삽입이 이루어지므로, front는 값이 변경이 없고 rear += 1을 하며 데이터를 삽입한다.
큐는 선입선출(FIFO) 구조로, 앞에서 삭제가 이루어져야 한다. 따라서 rear는 값의 변경이 없고 front += 1을 하며 데이터를 삭제한다.

def dequeue(self):
	if is_empty():
    	print("ERROR: EMPTY")
        return
    self.front = (self.front +1) % MAX_SIZE
    return self.queue[self.front]

def enqueue(self, x):
	if is_full():
    	print("ERROR: FULL")
        return
    self.rear = (self.rear+1)%(self.MAX_SIZE)
    self.queue[self.rear] = x
    
def queue_print(self): # 추가로 현재 큐에 저장된 데이터들을 출력
	i = self.front
    if is_empty():
    	print("EMPTY QUEUE")
        return
    while True:
    	i = (i+1)%self.MAX_SIZE
        print(self.queue[i], ' ')
        if i == self.rear or i != self.front:
        	break

3) Deque(데큐)

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

Stack + Queue
양쪽 가장자리에서 data를 넣거나 뺄 수 있다.
pushfront, pushback, popfront, popback

데큐의 종류와 특징

(1) 종류

스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱
셀프(self) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱 2) Dequeue의 특징
실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 없다.
보통 두가지 이유중 하나로 사용하게 됨. (입력과 출력을 추가하는 방식으로 사용)
큐에서 양쪽에서 출력할 수 있어야하거나 (스크롤, scroll) - 입력 제한
스택에서 양쪽에 입력하고 싶은경우 (셀프, self) - 출력 제한

데큐의 용도

(1)보통 스케줄링을 사용하게 됨

스케줄링이 복잡해질수록 큐와 스택보다 덱이 더 효율이 잘 나오는 경우가 있음 (2) 우선순위를 조절하게 될 때
ex) 옛날에 있던걸 우선순위를 높이기 위해서는 앞에서 빼낼 수 있어야 되는데 스택에서는 불가능함.
최근에 들어온걸 우선술위를 주고 싶은데 이 역시 큐의 구조에서는 불가능함
결국 앞뒤로 다 인출이 가능한 덱(Deque)만이 이 조건을 충족시킴

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

Reference

신찬수 교수님 강의 자료
원형 큐

Meaningful