Queue

1) Queue의 특성

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

Queue 뒤 : 삽입 / Queue 앞 : 삭제

- 선입선출구조(FIFO : First In FIrst Out)

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

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

 

2) Queue의 선입선출구조

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

3) Queue의 기본 연산과정

1. 공백 큐 생성: createQueue();

 

2.

 

4) Queue의 종류

- 선형 Queue

간단하고 기본적인 형태

배열 사용

- 원형 Queue

선형에서 발전된 형태

배열 사용

- 연결 Queue

리스트 형식 사용

- 우선순위 Queue

 

선형 Queue

1. 1차원 배열을 이용한 Queue

Queue의 크기 = 배열의 크기

front: 저장된 첫번째 원소의 인덱스

rear : 저장된 마지막 원소의 인덱스 

2. 상태표현

초기상태 front = rear = -1

공백상태 front = rear

포화상태 rear = n-1

 

원형 Queue

1. 초기공백 상태

front = rear = 0

2. Index의 순환

front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야함

이를 위해 나머지 연산자 mod를 사용

3. front 변수

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

4. 삽입 위치 및 삭제 위치

	삽입위치	삭제위치
선형 Queue	rear = rear + 1	front = front + 1
원형 Queue	rear = (rear +1) mod n	front = (front + 1) mod n

 

연결 Queue

1. 단순 연결리스트(LInked List)를 이용한 Queue

- Queue의 원소 : 단순 연결 리스트의 노드

- Queue의 원소 순서 : 노드 연결 순서, 링크로 연결 되어 있음

front : 첫번째 노드를 가르키는 링크

rear : 마지막 노드를 가르키는 링크

 

2. 상태표현

초기상태 

front = rear = null

공백 상태 

front = rear = null

 

 

 DFS( 깊이 우선 탐색)

- stack 활용

  

 BFS(너비 우선 탐색)

- Queue 활용

- 시작점의 인접한 정점들을 모두 차례로 방문 한후 방문 했던 정점을 시작점으로 하여 다시 인접한 장점들을 차례로 방문하는 방식

- 인접한 정점들을 탐색한 후 차례로 너비 우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 Queue 활용