[자료구조/알고리즘]04. 스택 Stack

CH 04 스택(Stack)

목표

자료구조 스택에 대해 알아보고, C/C++ 프로그래밍 언어로 구현해봄으로써 스택의 이해의 깊이를 늘려보세요

목차

1. 스택이란 무엇인가?
2. 스택 ADT
3. C로 구현하기
4. C++로 바꿔보기
5. 결론

1. 스택이란 무엇인가?

스택이란 마치, 프링글스 통과 같습니다.

그림처럼, 프링글스는 맨 위의 과자를 꺼내지 않는한, 그 밑의 과자는 먹을 수가 없지요. 즉, 가장 나중에 들어온 과자가 가장 먼저 나가게 됩니다. 이를 LIFO (Last In First Out) 구조라고 합니다. 바꿔서 스택이란 자료구조라도 말합니다. 자 지금부터 본격적으로 스택에 대해 알아봅시다.

2. 스택 ADT

스택의 ADT는 다음과 같습니다.

ADT Stack

• characters:
  1. arr: T[]
     • 데이터가 저장되는 배열
  2. top: Int
     • 가장 나중에 저장된 데이터의 위치
• operations:
  1. SInit(st: Stack *) : void
     • 스택을 초기화합니다. 스택 생성 후 가장 먼저 불립니다.
  2. SIsEmpty(st: Stack *) : bool
     • 스택이 비어있는지 여부를 반환합니다.
  3. STop(st: Stack *): T
     • 스택의 가장 맨 위의 데이터를 반환합니다.
  4. SPop(st: Stack *): T
     • 스택의 가장 맨 위의 데이터를 삭제하고 그 값을 반환합니다.
  5. SPush(st: Stack *, data: T): void
     • 스택의 가장 맨 위의 새로운 데이터를 추가합니다.

3. C로 구현하기

원래는 배열 리스트, 혹은 연결 리스트 기반으로 만들어야 실제 프로그래밍 시 사용할 수 있겠지만, 지금은 구현 동작에 초점을 맞추므로 그냥 정해진 길이가 있는 배열로 스택을 구현합니다. 먼저 stack.h를 만들고 다음을 복사해주세요.

stack.h

#pragma once

#include <stdbool.h>

#define MAX 10

typedef int T;

typedef struct _array_stack {
	T arr[MAX];
	int top;
}ArrayStack;

typedef ArrayStack Stack;

void SInit(Stack * st);			//스택 초기화
bool SIsEmpty(Stack * st);		//스택 비어있는지 확인
T STop(Stack * st);				//스택 맨 위의 데이터 확인
T SPop(Stack * st);				//스택 맨 위의 데이터 삭제
void SPush(Stack * st, T data); //스택 데이터 삽입

자 하나 하나 살펴보죠.

#pragma once

이 코드는 프로가드 매크로입니다. 추후, stack.h가 여러 c파일에서 include 되어도 컴파일 후에는 단 하나의 헤더 파일 코드만 존재하게 됩니다.

#include<stdbool.h>

이것은 c에 없는 bool 타입을 표준 라이브러리를 통해 가져오는 코드입니다. 이후, 이 헤더파일을 삽입한 c파일은 bool 타입을 사용할 수 있죠.

#define MAX 5

typedef int T;

typedef struct _array_stack {
	T arr[MAX];
	int top;
}ArrayStack;

typedef ArrayStack Stack;

자 정해진 배열을 가지고 스택을 구현할 것이기 때문에 MAX라는 매크로를 만들어 두었습니다. 이것은 추후에 스택의 배열이 생성될 때와 스택이 꽉차있는지 여부를 반환할 때 사용됩니다. c에서는 제네릭 프로그래밍이 어렵기 때문에, 그냥 int 형을 스택의 자료형으로 삼고 이를 T로 명명했습니다. 

그 후 배열 스택이라는 구조체를 만들었습니다. 필드로는 MAX만큼 길이를 가진 배열 arr과 데이터가 들어오고 나가는 위치를 가리키는 top이 존재합니다. 이후 좀 더 편하게 쓰기 위해서 배열 스택을 스택으로 재 명명하였습니다.

void SInit(Stack * st);			//스택 초기화
bool SIsEmpty(Stack * st);		//스택 비어있는지 확인
T STop(Stack * st);				//스택 맨 위의 데이터 확인
T SPop(Stack * st);				//스택 맨 위의 데이터 삭제
void SPush(Stack * st, T data); //스택 데이터 삽입

아까 정의해둔 ADT를 C코드로 옮긴 것입니다. 이제부터 본격적으로 스택의 동작을 구현해봅시다. stack.c를 만들고 stack.h를 include 합니다. 그 후, 다음 코드를 복사해 주세요.

stack.c

#include "Stack.h"

#include<assert.h>

void SInit(Stack * st) {
	st->top = -1;
}

bool SIsEmpty(Stack * st) {
	return (st->top == -1);
}
	
T STop(Stack * st) {
	assert(SIsEmpty(st) == false);
	return st->arr[st->top];
}

T SPop(Stack * st) {
	assert(SIsEmpty(st) == false);
	T ret = st->arr[st->top];

	st->arr[st->top] = -1;
	st->top -= 1;

	return ret;
}

void SPush(Stack * st, T data) {
	assert(st->top < MAX-1);

	st->top += 1;
	st->arr[st->top] = data;
}

하나 하나, 동작을 뜯어봅시다. 스택의 초기화는 먼저 배열은 생성된 후 0으로 초기화되기 때문에 그대로 두어도 상관 없습니다. 문제는 스택의 맨 위의 데이터를 가리키는 top인데 이는 -1로 초기화를 해주세요.

