#24 [C 자료구조] 큐 with 동적 할당 배열

지난, 지지난 포스팅에서 큐에 대해서 간략하게 설명했다!

큐 또한 다른 배열과 마찬가지로 동적 메모리를 할당할 수 있다ㅎㅎ 이 죽일 놈의 사랑

코드를 n배 어렵게 하는 동적 할당 배열을 큐와 함께 사용해보자.

아이 신나!

신나는 표정

동적 할당 배열 큐 개념

동적 할당 배열은 정적 배열의 큐가 메모리가 부족해지는 경우에 대비해서 만들어졌다. (+메모리 낭비 방지)

따라서 다음과 같이 확장해야 한다.

포화된 정적 큐

우리는 이미 포화된 큐, 그리고 마지막 인수가 중간에 있는 원형 큐에서 메모리를 확장해야 한다.

1) 이렇게 되면 다음과 같이 중간에 빵꾸가 나게 된다.

따라서 배열 크기를 확장 후 원소의 위치를 복사해서 조정해야 한다. 

2) 먼저 아래와 같이 잘라내어 값을 붙여 넣기 한 뒤

3) ABCDEFG 위치를 다 같이 조정해준다.

capacity 즉 공간은 8에서 16으로 늘어났고

확보한 메모리 공간을 원래 원형 큐의 이름으로 대체해준다!!

---

 

 

 

동적 할당 배열 큐 코딩

신나는 코딩 시간이다. 아이 신나.

위와 같은 1)2)3) 논리로 진행하면서 코딩을 하면 간편하게 할 수 있다!

 

void addq(element item) {
	rear = (rear+1) % capacity; // rear가 끝에 오류나는 것을 방지하기 위한 조건문
    if ( front == rear )
    	queueFull();
    queue[rear] = item;
}

먼저 이와 같이 addq 함수를 정의해줬다. rear에 item을 추가하는 방식이다.

void queueFull(){ //full이면 오류를 나타내지 않고, 두 배로 메모리를 늘린다.
	element* newQueue;
    MALLOC( newQueue, 2 * capacity * sizeof(*queue) ); //메모리 공간 확보한 새 메모리를 만듦
    
    int start = (front + 1) % capacity; 
    if ( start < 2) // 데이터가 한쪽에만 치우쳐져 있는 경우
    	copy ( queue + start, queue + start + capacity - 1, newQueue); //걍 통복붙으로 끝내버림
    else {
    	copy ( queue + start, queue + capacity, newQueue); //오른쪽 복사해서 새 메모리 맨 왼쪽으로
        copy ( queue, queue + rear + 1, newQueue + capacity - start ); // 나머지 왼쪽 복사해서 그 뒤에 붙임
        }
        
        front = 2 * capacity - 1; // front -->15
        rear = capacity - 2; // rear --> 공백 + 마지막 인자 위치 -2
        capacity = capacity * 2
        free(queue);
        queue = newQueue;
    }

참쉽쥬?

 

주석을 통해 이해하면 어렵지 않게 나만... 이해할 수 있을 것이다.