큐의 기본과 간단구현

 1  큐의 개념

큐(Queue) 자료구조는 입구와 출구가 따로 있는 원통 형태다. 6장에서 배운 스택과 대비된다.

입구가 하나라 처음 들어간 것이 가장 마지막에 나오는 FILO 특징과 달리 FIFO(First In Last Out) 특징이다.

큐 구조에서 주의할 점은 들어갈땐 지정해서 들어갈 수 있지만, 나올땐 특정 사람을 선택할 수 없는 것이다.

나올 때는 항상 대기줄 출구에서 가장 가까운 사람이 나올 수 밖에 없는 구조다.

 

 2  큐 원리

큐는 양쪽이 뚫려 있는 구조다. 한쪽에서는 삽입만 진행하고, 다른 쪽에서는 추출만 진행된다.

큐에서 데이터를 삽입하는 것을 enQueue, 추출하는 것을 deQueue라고 한다. 또 front(머리)와 rear(꼬리)가 있다.

데이터를 삽입할 때는 꼬리 바로 다음 위치에 삽입하고 추출할 땐 머리 위치가 추출된다.

즉, 머리는 첫 번째, 꼬리는 마지막 데이터를 가리킨다.

 

 3  데이터 삽입 : enQueue

큐에서 데이터를 삽입하는 과정은 rear을 증가시키고 rear 위치에 데이터를 삽입한다.

코드를 표현하면

## 크기가 5인 큐의 생성과 데이터 3개 입력 ##
queue = [None, None, None, None, None]
front = rear = -1

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('<-- [입구]')

 

 

 

 4  데이터 추출 : deQueue

큐에서 데이터를 추출하는 것은 맨 위쪽 데이터를 꺼내는 과정이다. 출구는 한곳 뿐이므로 중간 데이터는 꺼낼 수 없다.

데이터를 추출하는 과정은 front를 증가시키고 front 위치에 데이터를 추출한다.

## 큐에서 데이터 3개 추출 ##
queue = ["화사", "솔라", "문별", None, None]
front = -1
rear = 2

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

front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)

front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)

front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)
print("-------------------")

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