2026.10.16 · 4분 읽기 · 조회 0

삽입: enqueue()
삭제: dequeue()
컴퓨터에서 큐는 매우 광범위하게 사용된다.
-> 줄을 세워 처리하는 곳이면 거의 어디든 큐가 쓰인다.
enqueue(item) : 삽입 연산-> O(1)
def enqueue(item):
items.append(item) # 리스트의 맨 뒤에 items 추가 dequeue(): 삭제연산 -> O(n)
def dequeue():
if not isEmpty():
return items.pop(0) # 리스트의 맨 앞 항목을 꺼내서 반환
맨 앞을 빼면 뒤의 모든 항목이 한 칸 씩 앞으로 이동해야 하므로 O(n)이 된다.
이를 해결하려면 원형 큐를 이용하면 된다.

front: 첫 번째 요소 하나 앞의 인덱스 (최근 삭제된 위치)rear: 마지막 요소의 인덱스 (최근 삽입한 위치)삽입 : rear를 하나 증가시키고 그 위치에 항목 삽입 : O(1)
삭제 : front를 하나 증가시키고 그 위치 항목을 삭제 : O(1)

front == rearfront = (front+1) % MAX_QSIZErear = (rear+1) % MAX_QSIZEfront == (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 # rear 회전
self.items[self.rear] = item # rear 위치에 삽입
def dequeue(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
MAX_QSIZE를 더하고 나머지를 구해줘야 한다. def display(self):
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"[f={self.front}, r={self.rear}] ==> {out}")
q = CircularQueue()
for i in range(8): q.enqueue(i)
q.dislpay()
for i in range(5): q.dequeue()
q.display()
for i in range(8, 14): q.enqueue(i)
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]
시작 [ ]
1 삽입 [1]
1 꺼냄, 2·3 삽입 [2, 3]
2 꺼냄, 4·5 삽입 [3, 4, 5]
3 꺼냄, 6·7 삽입 [4, 5, 6, 7]
4 꺼냄, 8 삽입 [5, 6, 7, 8]
5·6·7·8 꺼냄 [ ] (front와 rear가 같아져 공백)
방문 순서: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8DFS에 대한 영상


범위검사 함수
def isValidPos(x, y):
if x < 0 or y < 0 or x >= MAX_SIZE or y >= MAX_SIZE:
return False
else:
return map[x][y] == '0' or map[x][y] == 'x'def BFS():
que = CircularQueue()
que.enqueue((1, 0))
print("BFS: ")
while not que.isEmpty():
here = que.dequeue()
x, y = here
if map[x][y] == 'x':
print(f"({x}, {y})->", end="")
return True # 출구이면 종료
else:
map[x][y] = '.' # 방문처리
if isValidPos(x-1, y): que.enqueue((x-1, y)) # 상
if isValidPos(x+1, y): que.enqueue((x+1, y)) # 하
if isValidPos(x, y-1): que.enqueue((x, y-1)) # 좌
if isValidPos(x, y+1): que.enqueue((x, y+1)) # 우
print(f"({x}, {y})->", end="")
que.display()
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' ] ]
MAX_SIZE = 6
result = BFS()
if result : print(' --> 미로탐색 성공')
else : print(' --> 미로탐색 실패')
# (2, 2)->[f=5, r=7] ==> [(4, 1), (2, 3)]
# (4, 1)->[f=6, r=7] ==> [(2, 3)]
# (2, 3)->[f=7, r=9] ==> [(1, 3), (3, 3)]
# (1, 3)->[f=8, r=0] ==> [(3, 3), (1, 4)]
# (3, 3)->[f=9, r=1] ==> [(1, 4), (4, 3)]
# (1, 4)->[f=0, r=1] ==> [(4, 3)]
# (4, 3)->[f=1, r=2] ==> [(4, 4)]
# (4, 4)->[f=2, r=3] ==> [(4, 5)]
# (4, 5)-> --> 미로탐색 성공queue 모듈파이썬의 queue 모듈은 큐와 스택 클래스를 제공한다.
큐(queue)와 스택(LifoQueue) 클래스
import queue
Q = queue.Queue(maxsize=20) # 큐 객체 생성(최대크기 20)
for v in range(1, 10):
if not Q.full():
Q.put(v) # 삽입은 put()
for _ in rante(1, 10):
if not Q.empty():
Q.get() # 삭제는 get()앱과 웹을 만들고, 직접 운영하며 기록합니다.
giscus로 동작하며 GitHub Discussions에 저장됩니다.