Queue

 

큐(Queue) : 

1. 삽입, 삭제의 위치가 제한적인 자료구조

큐 뒤 : 삽입 / 큐 앞 : 삭제

2. 선입선출구조(FIFO : First In First Out)

큐에 삽입한 순서대로 원소가 저장

가장 먼저 삽입(First In)된 원소는 가장 먼저 삭제(First Out)

3. 큐의 예 : 서비스 대기 행렬

오버플로우(Overflow) : 큐가 꽉 참.

언더플로우(Underflow) : 큐가 비어 있음.

 

 

🔸 큐의 종류

1. 선형 큐 : 간단하고 기본적인 형태. 리스트 사용 

2.  원형 큐 : 선형에서 발전된 형태. 리스트 사용

3. 연결 큐 : 연결 리스트 형식을 이용

4. 우선순위 큐

 

 

🔅 큐의 선입선출 구조

머리(Front) 저장된 원소 중 첫 번째 원소

꼬리(Rear) 저장된 원소 중 마지막 번째 원소

기본 연산 : 삽입(enQueue), 삭제(deQueue)

 

 

💫 큐의 주요 연산

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

 

💘 선형 큐

초기 상태 : front = rear = -1

공백 상태 : front = rear

포화 상태 : rear = n-1 (n은 배열의 크기)

원소의 삽입과 삭제가 반복될 경우 배열의 앞부분이 낭비됨.

원형큐로 해결하자~

 

 

💝 원형 큐

초기 공백 상태 : front = rear = 0

삽입 : rear=(rear+1)mod n

삭제 : front=(front+1)mod n

포화 상태 : (rear+1)mod n=front

front는 항상 빈자리로 둔다.

front와 rear가 마지막 인덱스를 가리킨 후, 인덱스 0으로 이동하기 위해 나머지 연산자 mod를 이용

 

 

🍕 연결 리스트 큐

초기 상태 : front = rear= null

공백 상태 : front = rear = null

포화 상태 검사는 없고 공백 상태 검사만 하면 됨.

 

 

💨 큐의 기본 연산 과정

1. 공백 큐 생성 : createQueue()

front=rear=-1

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

front=-1

rear=A

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

front=-1

rear=B

4. 원소 반환/삭제 : deQueue()

front=0

rear=B

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

front=0

rear=C

6. 원소 반환 / 삭제 : deQueue()

front=1

c=rear

7. 원소 반환 / 삭제 : deQueue()

front=rear

 

 

 

 

 

참고 SW expert academy