[자료구조] 큐(Queue) - 선형 큐(Linear Queue), 원형 큐(Circular Queue), 연결 큐(Linked List Queue), 데크(Double-Ended Queue)

선형 리스트란?

[자료구조] 선형 리스트 (Linear List)

연결 리스트란?

[자료구조] 연결 리스트 (Linked List)

 

● 큐 (Queue)

- 데이터를 임시 저장할 때 사용한다.

- 데이터가 rear에서 삽입되고, front에서 삭제된다.

- 선입선출 방식이다. 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다.

- front : 데이터를 삭제하는 부분

- rear : 데이터를 삽입하는 부분

- enqueue : 데이터를 삽입하는 작업

- dequeue : 데이터를 삭제하는 작업

 

● 선형 큐 (Linear Queue)

- 1차원 배열을 이용해 큐를 구현한다.

 

- 문제점 : 앞에 자리가 있음에도 불구하고 포화상태로 인식하는 경우가 있다.

 

● 원형 큐 (Circular Queue)

- 1차원 배열을 이용해 큐를 구현한다.

- 선형 큐의 문제점을 보완하고자 나왔다. -> rear mod queue_size, front mod queue_size

 

● 연결 큐 (Linked List Queue)

- 단순 연결 리스트를 이용해 큐를 구현한다.

 

● 데크 (Double-Ended Queue)

- 큐 두 개중 하나를 좌우로 뒤집어서 붙인 구조다.

- 데이터가 front&rear에서 삽입&삭제된다.

- 양방향으로 연산이 가능한 이중 연결 리스트를 이용하여 구현하는 것이 효율적이다.

○ 삽입 연산

Front Enqueue	Rear Enqueue

○ 삭제 연산

Front Dequeue	Rear Dequeue