Queue

원형 큐를 구현했다.

원형 큐는 다음과 같이 f(front),r(rear)이 있는데 F는 시작부분을 나타내고 R은 끝을 나타낸다.

 

처음엔 f와r이 같은 곳에 위치해 있다. 그리고 데이터가 push되면 그곳에 데이터를 저장하고 r을 다음 칸으로 옮긴다.

데이터를 계속 저장하다 큐가 꽉차게 되면 f와 r은 다시 같은 곳에 위치하게 된다.

하지만 이런 상황은 맨 처음 큐가 비었을 때와 동일하기 때문에 큐가 꽉찬 상태인지 비어 있는 상태인지 구분할 수가 없다.

 

따라서 맨 처음 f를 비운 상태로 시작해야 한다.

데이터를 push할 땐 r 위치를 다음 칸으로 옮긴 뒤 r에 데이터를 push한다.

이런 식으로 f위치는 비워두고 r위치에 데이터를 push한다.

 

pop을 해야할 땐 f위치를 다음 칸으로 옮겨 pop할 데이터를 잡은 뒤 

데이터를 pop한다.

 

이렇게 모든 데이터를 pop하게 되면 f와 r은 한칸 차이로, 시작 했을 때와 차이점이 있다.

 

원형 큐를 구현 해보자.

 

 

 

front와 rear,큐 배열을 가진 구조체이다.

 

 

 

front와 rear의 값을 0으로 초기화하는 queueinit함수,

큐가 비었는지 확인하는 qisempty함수,

push할 때 사용되는 NextPosIdx함수, 인덱스를 다음 칸으로 옮겨준다.

여기서 if문을 보면 pos == LEN-1이 있다. 이건 큐가 꽉차 있는 상황을 말한다.

 

 

push해주는 enqueue함수,  처음에 조건문으로 rear을 한칸 앞으로 했을 때의 인덱스가 front와 같다면

에러를 출력한다.

rear의 인덱스를 한칸 앞으로 해주고, 배열에 저장한다.

 

 

 

pop해주는 dequeue함수, 큐가 비어있다면 에러를 출력한다.

front의 인덱스를 한칸 앞으로 해주고, 값을 리턴한다.