chorock.page
소개글시리즈프로젝트실험
© 2026 chorock.page
← 목록으로
자료구조 · 4/5
← 이전 글다음 글 →
python자료구조

큐(queue) - ADT, BFS

2026.10.16 · 4분 읽기 · 조회 0

목차
큐ADT큐의 응용큐의 구현선형 큐의 문제원형 큐공백상태와 포화상태구현테스트 프로그램응용: 너비 우선 탐색(BFS)미로 찾기알고리즘테스트 프로그램파이썬의 queue 모듈

큐

  • 큐는 선입선출(First-In First-Out. FIFO)의 자료구조이다.

ADT

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

삽입: enqueue()
삭제: dequeue()

큐의 응용

컴퓨터에서 큐는 매우 광범위하게 사용된다.

  • 프린터와 컴퓨터 사이의 인쇄 작업 큐(버퍼링)
  • 실시간 비디오 스트리밍에서의 버퍼링
  • 시뮬레이션의 대기열(공항의 비행기들, 은행에서의 대기열)
  • 통신에서 데이터 패킷들의 모델링에 이용

-> 줄을 세워 처리하는 곳이면 거의 어디든 큐가 쓰인다.

큐의 구현

선형 큐의 문제

  • 파이썬 리스트로 만든 선형큐는 비효율적이다.

enqueue(item) : 삽입 연산-> O(1)

python
def enqueue(item):
  items.append(item)  # 리스트의 맨 뒤에 items 추가    

dequeue(): 삭제연산 -> O(n)

python
def dequeue():
    if not isEmpty():
        return items.pop(0)  # 리스트의 맨 앞 항목을 꺼내서 반환


맨 앞을 빼면 뒤의 모든 항목이 한 칸 씩 앞으로 이동해야 하므로 O(n)이 된다.

원형 큐

이를 해결하려면 원형 큐를 이용하면 된다.

  • 원형큐는 배열을 원형으로 사용한다
  • 리스트의 크기가 고정되어있다.
  • front: 첫 번째 요소 하나 앞의 인덱스 (최근 삭제된 위치)
  • rear: 마지막 요소의 인덱스 (최근 삽입한 위치)

삽입 : rear를 하나 증가시키고 그 위치에 항목 삽입 : O(1)
삭제 : front를 하나 증가시키고 그 위치 항목을 삭제 : O(1)

공백상태와 포화상태

  • 공백상태: front == rear
  • 변수증가: front = (front+1) % MAX_QSIZE
    rear = (rear+1) % MAX_QSIZE
  • 포화상태: front == (rear+1) % MAX_QSIZE

구현

python
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   
  • 리스트의 크기가 미리 결정되어 있어야 한다.
  • clear: 데이터를 지우지 않고 front 를 rear에 맞추어 공백상태로 만든다.
python
  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를 더하고 나머지를 구해줘야 한다.
python
  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}")

테스트 프로그램

python
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]

응용: 너비 우선 탐색(BFS)

  • 인접한 위치들을 먼저 방문한 다음, 방문한 위치들에 인접한 위치들을 순서대로 찾아가는 방법
  • 원형큐를 이용한다

python
시작               [ ]
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 → 8

DFS에 대한 영상

미로 찾기

  • 미로를 한 칸씩, 출발점에서 가까운 칸부터 넓게 퍼지며 찾고, 다음에 갈 칸을 큐에 줄세운다.
  • 상하좌우 순으로 큐에 넣는다.

알고리즘

범위검사 함수

python
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'
  • 범위 검사를 먼저 수행한다
  • 갈 수 있는 칸: 0(길) or x(출구)
  • 못 가는 칸: 1(벽) 과 마침표(지나온 길)
python
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                        

테스트 프로그램

python
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) 클래스

python
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에 저장됩니다.

관련 글

자료구조자료구조python

연결된 구조(LinkedList)

2026.11.17·7분 읽기·조회 0
자료구조python자료구조

스택(Stack) - ADT, 응용, DFS

2026.10.15·11분 읽기·조회 0
자료구조python자료구조

리스트(List) : ADT, Array, Linked-List

2026.10.13·5분 읽기·조회 0

목차

큐ADT큐의 응용큐의 구현선형 큐의 문제원형 큐공백상태와 포화상태구현테스트 프로그램응용: 너비 우선 탐색(BFS)미로 찾기알고리즘테스트 프로그램파이썬의 queue 모듈