Python 자료구조 5.1. 큐(QUEUE)

큐(QUEUE)

• 해당 자료구조의 구조와 동작 원리 이해
• 클래스 구현
• 덱 ( 원형 큐 상속) 구현
• 우선순위 큐 -> 전략적 미로 탐색 이해

큐의 기본
큐 자료구조는 입구와 출구가 따로 있는 원통 형태이다.
선입선출(First - In - First - Out : FIFO) -> 편의점 아르바이트나 술집 아르바이트 등 해본 사람이라면 알만한 구조!

큐의 원리
큐는 양쪽이 뚫려있는 구조다. 한쪽에서는 삽입(enQueue)만 진행, 다른 한쪽에서는 추출(deQueue)만 진행된다.
삽입되는 쪽은 rear, 삭제되는 쪽을 front아록 보통 칭한다.
즉, front에서는 첫 번째 데이터를 가리키고, rear에서는 마지막 데이터를 가리킨다.

큐 ADT

• 삽입과 삭제는 FIFO 순서를 따른다
• 삽입은 큐의 후단에서, 삭제는 전단에서 이루어진다.

Queue ADT
데이터 : 선입선출의 접근 방법을 유지하는 항목들의 모음
연산

• Queue(): 비어 있는 새로운 큐를 만든다.
• isEmpty(): 큐가 비어있으면 True를 아니면 False를 반환한다.
• enqueue(x): 항목 x를 큐의 맨 뒤에 추가한다.
• dequeue(): 큐의 맨 앞에 있는 항목을 꺼내 반환한다.
• peek(): 큐의 맨 앞에 있는 항목을 삭제하지 않고 반환한다.
• size(): 큐의 모든 항목들의 개수를 반환한다.
• clear(): 큐를 공백상태로 만든다.

큐의 구현

큐의 간단 구현

# 큐의 간단 구현
# 큐 생성
queue = [None] * 5
front = rear = -1 

rear += 1 
queue[rear] = '루니'
rear += 1
queue[rear] = '호날두'
rear += 1 
queue[rear] = '안데르송'
rear += 1
queue[rear] = '캐릭'

print('-----------큐 상태------------')
print('[출구] <--', end=' ')
for i in range(0,len(queue),1):
    print(queue[i], end=' ')
print('<--[입구]')

선형 큐의 문제!

1. 선형 큐는 비효율적이다.
   enqueue(item)의 삽입 연산은 -> O(1)
   dequeue()의 삭제 연산은 -> O(n)의 시간 복잡도
   이유는 앞에서 삭제할 때 마다 이동 연산이 필수!

2. 오버헤드 발생 문제

큐 작동을 위한 코드

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.items = []
    
    def isEmpty(self):
        return len(self.item) == 0
    
    def enqueue(self,item):
        self.items.append(item)
    
    def dequeue(self):
        if not isEmpty():
            self.items.pop(0)
    
    def peek(self):
        if self.items.isEmpty():
            print('큐가 비었습니다')
            return None
        return self.items[(self.front+1)]
    
    def size(self):
        return len(self.items)
    
    def clear(self):
        self.items=[]

원형 큐가 훨씬 효율적이다.

앞에서 다룬 큐는 한줄에 차례대로 데이터가 입출력되는 순차 큐이다.
이보다 좀 더 효율적인 원으로 구성된 원형 큐(Circular Queue)를 보겠다.
실제로 큐를 구현할 때는 순차 큐보다 원형 큐를 더 많이 사용한다.

• 원형 큐
  : 배열을 원형으로 사용한다.

• 전단과 후단을 위한 2개의 변수
  : front: 첫 요소 하나 앞 인덱스
  : rear : 마지막 요소 인덱스

• 회전 방법

1. 시계 방향

front = (front+1)% MAX_QSIZE
rear = (rear + 1)% MAX_QSIZE    

2. 반시계 방향

front = (front-1+MAX_QSIZE)% MAX_QSIZE
rear = (rear - 1 + MAZ_QSIZE)% MAX_QSIZE

• 공백상태와 포화상태

1. 공백상태

: front == rear

2. 포화상태

: front == (rear+1) % MAX_QSIZE

원형 큐의 구현

MAX_QSIZE = 10 # 원형 큐의 크기

class CircularQueue:
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.items [None] * MAX_QSIZE
    
    def isEmpty(self):
        return self.front == self.rear
    
    def isFull(self):
        return self.front == (self.rear+1)%MAX_QSIZE # 원형 큐의 포화상태
    
    def clear(self):
        self.front = self.rear
    
    def enqueue(self.item):
        if not self.isFull():
            self.rear = (self.rear+1) % MAX_QSIZE
            self.items[self.rear] = item
    
    def dequere(self):
        if not self.isEmpty():
            self.front = (self.front+1) % MAX_QSIZE
            return self.items[self.front]
        
    
    def peek(self):
        if not self.isEmpty():
            return self.items[(self.front+1)% MAX_QSIZE]
    
    def size(self):
        return (self.rear - self.front + MAX_QSIZE ) % MAX_QSIZE

파이썬의 queue 모듈

import queue
Q = queue.Queue(max_size =20)

for v in range(1,10):
    Q.put(v)
print("큐의 내용:" , end='')

for _ in range(1,10):
    print(Q.get(), end='')

print()