빗바이빗
19
2019-05-02 18:13:56 작성 2019-05-02 18:18:32 수정됨
3
495

배열의 메모리 저장 구조 관련 질문 드립니다.


안녕하세요.
오랜만에 큐를 배열로 구현하기 위한 환형 큐에 대해서 살펴보다가 문득 궁금해진 것이 있어 질문 드립니다.


어떤 큐에 1, 2, 3, 4, 5  라는 값이 있다고 가정할 때
링크드 리스트가 아닌 배열을 이용해 구현할 때 생길 수 있는 문제는
- 별 다른 처리 없이 그냥 enqueue - dequeue 를 반복하다 보면 dequeue된 공간이 낭비되게 된다.
- 위 문제를 해결하기 위해 dequeue 할 때, 각 배열의 값을 모두 한칸씩 앞으로 땡기면
  매번 dequeue 할 때마다 작업해야 할 양이 많아진다.

이런 점이 있기 때문에 큐의 맥스 사이즈를 정하고 환형큐 로 구현한다고 알고 있습니다.


그런데 여기서 의문점은 [1, 2, 3, 4, 5] 라는 배열에서 1을 dequeue 하고 나면
배열의 시작 위치 메모리 주소값을 2의 위치로 바꾸는 방식이
굳이 환형큐를 사용하는 것보다 깔끔한 해결 방식 아닌가요?

왜 환형큐를 사용해야 하는 걸까요.


배열 최대 사이즈를 늘려야 하는 경우 메모리 공간을 확장하면서 연속된 공간 확보가 어려울 경우
새로운 메모리 공간에 다시 배열을 재할당 해주기 위해
배열 시작 메모리 주소도 바꿔야 하는 경우가 있을 거라
배열의 시작 메모리 주소가 바뀌면 안 된다고 볼 수는 없을 것 같은데요.


뭘 잘못 알고 놓친 부분이 있는지 궁금합니다.
혹시 초기 배열 할당 [1,2,3,4] 에서 추가로 [5,6,7] 값을 추가해 줄 때
연속으로 할당해줄 공간이 없을 때 전체를 연속된 공간에 할당하기 위한 재배치가 이루어지는 것이 아니라
[1,2,3,4,5의 값이 시작되는 메모리주소],    [5,6,7]  이렇게 할당이 되나요?

1
  • 답변 3

  • rezigrene
    1k
    2019-05-02 20:44:02
    오랜시간동안 사용하는 시스템에선  메모리주소 끝까지 큐가 훑고 지나가는 사태가 벌어지겠네요..
  • Deer Hunter
    328
    2019-05-03 01:12:26

    원형큐가 아닌 선형큐에서 dequeue 후에 시작 위치만 다음 요소로 바꾸면, 말씀하신 dequeue 된 공간이 낭비되는 문제가 발생합니다.

    이를 해결하기 위해 원형큐를 사용하는 것입니다.


  • 빗바이빗
    19
    2019-05-03 03:08:24

    rezigrene // 감사합니다. 확실히 말씀하신 문제가 발생할 수 있겠군요. 제가 놓친 부분이 그것인 것 같습니다.
    Deer Hunter // 답글 감사합니다. 다만, 제 질문의 포인트와 다른 답변입니다.

  • 로그인을 하시면 답변 을 등록할 수 있습니다.