Javascript - Queue의 문제점(원형 큐(circle queue))

Queue는 데이터 구조를 하는데 문제점을 가지고 있다. First in, First Out 이라는 개념은 첫번째로 들어온 큐가 제일 먼저 나간다는 점과 제일 나중에 들어 온다는 개념을 활용을 했을 때...(요소를 제거하고 front와 rear의 위치는 이동 해야한다. 이동을 하지 않으면 제거 했을 때, element가 없는 것을 계속 가리키기 때문에)

 

  1. 문제점 : 앞에 요소를 한개 제거하고(dequeue) 첫번째인 front 위치를 한칸 뒤로 이동을 하게 되면, front가 +1 씩 커지면 앞에 있는 빈공간은 필요가 없어진다. 즉, 1억개의 데이터가 들어 있고, front 위치가 99,999,999 위치에 있다면, 그 앞쪽에 있는 빈공간은 아무 쓸모 없어진다.

 

 

 

  2. 문제점 : 앞에 있는 큐를 제거하고 데이터 전부를 앞으로 당긴다면 어떤 데이터를 빼내도 front의 값은 0이므로 굳이 큐라는 데이터를 구조를 사용할 이유가 없다. 또한 1억개의 데이터를 가지고 있고, 1개의 큐를 제거한다면 99,999,999개를 메모리에서 이동시켜야한다. 매우 비효율 적이다.

 

1, 2번 문제를 해결하기 위해 등장한 것이 순환구조인 circle queue(원형 큐)이다. 말 그대로 원형으로 되어 있어서 rear가 꽉차면 다시 앞으로 돌아가 순차적으로 또 넣을 수 있는 구조이다(앞쪽이 계속 빈 큐이면) front와 rear가 연결 되어있어서 순환 하면서 큐를 넣을 수 있다. 하지만 순환큐에도 문제점은 있다.

  3.문제점 : 큐를 만들 때, 초기값으로 front의 위치와 rear의 위치를 같은 위치로 해서 만든다(index : front = 0, rear =0) 여기서 문제가 발생한다. 초기값 즉, 빈 큐를 만들었 때와 큐를 4까지 다 채웠을 때, front === rear(index)가 같다. 여기서 프로그램적으로 모순이 일어나게 된다. 컴퓨터는 초기 빈 큐일때도 front === rear(index) 이고, 모든 큐가 다 차있는 상태에도 front === rear(index)이기 때문에 판단을 하기 어렵다. 어쩔 때는 빈 큐라고 판단 할 수 있고, 어쩔 때는 꽉차있는 큐라고 판단할 수 있기 때문에 문제점이 발생한다. 하지만, 원형 큐는 계속 순환하기 때문에 해결책을 통해서 효율 적으로 사용 할 수 있다.

  원형 큐 해결책 : front를 하나를 사용하지 않고, 비워 두게 된다면 이문제를 프로그램 적으로 해결 할 수 있다. rear와 front는 index를 나타내기 때문에 숫자이다. 이것을 이용하면 rear + 1 === front 이면(rear + 1 index와 front index가 같다면) 꽉차 있는 큐라고 판단 하면 원형 큐 문제점을 해결 할 수 있다. 그 다음 rear === front 이면(rear index와 front index가 같다면) 빈 큐라고 판단 할 수 있다. 이렇게 하면 프로그램적으로 순환 큐의 문제점을 해결 할 수 있다.

#javascript#codestates#queue#linearqueue#circlequeue#큐#선형큐#원형큐#문제점#선형큐문제점#원형큐문제점#원형큐해결책