큐(Queue)

<큐(Queue)>

스택과 마찬가지로 삽입과 삭제의 위치가 제한되어있는 유한 순서 리스트이다. 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조로 되어 있다.
선입선출 구조 (FIFO, First-In-First-Out) : 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)한 원소는 맨 앞에 있다가 가장 먼저 삭제(First-Out)된다.

2개의 포인터를 가지고 한쪽 끝에서 삽입이 발생되고 다른 한쪽 끝에서 삭제가 일어나는 순차적 구조이다. 뒤(rear)에서 노드가 삽입되고 앞(front)에서 삭제가 일어나도록 제한된다.

[적용분야] -> 정보처리 산업기사/기사 문제에도 나옴
컴퓨터 운영체제 작업 스케쥴링(job scheduling)이나 시분할 방식에 많이 사용되고, 키보드를 사용한 컴퓨터로의 입력이나 모니터, 프린트기를 사용한 출력에 사용된다.

큐의 연산은 enQueue와 deQueue로 한다.

enQueue : 삽입연산, (스택으로 비교하자면 push를 말함)

deQueue : 삭제연산 (스택으로 비교하자면 pop을 말함)

 

[큐 알고리즘 풀이]

<1차원 배열을 이용한 큐>

큐의 크기 = 배열의 크기
- 변수 front : 저장된 첫 번째 원소의 인덱스 저장
- 변수 rear : 저장된 마지막 원소의 인덱스 저장
- 초기 상태 : front = rear = -1 공백 큐 생성
- 공백 상태 : front = rear
- 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

 

[코드]