[Python 자료구조 #큐1] 선형 큐, 원형 큐, 너비우선탐색

* 큐(queue)

• 선입선출(First-In First Out: FIFO)의 자료구조이다.
• 실시간 비디오 스트리밍에서 다운로드 된 데이터가 비디오를 재생하기에 충분하지 않으면 큐에 순서대로 모아두었다가 충분한 양이 되었을 때 비디오를 복원하여 재생하는데 이것을 버퍼링(buffering)이라고 한다.

 

* 선형 큐

삭제 연산(pop)의 시간 복잡도는 O(n)이다. 비효율적이다. 삭제연산을 O(1)로 동작하도록 구현한 것이 원형 큐다.

items = [ ]	# 선형 큐

# 선형 큐 ADT(추상 자료형)
def isEmpty():	# 큐가 비어있는지 확인
    return len(items) == 0	

def enqueue(item):	# 항목 x를 큐의 맨 뒤에 추가한다.
    items.append(item)		

def dequeue():	# 큐의 맨 앞에 있는 항목을 꺼내 반환한다.
    if not isEmpty():		
        return items.pop(0)	

def peek():	# 큐의 맨 앞에 있는 항목을 삭제하지 않고 반환한다.
    if not isEmpty(): return items[0]

 

* 원형 큐( Circular Queue)

•  MAX_QSIZE로 크기를 고정한다.
• 공백상태는 front==rear이다. (반드시 0일 필요는 없다. 같은 곳을 가리키기만 하면 된다.)

 

출처 : 파이썬으로 쉽게 풀어쓴 자료구조

• 원형 큐에서는 포화상태를 표시하기 위해 아래 b와 같이 하나의 자리(front의 자리)를 비우는 전략을 취한다.
• front가 rear보다 하나 앞에 있으면 포화상태라고 정의한다. front == (rear +1)%MAX_QSIZE

출처 : 파이썬으로 쉽게 풀어쓴 자료구조

 

* 원형 큐의 ADT(추상 자료형) 구현

MAX_QSIZE = 10	# 10크기의 원형 큐를 가정한다.		    
class CircularQueue :
    def __init__( self ) :		
        self.front = 0			# front와 rear는 원형 큐의 시작과 끝을 알려주는 인덱스이다.
        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 ):	# 삽입. 포화상태에서 enqueue()가 호출되는 overflow의 예외처리 코드는 생략했다.
        if not self.isFull():			            
            self.rear = (self.rear+1)% MAX_QSIZE	
            self.items[self.rear] = item		    

    def dequeue( self ):	# 삭제. 마찬가지로 underflow의 예외처리 코드를 생략했다.
        if not self.isEmpty():			            
            self.front = (self.front+1)% MAX_QSIZE	
            return self.items[self.front]	# front는 리스트의 인덱스+1

    def peek( self ):	# 큐의 가장 앞에 있는 값을 확인할 수 있다.
        if not self.isEmpty():
            return self.items[(self.front + 1) % MAX_QSIZE]	# items[front]는 비어있다. 실제로 해당 리스트의 내용이 비어있는 것은 아니지만 개념적으로 비어있다.

    def size( self ) :	# 큐에 저장된 항목의 개수
       return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE

    def display( self ):	# front 다음 항목부터 rear 항목까지를 순서대로 출력
        out = []
        if self.front < self.rear :	# 슬라이싱 기능을 사용하기 위해서 두 경우로 나누어서 계산.
            out = self.items[self.front+1:self.rear+1]
        else:
            out = self.items[self.front+1:MAX_QSIZE] \
                + self.items[0:self.rear+1]		# +는 리스트를 합치는 연산이다.
        print("[f=%s,r=%d] ==> "%(self.front, self.rear), out)

q = CircularQueue()			       
for i in range(8): q.enqueue(i)		# 원형큐 q에 0~7까지의 값을 삽입
q.display()			            	
for i in range(5): q.dequeue();		# 원형큐 q에 5번의 dequeue 실행
q.display()
for i in range(8,14): q.enqueue(i)	# 원형큐 q에 8~13까지의 값을 삽입
q.display()

