[자료구조] Python - 큐(Queue)

1. 선입선출(FIFO: First-In First-Out)

가장 먼저 들어온 데이터가 가장 먼저 나가는 구조로 이루어져 있다. 

한 쪽 끝에서는 자료의 삽입 연산만 가능하고 반대쪽 끝에서는 삭제만 가능한 구조로서 선입선출의 특징을 가진다.

https://velog.io/@suitepotato/00004

 

 

위의 사진과 같이 앞(front)에서는 삭제만 일어나고, 뒤(rear)에서는 삽입만 일어난다.

실생활의 예시로는 은행 대기 줄, 에스컬레이터, 작업 큐, 프린터 인쇄 처리 방식 등이 있다.

 

2. 큐의 연산

• enqueue(e): 큐의 가장 뒤에 데이터를 삽입
• dequeue(): 큐의 가장 앞에 데이터를 제거
• isEmpty(): 큐가 비어 있는 경우 True를 반환, 아니면 False를 반환
• isFull(): 현재 큐가 가득 차 있는 경우 True를 반환, 아니면 False를 반환
• peek(): 큐의 가장 앞에 있는 데이터를 반환
• size(): 큐에 들어 있는 전체 요소의 수를 반환

3. 큐의 종류

1) 선형 큐(배열을 사용)

선형 큐는 배열을 선형으로 나타낸 형태이다.

자료의 삽입이나 삭제가 용이하나 큐에 빈 자리가 있어도 포화 상태로 인식하는 경우가 있어 빈 자리를 따로 정리 과정을 거쳐야 한다는 단점이 있다.

 

2) 원형 큐(연결리스트를 사용)

배열을 원형의 모습으로 표현한 것으로 논리적으로 배열의 처음과 끝을 연결한 형태이다.

자리를 이동시킬 필요가 없어 실용적인 특징을 가지고 있다.

원형 큐에서는 초기 공백 상태에서 front와 rear의 값을 0으로 하고 공백 상태와 포화 상태를 구분하기 위해 자리를 비워둔다.

자료를 삽일할 경우 rear의 위치를 한 칸 앞으로 옮기고 그곳에 자료를 삽입한다.

따라서 front가 지정하는 위치는 항상 비워진 상태로 유지된다.

• 실제로 배열이 원형이 되는 것이 아니라 인덱스 front와 rear를 원형으로 회전시키는 개념
• 시계 방향의 회전: front나 rear가 계속 증가하다가 용량(capacity)과 같아지면 0으로 만들어줌 
• front 회전 : front <- (front + 1) % capacity
• rear 회전 : rear <- (rear + 1) % capacity

3. 원형 큐의 구현

class ArrayQueue:
    def __init__(self, capacity=10) : # capacity 인수 주어지면 그 값을 사용하고 주어지지 않으며 기본값인 10을 사용
        self.capacity = capacity
        self.array = [None] * capacity
        self.front = 0
        self.rear = 0 

    # 공백 상태와 포화 상태 검사
    def isEmpty(self):
        return self.front == self.rear
    
    def isFull(self):
        return self.front == (self.rear+1)%self.capacity
    
    # 삽입 연산
    def enqueue(self, item):
        if not self.isFull():
            self.rear = (self.rear+1) % self.capacity
            self.array[self.rear] = item
        else:
            print("Queue Overflow: Cannot add more elements.")
            return
        
     # 삭제 연산
    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1) % self.capacity
            return self.array[self.front]
        else:
            print("Queue Underflow: Cannot remove elements from an empty queue.")
            return
        
    # 큐의 첫 번째 요소 반환 (제거하지 않음)
    def peek(self):
        if not self.isEmpty():
            return self.array[(self.front+1) % self.capacity]
        else:
            print("Queue is empty: No element to peek.")
            return None
        
    # 전체 요소의 수 
    def size(self):
        return(self.rear - self.front + self.capacity) % self.capacity
    
    # 전체 요소를 화면으로 출력 
    def display(self, msg):
        print(msg, end='= [')
        for i in range(self.front+1, self.front+1+self.size()):
            print(self.array[i%self.capacity], end=' ')
        print("]")

