큐(Queue)

이번 포스팅에서는 선형 구조의 또 다른 자료구조 인 큐(Queue)에 대해 알아 보겠습니다.

스택의 경우 나중에 들어 온 데이터가 먼저 나가는 구조인 데 반하여 큐(Queue)는 먼저 들어온 데이터가

먼저 나가는 구조로, 이러한 특성을 선입 선출(FIFO : First-In First-Out)이라고 한다.

큐의 예로는 매표소에서 표를 사기 위해 줄을 서는 것을 들 수 있다. 줄에 있는 사람들 중 가장 앞에 있는 사람이

가장 먼저 표를 사게 될 것이다. 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다.

컴퓨터 용어 사전에 기재 된 큐는

리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 스택과는 달리 리스트의 한쪽 끝에서는 원소들이 삭제되고

반대쪽 끝에서는 원소들의 삽입만 가능하게 만든 순서화 된 리스트.라고 정의 한다.

그림과 같이 삽입이 일어나는 곳을 후단(rear)이라고 하고 삭제가 일어나는 곳을 전단(front)라고 한다.

그럼 큐의 가장 중요한 연산인 put과 get에 대해 설명을 하자면,

put은 큐의 가장 뒤에 데이터를 넣는 연산이다.

get은 그 반대인 큐의 맨 앞에 데이터를 빼는 연산이다.

put과 get은 데이터를 추가하거나 제거 할 때 사용되며, 그로 인해 front롸 rear이 움직이게 된다.

이 front와 rear이 움직임으로 인해서 큐는 빈 공간을 좀 더 활용적으로 사용 할 수 있다.

다음으로 queue underflow와 queue overflow에 대해 알아보자.

큐 언더플로우(queue underflow)는 큐가 비어 있을 때 get을 하는 경우에 발생하게 된다.

아무 데이터도 없는데 데이터를 달라고 하면 당연히 오류가 발생 할 것이다.

큐 오버플로우(queue overflow)는 큐가 가득 차 있을 때 put을 하는 경우에 발생하게 된다.

큐에 더이상 데이터를 저장 할 공간이 없는데 데이터를 넣으려 한다면 데이터 손실이 일어 날 것이다.

마찬가지로 파란색으로 정의 된 부분을 기억하시고 어떻게 구성 되어있는지 이해를 하신 뒤에

직접 소스코딩을 해보는 것이 최고라고 생각합니다.