void SInit(Stack * st) {
	st->top = -1;
}

다음은 스택의 초기 상태를 나타낸 그림입니다.

현재는 스택이 비어있습니다. 즉, top = -1이라면, 스택은 비어있는 것이지요. 따라서 SIsEmpty도 손 쉽게 작성할 수 있습니다.

bool SIsEmpty(Stack * st) {
	return (st->top == -1);
}

이번에는 데이터를 넣어보겠습니다. 어떻게 해야 할까요? 가장 쉬운 방법은 top의 위치를 1올리고 그 자리에 데이터를 넣는 겁니다. 바로 이렇게 말이죠.

void SPush(Stack * st, T data) {
	st->top += 1;
	st->arr[st->top] = data;
}

만약 1을 넣었다면 그림이 이렇게 되겠죠?

근데 이 코드는 위험합니다. 만약 1, 2, 3, 4, 5를 넣었다고 칩시다. 근데 또 Push 명령을 받았다고 합시다. 그림으로 보면 이런 상황이죠.

이 경우에 스택이 소유한 메모리 공간이 꽉 찼기 때문에, 데이터가 들어가선 안됩니다. 따라서, 이것을 방지하는 코드가 있어야 하지요. 결국 top이 될 수 있는 숫자는 MAX-1 미만의 숫자만 가능합니다. 

왜냐 배열의 길이는 MAX 입니다. 그러나 top은 먼저 +1 되고 시작하기 때문에, MAX-1인 상태에서는 SPush가 불리우면 안되죠. 따라서 top은 MAX-1보다 항상 작을 때 SPush가 유효하다고 말할 수 있습니다. 위의 SPush에서 다음을 추가해 주세요.

void SPush(Stack * st, T data) {
    /* 추가 코드 */
	assert(st->top < MAX-1);

	st->top += 1;
	st->arr[st->top] = data;
}

자 이번에는 스택의 가장 맨 위의 데이터를 반환하는 STop 연산을 구현 해봅시다. 쉽습니다. 그냥 현재 top이 가리키는 위치의 원소를 반환하면 됩니다.

T STop(Stack * st) {
	return st->arr[st->top];
}

아까 5까지 넣은 스택이 있다고 치면 그림은 다음과 같겠죠?

근데 이 코드 역시 에러가 날 수 있습니다. 만약 스택이 비어있을 때, STop이 호출된다면 어떻게 될까요? top = -1이니 배열 arr[-1]로 접근하게 됩니다. 이러면 메모리 오류가 나죠. 즉 STop은 SIsEmpty가 항상 false여야 유효하다고 말할 수 있습니다. 따라서 STop에 다음의 코드를 넣어주세요.

T STop(Stack * st) {
    /* 추가 코드 */
	assert(SIsEmpty(st) == false);

	return st->arr[st->top];
}

자 이제 마지막으로 SPop을 구현해 봅시다. STop을 이해하셨다면 굉장히 쉽습니다. 먼저 스택이 비어있는지 확인하고, 데이터가 존재하면, top 위치에 있는 데이터를 저장하고 top을 1 감소시키면 됩니다. 코드는 다음과 같게 되겠죠.

T SPop(Stack * st) {
	assert(SIsEmpty(st) == false);
	T ret = st->arr[st->top];

	st->arr[st->top] = -1;
	st->top -= 1;

	return ret;
}

아까 스택에서 SPop 연산을 하게 되면 그림과 같게 되겠죠?

이렇게 해서 C로 스택을 구현 해보았습니다. 다음 절에서는 C++로 스택을 구현해 보도록 하겠습니다.

4. C++로 바꿔보기

3절 C코드를 C++로 변경하면 다음과 같습니다.

stack.hpp

#pragma once

#include<cassert>

const int MAX = 10;

template<class T> class Stack {
private:
	T arr[MAX];
	int topIdx;

public:
	//스택 초기화
	Stack() : topIdx(-1) {}
	~Stack() {}		

	//스택 비어있는지 확인
	bool isEmpty() {
		return (this->topIdx == -1);
	}
	//스택 맨 위의 데이터 확인
	T top() {
		assert(this->isEmpty() == false);
		return this->arr[this->topIdx];
	}
	//스택 맨 위의 데이터 삭제
	T pop() {
		assert(this->isEmpty() == false);
		T ret = this->arr[this->topIdx];

		this->arr[this->topIdx] = -1;
		this->topIdx -= 1;

		return ret;
	}
	//스택 데이터 삽입
	void push(T data) {
		assert(this->topIdx < MAX-1);

		this->topIdx += 1;
		this->arr[this->topIdx] = data;
	}
};

5. 결론

스택 정리

우리는 이번 시간에 스택의 모든 연산을 C로 구현해보고 동작 과정을 살펴 본 후 C++로 구현함으로써 스택을 이해하게 되었습니다. 어떤가요? ㅎㅎ 스택은 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO 구조라는 것을 잊지 말아주세요. 

여기서는 동작 과정에 초첨을 두었기 때문에, 배열 리스트, 연결 리스트 기반으로 스택을 만들지는 않았습니다. 이를 직접 구현해보는 것도, 좋은 공부가 될 것입니다. 

마지막으로 저는 제가 풀이한 스택 관련 문제들의 URL을 남기고 이만 물러갈까 합니다. 제 문제 풀이를 보기 전에 문제 URL로 접속하셔서 먼저 문제를 풀고 풀이를 봐주세요! 그럼 스택이란 자료구조의 응용법도 손쉽게 터득할 수 있으실 겁니다.

• 알고스팟 FENCE 풀이
• 알고스팟 BRACKETS2 풀이