Queue
: 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조. 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제된다 .(FIFO)
큐의 주요 연산
| 연산 | 기능 |
| enQueue(item) | 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 |
| deQueue() | 큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산 |
| createQueue() | 공백 상태의 큐를 생성하는 연산 |
| isEmpty() | 큐가 공백상태인지를 확인하는 연산 |
| isFull() | 큐가 포화상태인지를 확인하는 연산 |
| Qpeek() | 큐의 앞쪽에서 원소를 삭제 없이 반환하는 연산 |
선형 큐의 구현
# 삽입
'''
- 마지막 원소 뒤에 새로운 원소를 삽입하기 위해
1) rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련
2) 그 인덱스에 해당하는 배열원소 Q[rear]에 item을 저장
'''
def enQueue(item):
global rear
if isFull() :
print('Queue_Full')
else:
rear += 1
Q[rear] = item
# 삭제
'''
가장 앞에 있는 원소를 삭제하기 위해
1) front 값을 하나 증가시켜 큐에 남아있게 될 첫 번째 원소 이동
2) 새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능
'''
def deQueue():
global front
if isEmpty():
print('Queue_Empty')
else:
front += 1
return Q[front]
# 공백 상태 및 포화상태 검사
def isEmpty():
# front와 rear가 같은 곳을 가리킬 때 큐는 비어있다
return front == rear
def isFull():
# 가장 마지막 원소가 저장된 위치가 리스트의 마지막 인덱스 일때 큐는 Full!
return rear == len(Q) - 1
# 검색
'''
- 가장 앞에 있는 원소를 검색하여 반환하는 연산
- 현재 front의 한자리 뒤에 있는 원소, 즉 큐의 첫번째에 있는 원소 반환
'''
def Qpeek():
if isEmpty():
print('Queue_Empty')
else:
return Q[front + 1]
선형 큐 이용시의 문제점
* 잘못된 포화상태 인식
: 선형 큐를 이용하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불구하고, rear = n-1일때 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게된다
해결방법 1)
- > 매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시킨다, 하지만 이동에 많은 시간이 소요되어 효율성이 떨어짐
해결방법 2)
-> 1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형형태의 큐를 이룬다고 가정하고 사용 (논리적 구조)
원형 큐의 구현
- 초기 공백 상태 : front = rear = 0- 인덱스의 순환 : front와 rear가 n-1을 가리킨 후, 0번째 인덱스로 이동해야함-> 이를 위해 나머지 연산자 mod 사용- front 변수 : 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠- 삽입위치 : rear = (rear + 1) mod n- 삭제위치 : front = (front + 1) mod n
# 선형큐의 구현
def isEmpty():
return front == rear
def isFull():
return (rear+1) % len(Q) == front
def enQueue(item):
global rear
if isFull():
print('Queue_Full')
return
else:
# 삽입 위치 인덱스 조정
rear = (rear + 1) % len(Q)
Q[rear] = item
def deQueue():
global front
if isEmpty():
print('Queue_Empty')
return
else:
# 삭제위치 인덱스 조정
front = (front + 1) % len(Q)
return Q[front]
연습문제 2
- 마이쮸 나눠주기 시뮬레이션, 마지막 20번째,,마이쮸는 누가 가져갈지 출력!+ 큐에 있는 사람 수, 현재 1인당 나눠주는 사탕의 수, 현재까지 나눠준 사탕의 수 도 출력해보자
Q = []
# 학생들 번호
n = 1
# 첫번 째 학생 줄 세우기
Q.append(n)
cnt = [0] * 1000
mychu = 20
while mychu > 0:
# 맨 앞친구 마이쮸 받아
t = Q.pop(0)
# 다음에 올 땐 한개 더
cnt[t] += 1
# 마이쮸 감소
mychu -= cnt[t]
# 아까 그친구 다시 뒤로 줄서기
Q.append(t)
# 다음 친구도 줄 서기
n += 1
Q.append(n)
print(t, '학생 =>', cnt[t], Q)
'''
1 학생 => 1 [1, 2]
1 학생 => 2 [2, 1, 3]
2 학생 => 1 [1, 3, 2, 4]
1 학생 => 3 [3, 2, 4, 1, 5]
3 학생 => 1 [2, 4, 1, 5, 3, 6]
2 학생 => 2 [4, 1, 5, 3, 6, 2, 7]
4 학생 => 1 [1, 5, 3, 6, 2, 7, 4, 8]
1 학생 => 4 [5, 3, 6, 2, 7, 4, 8, 1, 9]
5 학생 => 1 [3, 6, 2, 7, 4, 8, 1, 9, 5, 10]
3 학생 => 2 [6, 2, 7, 4, 8, 1, 9, 5, 10, 3, 11]
6 학생 => 1 [2, 7, 4, 8, 1, 9, 5, 10, 3, 11, 6, 12]
2 학생 => 3 [7, 4, 8, 1, 9, 5, 10, 3, 11, 6, 12, 2, 13]
'''
BFS
: 너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
- > 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용한다.
def BFS(G, v):
visited = [0] * (n+1) # n : 정점의 개수
queue = [] # 큐 생성
queue.append(v) # 시작점 v를 큐에 삽입
while queue: # 큐가 비어있지 않는 동안 수행, 비어있으면 끝
t = queue.pop(0) # 첫번째 원소 반환해서 방문
if not visited[t]: # 방문되지 않은 곳이라면 방문했다고 표시하자
visited[t] = True
# visit(t) -> 정점 t를 방문해서 할일
for i in G[t]: # t와 연결된 모든 정점에 대해
if not visited[i]: # 방문되지 않은 곳이라면
queue.append(i) # 큐에 넣기
연습문제3
Q. 다음은 연결되어 있는 두 개의 정점 사이의 간선을 순서대로 나열해 놓은 것이다. 모든 정점을 너비우선 탐색하여 경로를 출럭하시오.
(시작정점은 1로 한다.)
-> 1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7
inputV = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]
n = 7 # 노드의 수
G = [[] for _ in range(n+1)]
for i in range(0, len(inputV), 2):
G[inputV[i]].append(inputV[i+1])
# BFS
def BFS(G, v):
visited = [False] * (n+1)
Q = []
# 시작 정점 추가하고 방문 표시
Q.append(v)
visited[v] = True
while Q:
t = Q.pop(0)
print(t, end=' ')
for i in G[t]:
if not visited[i]:
Q.append(i)
visited[i] = True
## result : 1 2 3 4 5 7 6
주일 낮 교회 앞에서 찍은 사진.
이제는 마냥 예전처럼 까불지 않는다는 말, 웃음을 잃은 것 같다는 말을 여러 곳에서 듣던 중 이었다.
생각이 많아져 스스로를 걱정하고 가엽게 여겼다가도!
모든 일에는 양면이 있고, 어떤 관점으로 볼 것인가 하는 것은 결국 내 몫이라는 생각을 하게 되었다.
난 웃음을 잃은게 아니라 씩씩해 지고 있는거임. ㅎ
무엇보다 원하던 공부도 하게 되었고, 좋은 친구들도 많이 사귀었고, 뭔가를 새롭게 시작할 마음도 잔뜩이다.
감사하지 않을 일이 하나도 없잔아?
댓글