C Data Structure - 큐

그날 그날 정리하고 올려야 한다.. 묵혀두면 이렇게 고생한다.

-

오늘은 큐에 대해서 기록할 것이다. 큐는 굉장히 중요한 자료구조이다.

큐란 무엇인가?

비유해보자면 선착순이다. 먼저 온 사람이 먼저 서비스를 받는 것!

이를 두고 선입선출의 개념이라고 한다. 그림과 같이 나타낸다.

위 그림에서 옆으로 눕혀진 원통은 배열이라고 생각하면 된다. 배열에서 큐를 구현할 때를 생각해보자.

단순 배열 기반 큐에서의 삽입

단순 배열 기반의 큐에서 삽입 연산을 하는 것은 어려울 것이 없다. 배열의 끝에 값을 추가하듯이 인덱스를 증가시켜가면서 값을 넣으면 된다. 다음과 같이 말이다.

큐를 만들기 나름이지만, 인덱스를 증가시킨 후 삽입하는 것으로 하겠다.

단순 배열 기반 큐에서의 값의 꺼냄(삭제)

그러면 큐의 자료 구조 원칙에 맞도록 먼저 들어온 값을 꺼내려거든 어떻게 해야하나? 이런 경우는 삽입을 위한 인덱스를 하나 두고 증가시키면서 삽입을 진행하고, 꺼내려는 인덱스를 하나 두고 꺼내는 연산을 할 때마다 증가 시키면 된다!

삭제 또한 인덱스를 증가시킨 후 값을 삭제하는 것으로 하겠다.

큐의 꽉참/비워짐 여부 확인

큐를 가지고 삽입 / 삭제 연산을 진행하기 위해서 선행되어야 하는 연산은 큐가 비워졌는지 꽉 찾는지를 확인하면 된다. 아래의 그림은 큐의 비워진 상태를 나타대기 위해서 삽입은 멈추고, 꺼내는 연산만 한 그림이다. 

큐에 값이 꽉 찼음을 확인하는 방법은 선형 큐에서는 다음과 같다.

이 경우이다. 삽입 인덱스가 끝까지 가서 삽입 후 증가를 해야하는데 증가를 하려는데 증가가 안된다. 왜냐하면 인덱스가 끝에 왔기 때문이다. 이 경우 우리는 꽉 찼음을 확인한다. 

배열 기반 큐의 문제

위의 기록한 큐에는 문제가 있다. 다음과 같다.

이는 구조의 문제이다. -> 배열 길이가 정해져있고 순환하지 않는 선형이기 때문에 

이로 인해서 등장하는 것이 원형 큐이다!

원형 큐를 구현하면 선형 큐의 모든 개념 + 선형 큐의 문제 해결이 들어가기 때문에 선형 큐를 따로 포스팅하고 원형 큐에서 구현까지 마무리 지을 것이다.