✔ Queue 개념 이해✍

SWExperAcademy Queue

◽ Queue 자료 구조의 개념

• 삽입, 삭제의 위치가 제한적인 자료구조
• 큐 뒤(Rear): 삽입/ 큐 앞(Front): 삭제
• 가장 먼저 삽입 된 원소는 가장 먼저 삭제 됨 (선입선출)

◽ 큐의 주요 연산

• enQueue(item) 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산
• deQueue() 큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산
• createQueue() 공백 상태의 큐를 생성하는 연산
• isEmpty() 큐가 공백상태인지를 확인하는 연산
• isFull() 큐가 포화상태인지를 확인하는 연산
• Qpeek() 큐의 앞쪽(front)에서 원소를 삭제 없이 반환하는 연산

◽ Queue의 종류

선형 큐

• 1차원 리스트를 이용한 큐 (리스트의 크기를 고정) => 메모리 낭비
• 큐의 크기 = 리스트의 크기
• fornt: 저장된 첫번째 원소의 인덱스
• rear: 저장된 마지막 원소의 인덱스
• 초기 상태 : front = rear = -1
• 공백 상태: front = rear
• 포화 상태 : rear = n-1 (n: 리스트의 크기, n-1: 리스트의 마지막 인덱스)

원형 큐

• 1차원 리스트를 사용하되, 논리적으로 리스트의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용함.
• 크기가 n인 1차원 리스트 생성(초기 공백큐 생성)
• 초기상태 : front= rear = 0
• 공백상태: front=rear
• 포화상태 : 삽입할 rear의 다음 위치(rear+1) % n = 현재 front

#큐가 비어있을 경우
def isEmpty():
	return front == rear
# 큐가 꽉 차있을 경우 
def isFull():
	return (rear+1) % len(cQ) == front
#원형큐의 삽입
def enQueue(item):
	global rear
	if isFull():
		print("Queue_fULL ",rear)

	else:
		rear = (rear+1)%len(cQ) 
		cQ[rear]=item
def deQueue():
	global front
	if isEmpty():
		print("Queue_Empty")
	else:
		front = (front+1)%len(cQ)
		return cQ[front]
cQ_SIZE = 4
cQ =[0] * cQ_SIZE

#front,rear를 0으로 초기화
front=0
rear =0

enQueue('A')
enQueue('B')
enQueue('C')
print(deQueue())
print(deQueue())
print(deQueue())

리스트를 활용하여 파이썬으로 구현한 원형 큐

def enQueue(item):
	queue.append(item)
def deQueue():
	if isEmpty():
		print('Queue_Empty')
	else:
		return queue.pop(0)
def isEmpty():
	return len(queue) ==0 
def Qpeek():
	if isEmpty():
		print("Queue_Empty")
	else:
		return queue[0]
queue =[]
#front =-1 rear =len(queue)-1 
enQueue('A')
enQueue('B')
enQueue('C')
print(deQueue())
print(deQueue())
print(deQueue())