Queue 큐

SW Expert Academy 강의

https://swexpertacademy.com/main/main.do
https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do

Queue 자료구조의 개념

• 삽입, 삭제의 위치가 제한적인 자료구조
  • 뒤로는 삽입 / 앞으로는 삭제
• 선입선출!!!(First In First Out : FIFO)

  • 큐에 삽입된 순서대로 원소가 저장됨

  • 가장 먼저 삽입된 원소는 가장 먼저 삭제됨

    
    
• 큐의 맨 앞을 Front(머리)라고 함 (저장된 원소 중 첫번째 원소)
• 큐의 맨 뒤를 Rear(꼬리)라고 함(저장된 원소 중 마지막 원소)\
  
  

---

큐의 기본연산

• 삽입 or enQueue(인큐)
• 삭제or deQueue(디큐)

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

---

큐의 기본 연산 과정

1. 공백 큐 생성 : createQueue() # 자료가 없는 상태이므로 front와 rear는 -1의 값으로 초기화됨
2. 원소 A 삽입 : enQueue(A) # front값은 변하지 않고 rear값이 0으로 변하게 됨
3. 원소 B 삽입 : enQueue(B) # front값은 변하지 않고 rear값이 1로 변하게 됨
4. 원소 반환/삭제 : deQueue() # 가장 먼저 삽입된 원소가 삭제 , 처음을 가리키는 front가 0으로 변함
5. 원소 C 삽입 : enQueue(C) # front값은 변하지 않고 rear값이 2로 변하게 됨
6. 원소 반환/삭제 : deQueue() # B와 C삭제 할 경우 front값이 2로 변함 (2칸 증가)
7. 다 삭제하고 나면 front값과 rear값이 같아짐. 따라서 front와 rear값이 같으면 큐가 비어있다고 판단

---

큐의 종류

1. 선형큐 : 간단하고 기본적인 형태 / 리스트 사용
2. 원형 큐 : 선형에서 발전된 형태 / 리스트 사용
3. 연결 큐 : 선형에서 발전된 형태 / 연결 리스트 형식을 이용
4. 우선순위 큐 : 큐를 응용

---

선형 큐

1차원 리스트를 이용한 큐

1. 큐의 크기 = 리스트의 크기
2. front : 저장된 첫 번째 원소의 인덱스
3. rear : 저장된 마지막 원소의 인덱스 (위치를 의미)

상태 표현

1.초기상태 : 비어 있기 때문에 저장된 원소가 없음. front = rear = -1
2. 공백 상태 : 큐의 연산이 진행되는 동안 큐가 비어있는 공백상태의 경우 front = rear
3. 포화 상태 : rear값이 리스트의 마지막 위치값이 되어있을 때 포화상태의 경우 rear = n-1(n : 리스트의 크기, n-1 : 리스트의 마지막 인덱스)

---

선형 큐의 구현

초기 공백큐 생성
1. 크기 n인 1차원 리스트 생성
2. front, rear = -1로 초기화

삽입 enQueue(item)
1. 마지막 원소 뒤에 새로운 원소를 삽입하기 위해서는 rear값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련함
2. 그 인덱스에 해당하는 리스트 원소 Q[rear]에 item을 저장

def enQueue(item):
	global rear
    if isFull(): 
    	print("Queue is Full")
    else:
    	rear += 1
        Q[rear] = item

삭제 deQueue()
1. 가장 앞에 있는 원소를 삭제하기 위해 front값을 하나 증가시켜 큐에 남아있는 첫번째 원소로 이동함
2. 새로운 첫번째 원소를 리턴함으로써 삭제와 동일한 기능을 함

def deQueue():
	global front
    if isEmpty(): 
    	print("Queue is Empty")
    else:
    	front += 1
        return Q[front]

공백상태 및 포화상태 검사 isEmpty(). isFull()
1. 공백상태 : front = rear

def isEmpty():
	return front == rear

2. 포화상태 : rear = n-1 (n : 리스트의 크기, n-1 : 리스트의 마지막 인덱스)

def isEmpty():
	return rear == len(Q)-1

가장 앞에 있는 원소를 검색하여 반환 Qpeek()

• 현재 front의 한자리 뒤(front +1)에 있는 원소, 즉 큐의 첫 번째 원소를 반환
• 프론트 값이 변경되면 안됨

def Qpeek():
	if isEmpty():
    	print("Queue is Empty")
    else:
    	return Q[front+1]

---

선형 큐의 문제점 (잘못된 포화 상태 인식)

• 장점 : 삽입, 삭제의 처리 속도가 빠름 BUT!
• 리스트의 크기를 고정 -> 사용할 큐의 크기만큼을 미리 확보 -> 메모리의 낭비 발생