-------------------------------------------------

[f=0,r=8] ==>  [0, 1, 2, 3, 4, 5, 6, 7]
[f=5,r=8] ==>  [5, 6, 7]
[f=5,r=4] ==>  [5, 6, 7, 8, 9, 10, 11, 12, 13]

 

* 큐의 응용 : 너비우선탐색

출처 : 파이썬으로 쉽게 풀어쓴 자료구조

 

# from CircularQueue import*


def isValidPos(x, y):
    if x < 0 or y < 0 or x >= MAZE_SIZE or y >= MAZE_SIZE:
        return False
    else:
        return map[y][x] == "0" or map[y][x] == "x"


def BFS():
    que = CircularQueue()
    que.enqueue((0, 1))
    print("BFS: ")

    while not que.isEmpty():
        here = que.dequeue()
        print(here, end="->")
        x, y = here
        if map[y][x] == "x":
            return True
        else:	# 탐색 순서가 '상하좌우'이기에 위 사진에서의 순서로 미로를 탐색한다.
            map[y][x] = "."	# 지나간 자리 점으로 표시
            if isValidPos(x, y - 1):	# 상
                que.enqueue((x, y - 1))	
            if isValidPos(x, y + 1):	# 하
                que.enqueue((x, y + 1))
            if isValidPos(x - 1, y):	# 좌
                que.enqueue((x - 1, y))
            if isValidPos(x + 1, y):	# 우
                que.enqueue((x + 1, y))
    return False

미로 예제

map = [
    ["1", "1", "1", "1", "1", "1"],
    ["e", "0", "1", "0", "0", "1"],
    ["1", "0", "0", "0", "1", "1"],
    ["1", "0", "1", "0", "1", "1"],
    ["1", "0", "1", "0", "0", "x"],
    ["1", "1", "1", "1", "1", "1"],
]
MAZE_SIZE = 6
result = BFS()
if result:
    print(" --> 미로탐색 성공")
else:
    print(" --> 미로탐색 실패")

 

* 파이썬의 queue 모듈은 큐와 스택 클래스를 제공한다.

import queue	# queue 모듈을 포함해준다.

Q = queue.Queue(maxsize=20)	# queue 모듈의 큐 클래스 이름은 Queue이다. 
	# 생성될 큐의 최대 크기를 키워드 인수 maxsize를 통해 지정.

for v in range(1, 10):
    Q.put(v)	# 삽입은 enqueue()가 아니라 put()이고,
print("큐의 내용: ", end="")
for _ in range(1, 10):
    print(Q.get(), end=" ")	# 삭제는 dequeue()가 아니라 get()을 사용해야 한다.
print()

---------------------------------
BFS: 
(0, 1)->(1, 1)->(1, 2)->(1, 3)->(2, 2)->(1, 4)->(3, 2)->(3, 1)->(3, 3)->(4, 1)->(3, 4)->(4, 4)->(5, 4)-> --> 미로탐색 성공
큐의 내용: 1 2 3 4 5 6 7 8 9

get() 연산과 put()연산을 수행할 때 언더플로(underflow)와 오버플로(overflow)가 발생한다. get()과 put() 함수는 언더플로나 오버 플로가 발생하더라도 에러를 반환하지 않고, 단순히 무한루프에 빠지게 되는 것에 유의할 것. empty()와 full()를 이용해 큐의 상태를 먼저 확인하는 것이 안전하다.

 

스택 클래스도 큐 모듈에서 제공한다. 클래스의 이름이 LifoQueue이다. 

 

지금까지 스택이나 큐를 직접 구현한 것은 스택과 큐의 구조에 대한 이해를 위해서이다. 실제 스택과 큐를 사용할 때는 파이썬의 큐 모듈을 이용하면 된다.