[자료구조 큐] What is Queue? / 큐란?

큐(Queue)에 대해 알아보자

 

큐(Queue)

    - 큐에 대해 가장 많이 설명하는 방법

        - 사람들은 줄을 선다

        - 대중교통을 이용할 때, 패스트푸드점에서 주믄을 할 때 등

    - FIFO(First-In, First-Out) 구조의 자료구조이다

 

출처) https://galid1.tistory.com/483

큐(Queue) ADT

 

출처) fundamentals of data structures in c - horowitz

큐(Queue) 구현

    - front(F)와 rear(R)이라는 기준을 사용

    - Enqueue : R이 다음 칸을 가리키게 되고, 그 자리에 새 데이터가 저장된다

출처) 윤성우의 열혈 자료구조

    - Dequeue : F가 가르키는 데이터를 반환하고, F을 한 칸 이동한다

출처) 윤성우의 열혈 자료구조

앞서 설명한 큐를 선형큐라고 표현한다

그러나 선형큐에는 다음과 같은 문제가 존재한다

출처) 윤성우의 열혈 자료구조

큐에 공간이 남아있음에도 불구하고 더 이상 R을 이동시킬 수가 없으며 더 이상 데이터를 추가할 수 없다

이 문제는 원형큐로 해결할 수 있다

 

원형큐 다음 포스팅 참고