1. 삽입, 삭제를 계속할 경우 리스트의 앞부분에 활용할 수 있는 공간이 있음에도 불구하고 rear = n-1인 상태 즉, 포화상태로 인식
2. 더이상의 삽입을 수행할 수 없음
   
   

• 해결법
  1.원형큐의 사용으로 메모리 절약 (앞쪽의 사용하지 않는 공간을 재활용해서 메모리를 좀 더 효율적으로 사용 가능)

2. 파이썬의 리스트는 크기가 동적으로 변경될 수 있기 때문에 이 특성을 살려 큐를 만들면 메모리 낭비를 덜 할 수 있음 (이 방법의 단점 : 삽입, 삭제, 복사, 데이터 이동시키는 연산 수행에 많은 시간 소모)
3. 단순연결 리스트로 구현한 큐 사용으로 메모리 동적 확보
4. 큐 라이브러리 사용

---

원형 큐

• 선형 큐의 단점을 보완
• 1차원 리스트를 사용하되, 논리적으로 리스트이 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용함
  
  

---

원형 큐의 특징

초기 공백 상태

• front = rear = 0

index의 순환

• front와 rear의 위치가 리스트의 마지막 인덱스인 n-1을 가리킨 후 , 논리적인 순환을 이루어 리스트의 처음 인덱스인 0으로 이동해야 함
• 이를 위해 나머지 연산자 %를 사용

front변수

• 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠

삽입 위치 및 삭제 위치

테이블 인덱스	삽입 위치	삭제 위치
선형 큐	rear = rear + 1	front = front + 1
원형 큐	rear = (rear+1) % n	front = (front+1) % n

---

원형 큐의 기본 연산 과정(큐의 크기가 4인 큐로 예제)

1. 큐 생성 : creat Queue

• front와 rear값이 0으로 초기화되고 큐가 생성

2. 원소 A를 삽입 : enQueue(A)

• 원소 A를 삽입하면 rear값이 1로 변경되고 rear위치에 A가 삽입

3. 원소 B를 삽입 : enQueue(B)

• 원소 B를 삽입하면 rear값이 2(rear + 1)로 변경되고 rear위치에 B가 삽입

4. 큐 삭제 : deQueue()

• 원소 A를 삭제하면 front값이 1로 변경

5. 원소 C를 삽입 : enQueue(C)

• 원소 C를 삽입하면 rear값이 3(rear + 1)로 변경되고 rear위치에 C가 삽입

6. 원소 D를 삽입 : enQueue(D)

• 원소 D를 삽입하면 rear값이 4(rear + 1)로 변경되고 rear위치에 D가 삽입
• rear값이 4가되면 나머지 연산자를 통해 0이 되고 맨 앞자리에 D가 삽입

7. front의 현재위치는 1인데, front가 있는 위치는 사용하지 않으므로 포화상태

---

원형 큐의 구현

초기 공백큐 생성 createQueue()
1. 크기 n인 1차원 리스트 생성
2. front, rear = 0으로 초기화

공백상태 및 포화상태 검사 isEmpty(). isFull()
1. 공백상태 : front = rear

def isEmpty():
	return front == rear

2. 포화상태 : 삽입할 rear의 다음 위치 = 현재 front값 일 때
3. 삽입할 rear의 다음 위치 : (rear +1) % n = front

def isEmpty():
	return front == rear
def isFull():
	return (rear +1) % len(cQ) == front

삽입 enQueue(item)
1. 마지막 원소 뒤에 새로운 원소를 삽입하기 위해서는 rear값을 조정하여 새로운 원소를 삽입할 자리를 마련함 : rear <- (rear + 1) % n
2. 그 인덱스에 해당하는 리스트 원소 cQ[rear]에 item을 저장

def enQueue(item):
	global rear
    if isFull(): 
    	print("Queue is Full")
    else:
    	rear = (rear + 1) % len(cQ)
        cQ[rear] = item

삭제 deQueue(), delete()
1. 가장 앞에 있는 원소를 삭제하기 위해 front값을 조정하여 삭제할 자리를 준비함
2. 새로운 front 원소를 리턴함으로써 삭제와 동일한 기능을 함

def deQueue():
	global front
    if isEmpty(): 
    	print("Queue is Empty")
    else:
    	front = (front + 1) % len(cQ)
        return cQ[front] 
###############################################
def delete():
	global front
    if isEmpty(): 
    	print("Queue is Empty")
    else:
    	front = (front + 1) % len(cQ)
        return cQ[front]	

---

연결 큐