# 테스트 프로그램
import random
if __name__ == "__main__":
    q = ArrayQueue(8)

    q.display("초기 상태")
    while not q.isFull():
        q.enqueue(random.randint(0, 100))
    q.display("포화 상태")

    print("삭제 순서: ", end='')
    while not q.isEmpty():
        print(q.dequeue(), end=' ')
    print()

 

4. 원형 큐를 링버퍼로 사용하기

가장 오래된 데이터를 삭제하고 새로운 데이트를 계속 저장하며, 큐를 계속 포화상태로 유지하는 것

class ArrayQueue:
    def __init__(self, capacity=10) : # capacity 인수 주어지면 그 값을 사용하고 주어지지 않으며 기본값인 10을 사용
        self.capacity = capacity
        self.array = [None] * capacity
        self.front = 0
        self.rear = 0 

    # 공백 상태와 포화 상태 검사
    def isEmpty(self):
        return self.front == self.rear
    
    def isFull(self):
        return self.front == (self.rear+1)%self.capacity
    
    # 삽입 연산
    def enqueue(self, item):
        if not self.isFull():
            self.rear = (self.rear+1) % self.capacity
            self.array[self.rear] = item
        else:
            print("Queue Overflow: Cannot add more elements.")
            return
        
     # 삭제 연산
    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1) % self.capacity
            return self.array[self.front]
        else:
            print("Queue Underflow: Cannot remove elements from an empty queue.")
            return
        
    # 큐의 첫 번째 요소 반환 (제거하지 않음)
    def peek(self):
        if not self.isEmpty():
            return self.array[(self.front+1) % self.capacity]
        else:
            print("Queue is empty: No element to peek.")
            return None
        
    # 전체 요소의 수 
    def size(self):
        return(self.rear - self.front + self.capacity) % self.capacity
    
    # 전체 요소를 화면으로 출력 
    def display(self, msg):
        print(msg, end='= [')
        for i in range(self.front+1, self.front+1+self.size()):
            print(self.array[i%self.capacity], end=' ')
        print("]")

    # 원형 큐: 링 버퍼를 위한 삽입 연산
    def enqueue2(self, item):
        self.rear = (self.rear+1)%self.capacity
        self.array[self.rear] = item
        if self.isEmpty():              # front == rear
            self.front = (self.front+1) % self.capacity

# 링 버퍼의 테스트 프로그램
import random
if __name__ == "__main__":
    q = ArrayQueue(8)               # 큐 객체를 생성(capacity=8)

    q.display("초기 상태")
    for i in range(6) :             # enqueue2(): 0, 1, 2, 3, 4, 5
        q.enqueue2(i)
    q.display("삽입 0-5")

    q.enqueue2(6); q.enqueue2(7)    # enqueue2(): 6, 7
    q.display("삽입 6,7")

    q.enqueue2(8); q.enqueue2(9)    # enqueue2(): 8, 9
    q.display("삽입 8,9")

    q.dequeue(); q.dequeue()        # dequeue() 2회
    q.display("삭제  x2")

 

5. 덱(deque, double-ended queue)

https://velog.io/@9e0na/자료구조-덱DEQUE

 

전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐 

덱은 스택과 큐의 연산을 모두 가지고 있다. 

• 덱의 구현도 원형 큐아 비슷하게 원형 덱(circular deque)으로 구현하는 것이 좋다. 
• 반시계 방향 회전: 인덱스를 하나씩 줄여야 함
• 주의해야 할 연산: deleteRear, addFront
• front 회전(반시계 방향) : front <- (front -1 + capacity) % capacity
• rear 회전(반시계 방향) : rear <- (rear -1 + capacity) % capacity

6. 덱의 연산

