Programming 기초/Python
[Python 자료구조 #큐1] 선형 큐, 원형 큐, 너비우선탐색
코딩상륙작전
2023. 5. 10. 23:55
* 큐(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 9get() 연산과 put()연산을 수행할 때 언더플로(underflow)와 오버플로(overflow)가 발생한다. get()과 put() 함수는 언더플로나 오버 플로가 발생하더라도 에러를 반환하지 않고, 단순히 무한루프에 빠지게 되는 것에 유의할 것. empty()와 full()를 이용해 큐의 상태를 먼저 확인하는 것이 안전하다.
스택 클래스도 큐 모듈에서 제공한다. 클래스의 이름이 LifoQueue이다.
지금까지 스택이나 큐를 직접 구현한 것은 스택과 큐의 구조에 대한 이해를 위해서이다. 실제 스택과 큐를 사용할 때는 파이썬의 큐 모듈을 이용하면 된다.