개요
이전 게시글에서의 스택과 큐는 배열 크기가 고정되어 있었습니다. 이번에는 배열 크기가 고정되지 않고 필요에 따라 확장할 수 있게 코드를 조금 변형해 보겠습니다. 본 게시글에서는 변경 사항만 언급합니다. 일부 생략된 내용이 있으므로 링크해드린 이전 게시글과 함께 읽으실 것을 권해드립니다.
동적 스택
변경 사항
IntStack 구조체가 변경됨
// 변경 전
typedef struct IntStack {
int Elements[5];
int Top;
} IntStack;
// 변경 후
typedef struct IntStack {
int* Elements;
int Top;
int Size;
} IntStack;- 메모리의 동적 할당을 위해
Elements를int*형으로 선언했습니다. - 배열 크기를 나타내는
Size변수를 추가했습니다.
Push 함수가 변경됨
// 변경 전
int Push(IntStackP Stack, int Element) {
If (IsFull(Stack) == True)
Error(0);
...
}
// 변경 후
int Push(IntStackP Stack, int Element) {
If (IsFull(Stack) == True)
Realloc(Stack);
...
}- 스택이 꽉 찼을 때, 배열에 메모리를 다시 할당해주는
Realloc함수가 실행됩니다.
Realloc 함수가 추가됨
void Realloc(IntStackP Stack) {
int* Temp;
Temp = (int*)calloc(Stack->Size * 2, sizeof(int));
for (int C = 0; C < Stack->Size; C++) Temp[C] = Stack->Elements[C];
Stack->Size = Stack->Size * 2;
free(Stack->Elements);
Stack->Elements = Temp;
}- 실행되면 배열 크기를 2배 늘려 스택에 다시 할당합니다. 동작 방식은 다음과 같습니다:
- 1. 새 배열 생성 : 기존의 2배 크기를 갖는 새 배열을 생성합니다.
- 2. 새 배열에 데이터 복사 : 기존 배열에 저장된 값을 새 배열로 복사합니다.
- 3. 기존 배열 할당 해제 : 기존 배열은 더 이상 사용하지 않습니다. 메모리 할당을 해제합니다.
- 4. 새 배열을 스택에 할당 : 크기가 늘어난 새 배열을 스택에 할당합니다. Realloc함수가 단순히 배열 크기를 2배로 늘린다고 생각해서는 안 됩니다.Realloc함수는 기존 배열을 새로 생성한 배열로 대체합니다.
Init 함수가 변경됨
IntStackP Init() {
...
Temp->Size = 5;
Temp->Elements = (int*)calloc(5, sizeof(int));
...
}- 기존의
Init함수에 다음 작업을 수행하는 코드 두 줄이 추가되었습니다:
- 배열의 최초 크기를 설정
- 배열에 최초 크기만큼의 메모리 할당
동적 큐
변경 사항
IntQueue 구조체가 변경됨
// 변경 전
typedef struct IntQueue {
int Elements[6];
int Rear, Front;
} IntQueue;
// 변경 후
typedef struct IntQueue {
int* Elements;
int Rear, Front;
int Size;
} IntQueue;- 메모리의 동적 할당을 위해
Elements를int*형으로 선언했습니다. - 배열 크기를 나타내는
Size변수를 추가했습니다. 이에 따라#define ARRAY_SIZE *로 정의된 매크로 변수는 삭제됩니다. 코드 내 매크로 변수ARRAY_SIZE는 모두IntQueue구조체의Size변수로 대체됩니다.
Init 함수가 변경됨
IntQueue P Init() {
...
Temp->Elements = (int*)calloc(6, sizeof(int));
Temp->Size = 6;
...
}- 기존의
Init함수에 다음 작업을 수행하는 코드 두 줄이 추가되었습니다:
- 배열의 최초 크기를 설정
- 배열에 최초 크기만큼의 메모리 할당
Add 함수가 변경됨
// 변경 전
int Add(IntQueueP Queue, int Element) {
if (IsFull(Queue) == 1)
Error(1);
...
}
// 변경 후
int Add(IntQueueP Queue, int Element) {
if (IsFull(Queue) == 1)
Realloc(Queue);
...
}- 스택이 꽉 찼을 때, 배열에 메모리를 다시 할당해주는
Realloc함수가 실행됩니다.
Realloc 함수가 추가됨
void Realloc(IntQueueP Queue)
{
int* Temp, Free;
Temp = (int*)calloc(Queue->Size * 2, sizeof(int));
for (int C = 0; C < Queue->Size; C++) Temp[C] = Queue->Elements[C];
Queue->Size = (Queue->Size - 1) * 2 + 1;
free(Queue->Elements);
Queue->Elements = Temp;
}
- 동작 방식은 이상의 동적 스택에서 설명한 그것과 같습니다.
- 새 배열의 크기에 관한 추가 설명입니다:
- 최초 큐의 크기가 5이므로, 최초 배열 크기는 6입니다. (배열 크기 = 큐의 크기 + 1)
- 2배 확장될 경우, 배열 크기 = (5 * 2) + 1입니다.
i meant to be