스택(Stack)
'쌓아놓은 더미' 스택(stack)의 사전적 의미입니다. 말 그대로 '무언가'를 밑에서 부터 차곡차곡 쌓는 형태입니다.
자료구조에 스택은 그 '무언가'가 곧 자료(data)가 되겠죠. 이제부터 스택의 동작 원리 및 특징에 대해서 다루기로 하겠습니다.
동작 원리
스택을 소개할 때, 밑에서 부터 자료를 차곡차곡 쌓는 형태라고 말씀드렸습니다.
쌓는 것은 자료구조에 저장한다는 의미이고 차곡차곡 쌓기 때문에 순서대로 밑에서부터 저장됩니다.
쌓여있는 구조에서 밑에 있는 것을 빼내려고 하면 어떻게 될까요? 당연히 무너지게 됩니다.
그러므로 저장된 자료들을 뽑을 때는 맨 위에서 부터 뽑아야겠죠. 맨 위에 있는 자료는 순서대로 밑에서 부터 저장되기 때문에 가장 늦게 저장된 자료일 것입니다.
'가장 늦게 저장된 자료가 가장 먼저 뽑힌다.' 이것이 스택의 동작 원리입니다.
우리는 이것은 '후입선출'이라고 합니다. 영어로는 'LIFO(Last In First Out)'라고 하죠.
| 5 | ||||
| 4 | 4 | |||
| 3 | 3 | 3 | ||
| 2 | 2 | 2 | 2 | |
| 1 | 1 | 1 | 1 | 1 |
1에서 부터 5까지 순서대로 스택에 저장하는 모습입니다. 빨간색으로 표현된 자료는 각 단계에서 가장 먼저 뽑을 수 있는 자료입니다.
특징
스택에서는 크게 두 가지 동작이 있습니다. 뽑는 것(Out)과 넣는 것(In) 입니다.
뽑는 것을 우리는 흔히 pop이라고 표현하고, 넣는 것을 push라고 표현합니다.
pop과 push는 위에서 말한 것 처럼, 스택의 가장 위에서 이루어지는기 때문에 이를 가리키는 녀석이 하나 필요한데 우리는 이것을 top이라고 말합니다.
배열과 연결 리스트를 이용해 스택을 구현할 수 있는 데, 배열에서 top는 단순히 index이고 연결리스트에서는 node를 가리키는 포인터가 되겠습니다.
이제 배열과 연결리스트를 이용해 스택을 구현하는 방법에 대해서 알아보겠습니다.
배열
사실 배열로 구현하는 스택은 정말 간편합니다.
top을 처음 설정할 때, -1 또는 0으로 설정할 수 있는데 이것은 취향차이라고 생각합니다.
top이 -1로 초기 설정해주었을 때는, top + 1해주고 push, pop해주고 top - 1을 해주면 되고
top이 0으로 초기 설정해주었을 때는 top에 push하고 top + 1, top - 1 해주고 pop해주면 됩니다.
다음은 1,2,3,4,5를 push 할 때, 각 상황에 맞게 top을 표시한 것입니다.
한마디로 표현하자면 top이 -1로 초기화 되었을 때는, 맨 위의 자료를 가리키고 0으로 초기화 되었을 때는 다음 자료가 push될 자리를 가리킨다고 생각하시면 쉬울 겁니다.
push(data element){ // top = -1로 초기화 되었을 때
if(스택 범위 넘어가면)
return;
stack[++top] = element;
}
pop(){
if(스택 비어있으면)
return;
return stack[top--];
}
push(data element){ // top = 0으로 초기화 되었을 때
if(스택 범위 넘어가면)
return;
stack[top++] = element;
}
pop(){
if(스택 비어있으면)
return;
return stack[--top];
}
연결 리스트
처음 top 포인터는 head 더미 노드를 가리키면서 시작합니다.
이후, push할 때마다, 새로운 노드를 생성해서 새로운 노드의 next가 top을 가리키는 노드를 가리키게 한 후, top이 새로운 노드를 가리키게 하면 됩니다.
사실, next의 방향을 반대로 해도 되지만 pop연산을 할 때 따로 top 이전의 노드에 대한 탐색이 필요하기 때문에 이런 방향을 선택했습니다.
pop을 할 때는 top을 가리키는 노드를 가리키는 tmp 포인터를 생성한 후, top을 이전 노드로 옮기고 tmp 노드는 삭제하면 됩니다.
push(data element){
node* new_node;
new_node = new node;
new_node->element = element;
new_node->next = top;
top = new_node;
}
pop(){
if(top->next = null)
return;
node* tmp = top;
top = tmp->next;
data ret = tmp->element;
delete tmp;
return ret;
}
지금까지, 스택의 동작 원리와 특징에 대해서 알아봤는데요. 가장 중요한 것은 '후입선출' 인 것 같아요.
어떤 문제 상황에 후입선출이라는 원리가 숨어져 있다면 무조건 스택을 활용하면 됩니다.
대표적으로 연산식에 괄호가 올바르게 형성되어 있는지 스택을 이용해서 알 수 있습니다.
닫는 괄호('},],),>')가 나올 때 마다, 순서대로 스택에 push한 여는 괄호(' {, [, (, <')를 pop해서 쌍이 맞는 지, 확인하고 식 전체를 탐색했을 때, stack안에 아무 자료도 없다면 알맞는 괄호 식이 되겠습니다.
추가적으로, 제가 풀었던 알고리즘 문제에서도 스택을 활용한 문제가 있는데요. 바로 드래곤 커브입니다.
어느 정도 스택을 사용할 줄 아시면 이 문제에 도전해보시면 좋을 것 같습니다.
의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!