배열로 push_swap 해보자! (5)
“push_swap에 대하여”
< 목차 >
명령어 함수
1. void resize(t_deque *d, int new_cap)
void resize(t_deque *d, int new_cap)
{
int *new_arr;
int idx;
int i;
new_arr = (int *) malloc(sizeof(int) * new_cap);
idx = 0;
i = d->head - 1;
if (d->head < d->tail)
while (++i < d->tail)
new_arr[idx++] = d->arr[i];
else
{
while (++i < d->capacity)
new_arr[idx++] = d->arr[i];
i = -1;
while (++i < d->tail)
new_arr[idx++] = d->arr[i];
}
free(d->arr);
d->arr = new_arr;
d->head = 0;
d->tail = idx;
d->capacity = new_cap;
}
스택에 원소를 push해야 하는데, 스택의 size가 capacity와 동일해서 더 이상 원소를 받을 수 없는 경우, capacity를 2배로 늘려 새로운 배열을 할당한 뒤, 이전 배열의 정보를 옮겨담는다.
스택에서 원소를 pop했는데, 스택의 size가 capacity의 2분의 1 이하인 경우, capacity를 2분의 1로 줄여 새로운 배열을 할당한 뒤, 이전 배열의 정보를 옮겨담는다.
이전 글의
push_back()에서 resize하는 것을 살짝 보여줬었다. 여기서 자세하게 살펴보자. 우선 기존의 capacity의 2배에 해당하는 매개 변수new_cap만큼의 새로운 정수 배열을 할당한다.
new_arr = (int *) malloc(sizeof(int) * new_cap);
- 이후, 원래의 배열에서 새로운 배열로 원소들을 하나씩 복사하는데, 여기서 분기가 2개로 나뉜다.
(1) head < tail인 경우
...
i = d->head - 1; // 전위 연산을 하기 위해 -1을 함
idx = 0;
...
if (d->head < d->tail)
while (++i < d->tail)
new_arr[idx++] = d->arr[i];
...
- head가 tail보다 작은 경우는 간단하다. 우리가 평상시에 배열을 복사하는 것처럼 순서대로 하나씩 복사하면 된다. 이 경우는 주로 capacity를 줄일 때 발생한다. 아래를 보자.
"t_deque* a의 정보"
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... , -, -}
↑
head
idx = 0 1 2 3 4 5 6 7 8 9 ... 14 15
size = 8; // 스택 a의 사이즈
- 위 코드는 stack a가 계속해서 pop_back되서, size를 줄인 순간 8이 되어 기존의 capacity인 16의 절반 이하가 된 모습이다. capacity를 8로 조정하여 새로운 배열을 만들 것이다.
...
i = d->head - 1; // 전위 연산을 하기 위해 -1을 함
idx = 0;
...
if (d->head < d->tail) // d->head = 0, d->tail = 8
while (++i < d->tail) // while 문을 8회 돌면서 배열을 채우게 된다.
new_arr[idx++] = d->arr[i];
...
- 그런데 이 분기문…, capacity를 줄일 때 생기는 예외에 대한 처리가 안되어있다. 애초에 줄이는 것을 상정하지 않고 만든 코드이기 때문에 제출할 때는 몰랐던 것 같다. 8로 조절해서 배열을 만들었을 때, head가 0이 되고, capacity가 new_cap이 되는 건 맞는데, tail이 8이 되는건 문제가 있다.
...
d->head = 0;
d->tail = idx; // 예외가 있다.
d->capacity = new_cap;
...
- 배열을 복사하고 나면 idx가 8이 될 것이다. capacity가 8인 배열에서 tail은 8이 될 수 없다. a[7]이 배열의 마지막이기 때문이다. 따라서 capacity를 줄였을 때, tail이 capacity와 같다면 tail을 0으로 바꾸는 작업이 필요할 것이다. tail이 0일 때, tail - 1은 capacity 처리에 따라 arr[7]이 된다.
if (d->tail == new_cap)
d->tail = 0;
- 이거 말고도 내가 찾지 못한 예외가 있을 것 같은데…, 일단 여기까지만 설명하도록 하겠다.
(2) head >= tail인 경우
...
i = d->head - 1; // 전위 연산을 하기 위해 -1을 함
idx = 0;
...
else
{
while (++i < d->capacity)
new_arr[idx++] = d->arr[i];
i = -1;
while (++i < d->tail)
new_arr[idx++] = d->arr[i];
}
...
- 주로 capacity를 늘리는 상황에서 발생한다. tail이 head보다 작은 상황이라는 것은 많은 예시를 봐서 알듯이
capacity = 16
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , -, 11, 10}
↑
head
- 이런 상황을 말하는 것이다. 그런데 여기에 원소를 계속해서 push하면…?
capacity = 16
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 11, 10}
↑
head
추상화된 stack a = {11, 10, 1, 2, …, 16}, arr[head]가 11이고 arr[tail - 1]이 16이고… 그 다음은 뭐다? 우리는 arr[head]부터 arr[tail - 1]까지를 스택으로 간주한다.
tail이 밀리면서 head와 같아지는데, 여기에 뭘 더 push하려고 할 때 capacity를 늘리게 되는 것이다. 두 번째 분기는 주로 이런 상황에 발생하게 된다. 아래를 보자.
...
while (++i < d->capacity) // i는 head와 동일
new_arr[idx++] = d->arr[i];
...
- 먼저 새로운 배열에, 기존 배열의 head에서 capacity - 1까지의 수까지 복사한다. 위에 16개짜리 배열에서는 먼저 11이랑 10을 새로운 배열에 복사해 넣는 것이다. 그 다음…
...
i = -1; // 전위 연산하려고 -1로 함
while (++i < d->tail) // i = 0으로 시작
new_arr[idx++] = d->arr[i];
...
- i를 0으로 바꾸고, tail까지 새로운 배열에 복사해넣는다. 위에 16개짜리 배열에서는 1부터 16까지를 복사해 넣는 것이다. 그리고 head를 0, tail을 idx(여기서는 예외가 없다!), capacity를 new_cap으로 바꾸면, 결과적으로는 …
capacity = 32;
arr = {11, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, '-', ... , '-', '-'}
↑ ↑
head tail
- 이렇게 깔끔한, 새로운 capacity의 배열로 바뀌게 된다. 여기까지가 resize가 되겠다.
2. void rotate(t_deque *d, int new_cap)
void rotate(t_deque *d)
{
push_back(d, pop_front(d));
}
- 짧다. push_back과 pop_front를 제대로 이해했다면 설명이 필요없는 수준이다. 스택의 top에서 빼서 스택의 bottom에 가져다 놓는다. 스택의 첫 번째 원소가 마지막 원소가 된다. 물론 head와 tail, capacity도 알아서 맞춰지게 되어 있다. 내가 직접 vscode에 적어두었던 메모로 설명을 갈음하도록 하겠다.
- 위 메모는 추상화된 stack a = {2, 3, 4, 5}을 rotate해서, {3, 4, 5, 2}로 바꾸는 과정이 담겨 있다. h는 head의 약자, t는 tail의 약자이다. (1)에서 2가 pop_front 되고 (2)에서 그 2가 push_back 되었다.
3. void reverse_rotate(t_deque *d, int new_cap)
void reverse_rotate(t_deque *d)
{
push_front(d, pop_back(d));
}
- 마찬가지다. 스택의 bottom에서 빼서 top으로 가져다 놓는다. 스택의 마지막 원소는 스택의 첫 번째 원소가 된다. 또한 vscode에 적어두었던 메모로 설명을 대신한다.
- 위 메모는 추상화된 stack a = {3, 4, 5, 2}를 reverse rotate해서, {2, 3, 4, 5}로 바꾸는 과정이 담겨있다. 이것은 rotate의 역연산이다. (1)에서 2가 pop_back 되고, (2)에서 그 2가 push_front 되었다.
4. void push(t_deque *from, t_deque *to)
void push(t_deque *from, t_deque *to)
{
if (empty(from))
return ;
push_front(to, pop_front(from));
}
- from 스택의 top 원소를, to 스택의 top에 옮긴다. pa, pb 모두 옮기려는 스택이 비어있다면 아무런 행위를 하지 않기 때문에 그것에 대한 예외처리를 해야한다. 그 이후에는 간단하다. from 스택에서 pop_front해서 top 스택을 반환받는 후 그대로 그 값을 to 스택에 push_front 해서 top에 써 넣는다.
해제 함수
5. void delete_deque(t_deque *d)
void delete_deque(t_deque *d)
{
free(d->arr);
free(d);
}
- 구조체 안에 동적으로 할당한 정수 배열을 해제하고, 이후 구조체 자체를 해제한다. 정수 배열을 해제하는 것을 까먹고 메모리 누수 지점을 찾아 하염없이 맴돌았던 기억이 난다. 메모리 관리를 잘하자.
