생각을 개발하자, 박진형

[자료구조 알고리즘] 큐 - ADT, Array/Circular/LinkedQueue 구현 본문

Data structure & Algorithm/data structure_algorithm

[자료구조 알고리즘] 큐 - ADT, Array/Circular/LinkedQueue 구현

imjinbro imjinbro 2017.09.29 13:32

[큐]

- FIFO : 첫번째로 들어온 데이터가 첫번째로 나감 

- 데이터 저장 입구와 출구가 각각 나뉨

- 예시 : 매표소, 맛집 줄 등



[큐 ADT]

1) isEmpty : 큐가 비었는지 확인

2) enQueue : 큐에 데이터 저장

3) deQueue : 큐에서 데이터 빼기(삭제)

4) qPeek : 첫번째로 저장된 데이터 조회



[큐 구현]

- Array, Linked(노드 간 연결)로 구현


1) ArrayQueue

- 고정적인 크기 

- 내부적으로는 index로 제어

- 1열 형태 + 고정적인 크기 : 입구는 막혔고, 출구는 조금씩 입구와 가까워질 때 데이터가 지워진 공간이 메모리 낭비 

=> CircularQueue 구현이유



2) CircularQueue

- Array를 사용

- ArrayQueue의 한계점을 극복하기위해 출구와 입구를 연결시킴 : 원형 형태(공간낭비 없애기, 입구와 출구가 가까워졌을 때



3) LinkedQueue

- 고정적인 크기 X

- 레퍼런스 타입의 Node를 사용한 큐 구현

- 레퍼런스 타입에 주목할 것




[큐 구현 코드]

- github 공유 : 앞으로 자료구조 코드는 블로그에 직접올리지않고 github에 공유할 예정

- github repo : https://github.com/imjinbro/datastructure

- 게시글은 업로드 되고 있지않더라도 코드를 계속해서 푸쉬되고 있음