배열로 push_swap 해보자! (4)
“push_swap에 대하여”
< 목차 >
명령어 함수
void swap_top(t_deque *a)
void swap_top(t_deque *a)
{
int tmp;
int idx1;
int idx2;
idx1 = a->head;
if (idx1 == a->capacity - 1)
idx2 = 0;
else
idx2 = idx1 + 1;
tmp = a->arr[idx1];
a->arr[idx1] = a->arr[idx2];
a->arr[idx2] = tmp;
}
- 스택 a의 top에 있는 원소와, 그 다음 원소를 swap 한다. 앞서 우리는
arr[head]가 스택의 top에 있는 원소라는 것을 공부한 바 있다. - 분기문이 눈에 띈다. 마찬가지로 head가 capacity - 1일수도 있다. 아래를 보자.
"t_deque* a의 정보"
capacity = 32;
arr = {2, 3, 4, 5, 6, 7, -, ..., -, 1} // len, capacity = 32
↑ ↑ ↑
top + 1 tail head(top) = capacity - 1
0 6 31
head = 31; // arr[31] = 1;
tail = 6; // a[tail - 1] = 7;
** 추상화된 stack a -> {1, 2, 3, 4, 5, 6, 7} **
스택 a의 size = 7 // {1, 2, 3, 4, 5, 6, 7}의 7개
"swap a 이후, t_deque* a의 정보"
capacity = 32;
arr = {1, 3, 4, 5, 6, 7, -, ..., -, 2} // 1과 2의 위치가 바뀜
↑ ↑ ↑
top + 1 tail head(top)
0 6 31
head = 31; // arr[31] = 2;
tail = 6; // a[tail - 1] = 7;
** 추상화된 stack a -> {2, 1, 3, 4, 5, 6, 7} **
스택 a의 size = 7 // {2, 1, 3, 4, 5, 6, 7}의 7개
- 스택 a의 top과 그 다음 원소를 swap하고 싶다. top은 arr[head]인데, 다음 원소는 배열 상에 존재하지 않는다. 지난 글에서 공부했다시피 이 경우, arr[head]의 다음 원소는 arr[0]이 된다. 배열이 처음과 끝이 이어진 원형 큐와 같이 작동하기 위해선 이와 같이 처리해야한다.
(2) void push_back(t_deque *a, int val)
void push_back(t_deque *a, int val)
{
if (a->size == a->capacity)
resize(a, a->capacity * 2); // void resize(t_deque *a, int new_cap)
a->arr[a->tail++] = val;
if (a->tail == a->capacity)
a->tail = 0;
a->size++;
}
구조체의 포인터와 추가하고 싶은 value를 매개변수로 받아 스택의 bottom에 변수를 추가한다. arr[tail]에 변수를 추가하고(기존 배열은 arr[tail - 1]이 스택의 마지막 원소 bottom), tail을 1 더하고, size를 하나 늘리면 되겠다. 역시 capacity 끝처리를 잘해주어야 한다. 앞으로 등장하는 명령어 함수에 있어서 이런 capacity 끝처리는 계속해서 등장한다. 물론 배열의 끝과 끝이 이어져있다는 것을 인지하고 있다면 아주 어려운 처리는 아니라고 생각한다.
맨 앞에 있는 resize 코드는 다음 글에서 다룰 텐데, capacity가 32인 경우에, arr[0]부터 arr[capacity - 1]까지 모든 배열의 원소가 가득 차 있어서 배열이 더 이상 숫자를 담을 수 없을 때 capacity를 64로 늘린 새로운 배열을 할당하고 기존 배열의 head, tail, size와 같은 정보를 옮겨담는 과정이 담겨있는 코드다. 우선 여기서는 capacity를 늘린다는 점만 염두해두도록 하자.
arr[tail]에 val을 담고, tail에 1을 더했다. 이때 tail이 capacity인 경우에 대한 처리가 필요하다. capacity가 32인 경우, tail이 32면 배열 바깥으로 벗어나게 된다(arr[32], 32개짜리 배열의 마지막 인덱스는 arr[31]이다). 이 경우 tail을 0으로 바꿔주어야 한다. 이렇게 되면 tail - 1이 arr[31]을 가리키고 tail이 0인, 원형으로 이어진 배열 모양을 맞추게 된다.
예를 들어 capacity가 8이고, arr = {1, 2, 3, 4, 5, 6, 7, 8}인 배열을 담고 있는 스택 a를 생각해보자.
arr[head]는 1이고,arr[tail - 1]은 8이다. head와 tail은 둘다 0이다. 물론 head와 tail이 동일할 수 있다. 우리는 arr[head]부터 arr[tail - 1]까지를 스택으로 간주한다. tail - 1이 7인데 왜 tail이 0인지 모르겠다면, 지난 글의int back()을 참고하자.
(예시)
"t_deque* a의 정보"
capacity = 8;
arr = {1, 2, 3, 4, 5, 6, 7, 8}
↑ ↑
head tail - 1
tail
idx = 0 1 2 3 4 5 6 7
size = 8; // 스택 a의 사이즈
- 여기에 9를 push_back() 해보자. 먼저 9가 들어오면 원소의 개수가 capacity보다 많아지므로, capacity를 16으로 resize한다. 스택은 다음과 같이 바뀐다.
"resize한 후, t_deque* a의 정보"
// resize(a, a->capacity * 2);
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, -, -, ... , -}
↑ ↑
head tail - 1
idx = 0 1 2 3 4 5 6 7 8 ... 15
size = 8; // 스택 a의 사이즈
- capacity가 8에서 16으로 바뀌어 새로운 원소를 받을 준비가 끝났다. 이후엔 tail을 하나 늘리고, 원소를 넣고, 사이즈를 늘리는 예의 처리를 진행한다. 9를 push_back 해보자.
"9를 push_back한 후의 t_deque* a의 정보"
// a->arr[a->tail++] = val;
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , -, -}
↑ ↑
head tail - 1
idx = 0 1 2 3 4 5 6 7 8 ... 14 15
size = 9; // 스택 a의 사이즈, size++;
- 마지막엔 역시
a->tail == a->capacity인 경우에 대한 처리가 있다. 이때는 tail을 0으로 바꾼다.
(3) void push_front(t_deque *d, int val)
void push_front(t_deque *d, int val)
{
if (d->size == d->capacity)
resize(d, d->capacity * 2);
d->head--;
if (d->head < 0)
d->head = d->capacity - 1;
d->arr[d->head] = val;
d->size++;
}
- 구조체의 포인터와 추가하고 싶은 value를 매개변수로 받아 스택의 top에 변수를 추가한다. 역시 스택의 size가 늘어나는 연산이기 때문에, size가 capacity와 동일하다면 연산 이전에 배열을 resize한다. 이후 head를 한칸 당기고 그 head의 인덱스에 value를 넣는데, 이때 원래 head가 0이어서 한칸 당겼을 때 음수(-1)가 된다면, head를 capacity - 1로 변경한다. 두말하면 잔소리지만 head가 capacity - 1이 될 수가 있다. 바로 위의 스택 a에 10을
push_front()해보자.
"t_deque* a의 정보"
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , -, -}
↑
head
idx = 0 1 2 3 4 5 6 7 8 ... 14 15
size = 9; // 스택 a의 사이즈
- head는 0으로 1을 빼면 -1이 된다. 이때 head를 capacity - 1로 바꾼다. 그리고 새로이 capacity - 1이 된 head 인덱스(arr[capacity - 1])에 value를 넣는다. 아래와 같다.
"10이 push_front된 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 = 10; // 스택 a의 사이즈
arr[head]에서부터 arr[tail - 1]까지가 스택이기 때문에 추상화된 stack a는 {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}가 된다. a의 top은 10이다. arr[head]가 10이기 때문이다. 배열은 원형 큐 모양을 가지고 있기 때문에 arr[head] 다음의 원소를 찾게 된다면(arr[head + 1]), arr[0]을 반환하게 될 것이다.
그 이외의 push_front는 그냥 head를 당기고, 원소를 넣고, 사이즈를 늘리면 된다. 다시 11을 push_front해보겠다.
"11이 push_front된 t_deque* a의 정보"
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , 11, 10}
↑
head
idx = 0 1 2 3 4 5 6 7 8 9 ... 14 15
size = 11; // 스택 a의 사이즈
- 마찬가지로 추상화된 stack a는 {11, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9}가 된다. a의 top은 11이다. arr[head]가 11이기 때문이다.
(4) int pop_front(t_deque *a)
int pop_front(t_deque *a)
{
int ret;
ret = front(a);
a->head++;
if (a->head == a->capacity)
a->head = 0;
a->size--;
return (ret);
}
pop 계열 함수들은 push 계열 함수들과 달리, 반환형이
int다. 어떤 원소를 반환받는지는 상당히 중요한 issue이기 때문이다. 예를 들어 pa(b의 top에 위치한 원소를 a의 top에 놓는다.)를 구현한다고 해보자. b를pop_front한 후, 그 반환값을 그대로 a에push_front해주면 된다. 얼마나 간편한가? rotate도 마찬가지다. ra(a의 원소들을 한 칸씩 옮긴다. 첫 번째 원소는 마지막 원소가 된다.)의 경우 a을pop_front한 후, 반환값을 그대로 다시 a에push_back해주면 된다. 너무 간편하다.눈치가 빠른 사람은 위 코드에 size에 1을 뺀 이후, 배열의 capacity를 resize하는 코드가 없다는 것을 알았을 것이다. 사실 늘리기만 하고, 줄이지 않아도 과제를 통과하는데는 아무런 문제가 없다. 공간 복잡도는 과제 통과에 제약 사항이 없기 때문이다. 물론 아래처럼 추가해줄 수도 있을 것이다.
int pop_front(t_deque *a)
{
...
a->size--;
if (a->size == a->capacity)
resize(a, a->capacity / 2); // void resize(t_deque *a, int new_cap)
return (ret);
}
- push_front를 유심히 봤다면, pop_front가 push_front의 역연산이라는 것을 빠르게 이해할 수 있을 것이다. 바로 위의 stack a = {11, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9}을 가지고 와서, pop_front를 두번 진행해보자.
"t_deque* a의 정보"
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , 11, 10}
↑
head
idx = 0 1 2 3 4 5 6 7 8 ... 14 15
size = 11; // 스택 a의 사이즈
- pop_front 1회 진행, 반환값은 현재 스택 a의 top,
int front(a)가 된다. 이 반환값은 함수 도입부에 반환값으로 받아둔다.
"pop_front 1회 진행한 t_deque* a의 정보"
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , 11, 10}
↑
head // (head++;)
idx = 0 1 2 3 4 5 6 7 8 9 ... 14 15
size = 10; // 스택 a의 사이즈 (size--)
ret = 11;
반환값은 미리 받아둔 11이 된다. 11이 스택에서 pop 되었다.
11은 arr[head] ~ arr[tail - 1]의 스코프에서 벗어났기 때문에 스코프 바깥으로 벗어났고, 쓰레기 값이 되어(‘-‘과 동일 취급) 더 이상 연산에 영향을 끼치지 못한다. 또 pop_front 해보자.
"pop_front 2회 진행한 t_deque* a의 정보"
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , 11, 10}
↑
head // (head++; -> head = 0;)
idx = 0 1 2 3 4 5 6 7 8 9 ... 14 15
size = 9; // 스택 a의 사이즈
ret = 10;
반환값은 미리 받아둔 10이 된다. 10이 스택에서 pop 되었다.
head에 1을 더했더니, capacity가 되어버렸다(16). arr[16]은 없는 값이기 때문에, 원형 큐와 같이 작동하도록 만들기 위해 head를 0으로 만든다. 배열의 마지막 값(arr[capacity - 1]) 다음은 배열의 첫 번째 값이 된다(arr[0]).
10은 arr[head] ~ arr[tail - 1]의 스코프에서 벗어났기 때문에 스코프 바깥으로 벗어났고, 쓰레기 값이 되어(‘-‘과 동일 취급) 더 이상 연산에 영향을 끼치지 못한다.
(5) int pop_back(t_deque *a)
int pop_back(t_deque *a)
{
int ret;
ret = back(a);
a->tail--;
if (a->tail < 0)
a->tail = a->capacity - 1;
a->size--;
return (ret);
}
- 긴말할 필요없다. 바로 위 코드에서 pop_back한 예시를 본 후,
a->tail--이 음수인 경우도 마저 보는 것으로 이번 글을 마친다.
"t_deque* a의 정보"
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , 11, 10}
↑
head
idx = 0 1 2 3 4 5 6 7 8 9 ... 14 15
size = 9; // 스택 a의 사이즈
stack a = {1, 2, 3, 4, 5, 6, 7, 8, 9}
- pop_back을 진행한다.
"pop_back한 t_deque* a의 정보"
capacity = 16;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , 11, 10}
↑
head
idx = 0 1 2 3 4 5 6 7 8 9 ... 14 15
size = 8; // 스택 a의 사이즈
stack a = {1, 2, 3, 4, 5, 6, 7, 8}
9는 arr[head] ~ arr[tail - 1]의 스코프에서 벗어났기 때문에 스코프 바깥으로 벗어났고, 쓰레기 값이 되어(‘-‘과 동일 취급) 더 이상 연산에 영향을 끼치지 못한다.
tail이 음수인 경우도 살펴보자. 아래 코드는 위에서 썼던, capacity 8짜리 코드이다. head와 tail 똑같이 0인 스택 a다. 여기에 pop_back을 해보자
"t_deque* a의 정보"
capacity = 8;
arr = {1, 2, 3, 4, 5, 6, 7, 8}
↑ ↑
head tail - 1
tail 7
idx = 0 1 2 3 4 5 6 7
size = 8; // stack a의 사이즈 -> {1, 2, 3, 4, 5, 6, 7, 8}
"pop_back한 t_deque* a의 정보"
capacity = 8;
tail
↓
arr = {1, 2, 3, 4, 5, 6, 7, 8}
↑ ↑
head tail - 1
idx = 0 1 2 3 4 5 6 7
size = 7; // stack a의 사이즈 -> {1, 2, 3, 4, 5, 6, 7}
tail이 0이라 1을 빼면, -1이 된다. 이 경우 tail은 capacity - 1이 되고, arr[head] ~ arr[tail - 1]인 {1, 2, 3, 4, 5, 6, 7}만이 스택으로 간주된다.
8는 arr[head] ~ arr[tail - 1]의 스코프에서 벗어났기 때문에 스코프 바깥으로 벗어났고, 쓰레기 값이 되어(‘-‘과 동일 취급) 더 이상 연산에 영향을 끼치지 못한다.