• addFront(e): 새로운 요소를 front에 추가
• addRear(e): 새로운 요소를 rear에 추가
• deleteFront(): 덱의 front를 꺼내서 반환 
• deleteRear(): 덱의 rear를 꺼내서 반환
• getFront(): 덱의 front를 삭제하지 않고 반환
• getRear(): 덱은 rear를 삭제하지 않고 반환
• isEmpty(): 덱이 비어 있는 경우 True를 반환, 아니면 False를 반환
• isFull(): 덱이 가득 차 있는 경우 True를 반환, 아니면 False를 반환
• size(): 큐에 들어 있는 전체 요소의 수를 반환

6. 덱의 구현

1) 큐와 알고리즘이 동일한 연산

• addRear(), deleteFront(), getFront() = 큐의 enqueue, dequeue, peek 연산과 동일 
• 덱의 후단을 스택의 상단으로 사용하면, addRear(), deleteRear(), getRear()
  = 스택의 push, pop, peek 연산과 동일

2) 큐와 데이터가 동일하고 연산도 유사함 

3) 새로 추가해야 되는 연산: addFront(e), deleteRear(), getRear()

 

따라서 원형 큐를 상속해서 원형 덱을 구현한다.

from ArrayQueue import *

class CircularDeque(ArrayQueue):
    def __init__(self, capacity=10):
        super().__init__(capacity)

    # 원형 덱: 동작이 동일한 연산들
    def addRear( self, item ): self.enqueue(item )
    def deleteFront( self ): return self.dequeue()
    def getFront( self ): return self.peek()

    # 원형 덱: 추가된 연산 
    def addFront(self, item):
        if not self.isFull():
            self.array[self.front] = item
            self.front = (self.front-1+self.capacity) % self.capacity
        else: 
            print("Deque Overflow: Cannot add more elements at the front.")
            return

    def deleteRear(self):
        if not self.isEmpty():
            item = self.array[self.rear]
            self.rear = (self.rear-1+self.capacity) % self.capacity
            return item
        else: 
            print("Deque Underflow: Cannot remove elements from an empty deque.")
            return None
        
    def getRear(self):
        if not self.isEmpty():
            return self.array[self.rear]
        else:
            print("Deque is empty: No element at the rear.")
            return None
        
# 코드 2.5: 원형 덱: 테스트 프로그램
if __name__ == "__main__":
    dq = CircularDeque()

    for i in range(9):
        if i%2==0 : dq.addRear(i)
        else : dq.addFront(i)
    dq.display("홀수는 전단 짝수는 후단 삽입")

    for i in range(2): dq.deleteFront()
    for i in range(3): dq.deleteRear()
    dq.display("전단 삭제 2번, 후단 삭제 3번")

    for i in range(9,14): dq.addFront(i)
    dq.display("전단에 9 ~ 13 삽입")

 

6. 파이썬에서 큐와 덱 사용하기

파이썬 리스트는 스택으로 사용하기는 충분하지만, 원형 큐나 덱으로 직접 사용하기에는 적절하지 않다.

따라서 파이썬에서 제공하는 모듈을 사용하기.

 

💡 queue 모듈의 Queue 사용하기 

 

queue 모듈은 스택과 함께 큐를 제공한다. 

import queue			# 파이썬의 queue 모듈 포함
q = queue.Queue(maxsize = 20)	# 큐 객체 생성(최대크기 20)

 

ArrayQueue ➡️ queue.Queue 연산

• 삽입/삭제: enqueue(), dequeue() ➡️ put(), get()
• 공백/포화 상태 검사: isEmpty(), isFull()➡️ empty(), full()
• 전단 들여다보기: peek() ➡️  제공하지 않음 

💡 collections 모듈의 deque 클래스 사용하기 

import collections		# 파이썬의 collections 모듈 포함
dq = collections.deque()	# 용량이 무한대인 덱 객체 생성

 

CircularDeque ➡️ collections.deque 연산

• 전단 삽입/삭제: addFront(), deleteFront() ➡️ appendleft(), popleft()
• 후단 삽입/삭제: addRear(), deleteRear() ➡️ append(), pop()
• 공백 상태 검사: isEmpty() ➡️ dq ( 예: if dq: ...)
• 포화 상태 검사: isFull()➡️ 의미 없음
• 들여다보기: getFront(), getRear() ➡️  제공하지 않음