아래 내용과 코드는 해당 교재를 바탕으로 정리한 글입니다.😊
Queue
1. 생활 속 큐
생활 속에서 큐를 설명하자면 은행 ATM기에서 예금을 인출하는 경우가 있습니다. 먼저 줄을 선 사람이 먼저 인출합니다. 이것을 큐의 한 형태로 볼 수 있습니다.
2. 큐의 개념
큐(Queue) 자료 구조는 입구와 출구가 따로 있는 원통 형태와 같은데요.
앞서 배웠던 스택의 FILO(First In Last Out)(or LIFO: Last In First Out)과 대비됩니다. 스택은 입구가 하나라서 처음 들어간 것이 가장 마지막에 나오는 구조였다면, 큐는 입구와 출구가 따로 있습니다.
위에서 설명한 ATM기의 줄, 유명 맛집의 대기줄, 기차가 터널을 나오는 순서 등처럼 먼저 온 순서대로 먼저 나가는 FIFO(First In First Out)의 특징이 있습니다.
💡 스택: FILO(First In Last Out) or LIFO(Last In First Out)
- 가장 먼저 들어간 놈이 가장 마지막에 나옴. 차곡차곡 쌓이는 프링글스 통 모양
💡 큐: FIFO(First In First Out)
- 가장 먼저 들어간 놈이 먼저 나옴. 기차가 터널을 빠져나오는 순서와 같음
3. 큐의 원리
큐는 양쪽이 뚫려 있는 구조이기 때문에 한쪽에서는 데이터 삽입만 이루어지고 다른 한쪽은 데이터 추출만 진행됩니다.
데이터 삽입 작동을 enQueue라고 하며, 반대로 데이터 추출 작동을 deQueue라고 한다.
또한, 큐의 중요한 용어로 front(머리), rear(꼬리)가 있습니다.
데이터를 삽입하면 rear 다음에 새로운 데이터를 삽입하게 될 것이고(rear+1의 위치), 데이터를 추출하면 가장 먼저 들어온 데이터가 나가야 하기 때문에 머리 위치가 추출됩니다.
💡 큐에서 사용한 용어: front, rear, enQueue, deQueue
💡 스택에서 사용한 용어: top, bottom, push, pop
1) 데이터 삽입: enQueue
큐 공간 5칸이 모두 빈 상태가 있습니다.
큐가 모두 비어있다면 front(머리)와 rear(꼬리) 값이 같고, -1이어야 합니다.
front = rear = -1
그리고 데이터를 삽입하면 rear를 오른쪽으로 한 칸 이동시킵니다.
그러면 rear의 값은 0이 되겠죠. 데이터는 0번의 자리에 삽입됩니다.
2) 데이터 추출: deQueue
큐에서의 데이터 추출은 맨 왼쪽의 데이터를 꺼내는 것과 같습니다.
출구가 하나이므로 중간 데이터를 추출하는 것은 불가능하고, 맨 왼쪽의 데이터를 꺼낼 수 있습니다.
그리고 만약 제일 왼쪽의 데이터가 추출된다면 맨앞의 데이터가 비어있기 때문에 그 다음 데이터를 한칸씩 왼쪽으로 이동 시켜주는 것을 생각해 볼 수 있습니다.
이 작업을 하지 않으면 앞의 공간은 계속해서 비어있는데 뒤에 rear는 그대로이기 때문에 작업 공간이 가득찼다고 오해하여 데이터 삽입이 불가능해지기 때문입니다.
(whiteboard로 수작업... 해당 그림이 잘못되었다면 댓글로 알려주세요😂)
4. 큐의 간단 구현
1) 데이터삽입: enQueue
# 생성한 큐에 화사를 넣으려면 우선 rear를 1 증가 시킨 뒤, rear 위치에 데이터를 넣는다.
queue = [None, None, None, None, None] # 크기가 5인 빈 큐 준비
front = rear = -1 # 초깃값 설정
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('<--[입구]')출력 결과
-----큐 상태-----
[출구]<-- 화사 솔라 문별 None None <--[입구]2) 데이터추출: deQueue
# 데이터가 3개 있는 큐에서 데이터를 추출하려면 front를 1 증가시킨 후
# front 위치의 데이터를 밖으로 추출하고 front 위치의 데이터는 None으로 만든다.
queue = ['화사', '솔라', '문별', None, None] # 테스트용 큐
front = -1
rear = 2
# 데이터 추출 이전의 큐 상태 확인
print("----큐 상태-----")
print('[출구] <---', end = ' ')
for i in range(0, len(queue)):
print(queue[i], end=' ')
print('<-- [입구]')
print('----------------')
front += 1 # front 위치를 오른쪽으로 증가
data = queue[front] # 현재 front 위치의 데이터 추출
queue[front] = None # 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('<-- [입구]')출력 결과
----큐 상태-----
[출구] <--- 화사 솔라 문별 None None <-- [입구]
----------------
deQueue --> 화사
deQueue --> 솔라
deQueue --> 문별
----------------
----큐 상태-----
[출구] <--- None None None None None <-- [입구]