[Data Structure] 스택(Stack)

이번에는 스택에 대해 다뤄보려고 합니다.

흔히 사용하는 표현 중에서 스택을 쌓는다는 말이 있습니다. 즉, 쌓는다는 말을 사용하듯 밑에서부터 위로 올라가는 형식임을 알 수 있습니다. 

만약 접시를 차곡차곡 쌓는다고 해보겠습니다. 10개를 쌓았는데 그중 6번째 접시를 빼내고 싶으면 10부터 7까지의 접시를 빼낸 후 6번째 접시를 빼냅니다. 

스택에서는 접시 대신 자료가 들어가는 셈입니다. 

스택의 형태는 위의 그림과 같습니다. 내가 원하고자 하는 요소를 얻기 위해서는 그 위에 있는 모든 요소를 빼낸 후 볼 수가 있기 때문에 후입선출 리스트라고 할 수 있습니다. 후입선출은 Last-In-First-Out으로 마지막에 들어온 게 가장 먼저 나간다라는 뜻입니다. 

 

스택에는 연결리스트나 기타 자료구조와는 다르게 top이라는 순서 리스트가 존재합니다. top은 실제 스택과는 별개의 리스트로 연산이 일어나는 스택의 끝을 의미합니다. 스택은 후입선출 리스트이기 때문에 항상 연산은 가장 위에서 일어날 수밖에 없습니다. 

 

그럼 이러한 스택은 어디에 쓰일까요? 예를 들어 편집기능 중에서 undo 기능으로 활용할 수 있습니다. 아니면 함수호출 시 복귀주소를 기억하는데 사용될 수도 있습니다.

 

스택을 이해하는데는 삽입 연산인 push와 삭제 연산인 pop을 알아야 합니다. 

push는 스택의 가장 위에 있는 요소 위에 삽입하는 것이고 pop은 현재 가장 위에 있는 요소를 빼내는 것입니다.

 

○ 스택의 표현

▶ 배열 활용

 

스택을 표현하는 방법은 여러가지가 있습니다. 가장 먼저 생각할 수 있는 방법은 배열로 구현하는 것입니다. 

배열로 구현하는 이유는 일단 쉽고 형태가 유사하기 때문입니다.

#define MAX 5
typedef int element;

typedef struct Stack {
    element arr[MAX];
    int top;
}stack;

stack* create(stack* s) {
    s = (stack*)malloc(sizeof(stack));
    s->top = -1;
    return s;
}

int getlength(stack* s) {
	return top + 1;
}

int isFull(stack* s) {
	return s->top == MAX -1;
}

int isEmpty(stack* s) {
	return s->top == -1;
}


void push(stack* s) {
    if(isFull(s)) {
        ERROR
    }
    else {
    	s->top += 1;
        s->arr[s->top] = x;
    }
}

int pop(stack* s) {
	if(isEmpty(s)) {
        ERROR
    }
	else {
		element e = s->arr[s->top];
		s->top -= 1;
    	return e;
    }
}

element peek(stack* s) {
	return s->arr[s->top];
}

구조체 선언부터 설명하자면 스택 안에는 자료를 담을 배열과 top이 존재합니다. top는 실제로 스택에 영향을 미치진 않지만 항상 연산이 일어나는 마지막 요소를 가리키기 때문에 수차레의 연산을 거쳐도 굳이 맨 위를 찾을 필요 없이 top을 사용하면 되기에 매우 유용한 변수라고 할 수 있습니다. 

그다음은 isEmpty와 isFull입니다. 배열로 선언을 하기 때문에 크기를 무조건 지정을 해줘야 합니다. (malloc이 아닌 이상)

위에서는 MAX_SIZE라는 define된 상수로 취급을 했는데 만약 size가 100일 때 이미 꽉 찬 배열에 삽입을 하려 한다면 오류가 날 것이고 텅 빈 배열에서 삭제를 한다면 마찬가지로 오류가 날 것이기 때문에 이 두 함수를 이용하여 배열의 상태를 판단합니다.

 

처음에 create를 보면 아시겠지만 top을 -1로 지정합니다. 그 이유는 인덱스가 0부터 시작하는데 텅 빈 배열에서 top을 0으로 둘 수는 없기 때문입니다. 그 후에 push와 pop에서는 개념을 그대로 구현합니다.

 

 

▶ 연결 리스트 활용

 

연결 리스트도 활용할 수 있습니다. 함수는 거의 배열과 동일하지만 가장 주의해야 할 사항은 link의 방향입니다. 

보통 연결 리스트를 구현하면 앞에서 뒤로 link를 이어줍니다. 그러나 스택을 연결 리스트로 구현할 때는 link가 위에서 밑으로 내려옵니다. 즉, 가장 밑에 있는 요소는 link field가 NULL을 가리키고 위에 있는 요소들도 그 밑을 가리킵니다. 

예시들을 들어본다면 논리적으로 이러한 구성을 가지는 이유를 알 수 있을 것입니다.

 

typedef int element;

typedef struct stackNode {
	element data;
    struct Stack* link;
}stackNode;

typedef struct Stack {
	stackNode* top;
}stack;

stack* create() {
	s = (stack*)malloc(sizeof(stack));
    s->top = NULL;
    return s;
}

int isEmpty(stack* s) {
	return s->top == NULL;
}

void push(stack* s, element x) {
	stackNode* newNode = (stackNode*)malloc(sizeof(stackNode));
    newNode->data = x;
    
    newNode->link = s->top;
    s->top = newNode;
}

element pop(stack* s) {
	stackNode* cur;
    element e;
	if(isEmpty(s)) {
    	return error;
    }
    else {
    	cur = s->top;
        s->top = cur->link;
        e = cur->data;
        free(cur);
        return e;
    }
}

element peek(stack* s) {
	if(isEmpty(s)) {
		return error;
    }
    else {
    	return s->top->data;
    }
}

배열과의 차이점은 일단 top을 요소와 별개로 처리한다는 것입니다. 배열에서는 top이 일종의 인덱스 번호의 역할을 해줬습니다. 그러나 연결 리스트가 되면서 그럴 필요가 없어졌고 효율적인 선언을 위해 위와 같이 바뀐 것입니다. 

두 번째는 ifFull의 유무입니다. 연결 리스트는 크기의 제약을 받지 않기 때문에 모든 경우에는 false가 나오기에 선언해주는 의미가 없습니다. 

 

---

지금까지 스택의 개념과 간단한 구현에 대해 알아봤습니다. 스택에서는 파생되는 화용이 많기 때문에 다음 게시물에서는 스택을 활용할 수 있는 예시, 후위표기식과 maze problem에 대해 알아보겠습니다.