스택(Stack)의 정의와 구현

자료구조의 가장 기본이 되면서, 실제로 정말 많이 쓰이고 있는 스택에 대해 알아볼 것이다.

 

스택이란

쉽게 말해 가장 최근에 들어온 데이터를 가장 먼저 빼내는 형태의 자료구조이다.

이를 후입 선출(LIFO, Last-In First-Out)이라 한다.

 

위의 이미지도 스택의 한 예가 될 수 있다.

여러 권의 책을 차례로 쌓아놓고 이 중 한 권의 책을 들어 올리라고 했을 때, 중간이나 맨 아래의 책보다는 맨 위의 책을 들어 올리는 것이 가장 자연스러울 것이다.

 

하지만 무작정 맨 위의 것을 선택하라는 것은 인간의 사고방식이지,

컴퓨터에게는 어떤 데이터가 맨 위에 있는 것인지를 알려줄 필요가 있다.

이 때 사용되는 것이 top이다.

 

top은 항상 스택에 마지막으로 들어온 데이터를 가리키며, 이것을 이용해 스택에 데이터를 삽입하거나 삭제할 수 있다.

 

스택을 직접 구현하면서 동작 방식에 대해 살펴보기로 하자. (구현에는 C언어를 사용하였다.)

쉬운 이해를 위해 선형 배열을 사용하여 구현하려고 한다.

 

---

1. 초기화

#define SIZE 5

int stack[SIZE] = { 0 };
int top = -1;

 

우선 크기가 5인 배열을 선언하고 0으로 초기화해주었다.

그 후 top을 저장하기 위한 변수를 선언하였다.

여기서 top을 -1로 초기화한 이유는 top이 가장 마지막 데이터가 있는 인덱스를 저장하고 있게 하기 위함이다.

 

이것은 구현하려고 하는 방식에 따라 달라질 수 있는데,

만약 top이 미래에 데이터를 추가할 인덱스를 가리키도록 할 경우 top을 0으로 초기화할 수도 있다.

 

 

2. 삽입

다음으로 스택에 원소를 추가하는 메소드인 push()를 구현해보자.

void push(int *stack, int *top, int element){
	if(*top == SIZE-1){
    	fullStackException();
    }
    
    *top += 1;
    stack[top] = element;
}

 

스택을 배열로 구현할 경우 배열에 저장할 수 있는 원소의 개수에는 한계가 있다는 것을 생각하고 꼭 예외 처리를 해주어야 한다.

그렇지 않으면 배열이 가득찬 상태에서 push를 시도할 경우 런타임 오류가 발생하고 말 것이다.

배열의 이러한 한계는 연결리스트로 구현할 경우 해결할 수 있다.

 

스택에 아직 여유가 있을 경우 top을 하나 증가시켜준 뒤 값을 넣는다.

 

 

3. 삭제

이번에는 스택의 원소를 삭제하는 메소드인 pop()을 구현해보자.

int pop(int *stack, int *top){
	int element;
    
    if(*top == -1){
    	emptyStackException();
    }
    
    element = stack[*top];
    *top -= 1;
    return element;
}

여기서도 마찬가지로 스택이 비어있을 때 삭제를 시도할 경우에 대해 예외 처리를 해주어야 한다.

스택이 비어있는 것에 대한 예외처리는 연결리스트로 구현하려고 할 때에도 반드시 있어야 하는 부분이다.

 

그 후, 스택의 top에 저장되어 있는 데이터를 저장해 두고 top의 값을 하나 감소시킨 뒤 저장해둔 데이터를 반환한다.

 

---

시간복잡도

이렇게 배열을 사용하여 스택을 구현할 경우 각 작업의 시간복잡도는 O(1)이 된다.

 

이밖에도

배열을 사용하였으므로 추가나 삭제가 아닌 단순 접근을 할 때 굳이 top을 이용하지 않고도 나머지 원소에 접근할 수 있게 되는데,

정말 스택을 스택답게 이용하기 위해서는 스택에 있는 데이터에 접근할 때에도 반드시 top을 이용해서 마지막 원소에만 접근하도록 해야 한다.

 

 

마지막으로 스택을 연결리스트로 구현한 코드를 첨부하고 마무리 하려고 한다.

앞서 배열을 사용한 스택의 push에서 배열의 한계 때문에 fullStackException이 발생하였는데, 이 경우에는 그것에 대한 예외 처리를 해주지 않아도 된다.

또한 연결리스트로 구현하였을 경우에도 각 작업의 시간복잡도는 O(1)이 된다.

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
	int value;
    struct _node *next;
} NODE;

NODE* getnode(int value){
	NODE *node = (NODE*)malloc(sizeof(NODE));
    node->value = value;
    node->next = NULL;
    return node;
}

void initialize(int **top){
	*top = NULL;
}

void push(int **top, int element){
	NODE *node = getnode(element);
    
    node->next = *top;
    *top = node;
}

int pop(int **top){
	int element;
    NODE *tmp;

	if(*top == NULL) emptyStackException();

	element = (*top)->value;
    tmp = *top;
    *top = (*top)->next;

	free(tmp);
    return element;
}