jow1025   5년 전

책에 순차큐의 공백상태를정의하는데 문제가발생(front==rear일때 공백아닌경우있음)하기때문에

이를 보완한게 원형큐라고 설명이되어있는데요 .그럼 큐의구현문제 특히,큐의배열을 크게선언해도되지않을 경우

무조건 순차큐보다 원형큐를 사용하는게 옳은가요? 아니면 순차큐가 공백의상태의 애매함이 생길수있음에도 원형큐

대신 쓰여서 더 좋은 경우가있는지 궁금합니다.

djm03178   5년 전

무슨 뜻인지 잘 모르겠습니다. 오히려 순차큐에서는 front, rear 모두 증가만 하기 때문에 front == rear이면 무조건 empty한 상태인 것이고, 원형 큐에서는 rear가 한 바퀴 돌아서 다시 front에 돌아왔을 때 큐가 꽉 찬 상태임에도 불구하고 empty로 판단해버리는 일이 발생할 수 있습니다. 원형큐에서도 무조건 front, rear를 증가시키고 큐의 capacity로 나눈 나머지를 사용하면 이런 문제를 해결할 수는 있는데, 순차큐에서 그 판단을 못 하는 경우가 있다는 건 이해할 수 없네요.

djm03178   5년 전

원형 큐가 순차 큐에 비해 좋은 점은 배열의 크기를 "큐에 동시에 들어가있을 수 있는 최대 원소 수"만큼만 할당해주면 되기 때문이고, 그 외에는 특별한 장점은 없습니다. 문제 풀이에서는 이 값과 "프로그램이 실행되는 동안 push되는 총 원소 수"가 동일한 경우가 많기 때문에 오히려 매번 나머지 연산으로 인덱스를 조정해줘서 더 느린 원형 큐를 쓸 일도 별로 없는 것 같습니다.

jow1025   5년 전

책에 순차큐의 잘못된 포화상태인식문제,큰 오버헤드의 발생하는경우를  해결하기 위해 원형큐를 사용한다고 되어있는데 한번 찬찬히 다시 이해해보겠습니다. 감사합니다.!

댓글을 작성하려면 로그인해야 합니다.