스택

스택(Stack)은 데이터를 쌓아올린듯한 자료구조입니다.

마트에 가면 '프루팁스'라고 제가 좋아하는 젤리를 팝니다.이렇게 생긴 원통형 젤리인데요. 한쪽은 젤리를 꺼낼 수 있는 뚜껑이 있고 반대쪽은 막혀있습니다. 그래서 한쪽으로만 젤리를 넣고 꺼낼 수 있죠. 스택이 마치 이 젤리와 같은 모양의 자료 구조입니다.

스택은 원통형(물론 물리적으로 원통은 아니고 생긴게 그렇다~라는 말입니다.) 자료구조입니다. 데이터를 한쪽으로만 꺼내고 넣을수가 있습니다. 그래서 구조적으로 먼저 들어간 자료가 나중에 나오는데, 이를 후입선출, LIFO(Last In First Out)구조 라고 합니다. 그림으로 대충 표현하자면 다음과 같습니다.

스택의 개념

스택에선 구조를 지칭하는 몇가지 단어들이 있습니다. 구현에 앞서 그 단어들을 알아보고 구현을 해보도록 하겠습니다.

탑 top

탑(top)은 단어 그대로 꼭대기 입니다. 어떤 꼭대기를 지칭하냐면 스택 내부의 데이터 중 가장 위쪽에 있는 데이터가 top 이 됩니다. top이 별거 아닌것 처럼 보이지만 중요한게 top은 가장 나중에 들어온 자료이기도 하면서, 스택의 입출구 역할을 합니다. 원통형이라고 하지만 실제로는 그냥 선형 자료구조이기 때문에 컴퓨터는 입구가 어딘지 알 수 없습니다. 그래서 이 top을 명시함으로써 우리는 입출구를 정할 수 있다는 의외로 중요한 부분이 되겠습니다.

푸시와 팝 push & pop

푸시와 팝, 직역하면 밀다와 튀어나오다 정도네요. 이름에서 대강 유추할 수 있듯이 데이터를 넣고 빼는것을 지칭하는 단어입니다. push는 스택에 데이터를 넣는 것(삽입), pop은 스택에서 데이터를 빼내는 것(삭제)을 지칭합니다.스택에 관련된 것은 이것들이 전부입니다. 스택을 선언하고, top을 설정하고, 푸시와 팝을 구현하면 간단한 스택구조가 완성이 됩니다. 그러면 이들을 기반으로 스택을 한 번 구현해보도록 하겠습니다.

스택은 두 가지 방식으로 구현이 가능합니다. 단순히 배열을 이용한 것과 이전에 배운 노드 구조를 가진 연결 리스트로 구현하는 방식이 있는데 둘 다 장단점이 있으니 둘 다 알아보도록 하겠습니다.

배열로 스택 구현

배열을 이용한 스택 구현의 장점은 정말 간단하다는 것 입니다. 밑에 예제로 비교해보면 아시겠지만, 장점으로는 코드가 정말 간결하고 쉽습니다. 그러나 배열의 고질적인 단점인 크기변화에 유연하지 못하다는 단점도 있습니다.

초기 설정

저는 크기가 100인 배열로 스택을 만들 것이고 스택 내부에는 숫자(int)값만이 들어올 수 있도록 한 스택을 만들려고합니다. 그래서 초기 설정및 초기화는 다음과 같습니다.

top을 -1로 초기화 하는 이유는 top이 특정 숫자가 아니라 배열(스택)의 인덱스를 나타내게 됩니다. 자료를 넣으면 top이 0가 되고 하나 더 넣으면 1이 되는 구조입니다. 그래서 0~99까지 존재할 수 있기 때문에 -1로 초기화 해서 시작하게 됩니다.

#define STACK_SIZE 100

typedef int element;

element stack[STACK_SIZE];

int top = -1;

또 다른 설정으로는 스택이 가득 찼는지, 비었는지 확인하는 메소드가 필요합니다. 구조적으로 어려운 부분은 없으므로 설명은 필요 없으리라 생각이 됩니다!

int isStackEmpty() {
	if (top == -1) {
		return 1;
	}
	else {
		return 0;
	}
}

int isStackFull() {
	if (top == STACK_SIZE - 1) {
		return 1;
	}
	else {
		return 0;
	}
}

푸시 구현

void push(element elem) {
	if (isStackFull()) {
		return;
	}
	else {
		stack[++top] = elem;
	}
}

데이터를 삽입하는 푸시입니다. 의외로 간단하죠?

우선 스택이 가득 찼는지 확인합니다. 가득 찼다면 데이터를 더 이상 푸시할 수 없기 때문에 별다른 동작 없이 넘어갑니다. 저는 그냥 return을 해줬는데, 여기에 printf()등으로 가득 찼다는 메세지를 출력하면 좋을 것 같습니다.

본격적인 푸시는 가득 차지 않았을 때인 else 문 부터 시작합니다. stack의 인덱스인 top을 1올리고 elem을 삽입합니다. 이때 반드시 top을 먼저 1증가시키고 데이터를 넣어야 하기에 전위연산자로 top에 1을 먼저 더했습니다. 여기서 인수 elem은 스택에 넣을 데이터 입니다.

물론 사람마다 구현 방식이 다 다를 수 있습니다. 저는 top 초기화를 -1로 하는 선택을 하였기 때문에 위와 같은 삽입 방식이 나온 것 입니다. 다시 한 번 말하지만 구현에는 정답이 없습니다.

팝 구현

void pop() {
	if (isStackEmpty()) {
		return 0;
	}
	else {
		return stack[top--];
	}
}

팝은 푸시의 반대입니다. 스택이 비었는지 부터 확인합니다. 스택이 비었다면 팝을 할 수 없으니까 말이죠.

제가 한 구현은 간단한 눈속임이 들어있습니다. 보면 팝 연산이 top을 -1 하는 것 뿐입니다. 이렇게 하면 실제적으로 스택에 데이터는 남아있는데, 제일 꼭대기만 바꿈으로써 마치 삭제된 것 처럼 보여집니다. 그리고 이 상태에서 푸시하면 탑 다음 인덱스의 데이터가 덮어씌워짐으로써 정말로 삭제되었던 것 처럼 보일 수 있습니다.

피크 peek

위에서 피크를 말한 적은 없지만 피크 연산도 빠질 수는 없습니다. 피크(peek)는 제일 꼭대기의 데이터를 확인하는 기능입니다. 그 이름처럼 구현도 그냥 top이 가리키는 위치의 데이터를 return 하면 됩니다.

element peek() {
	if (isStackEmpty()) {
		exit(1);
	}
	else {
		return stack[top];
	}
}

연결 리스트로 스택 구현

배열로 스택을 구현했으니 이번에는 연결 리스트로 스택을 구현하는 방법을 알아볼 차례입니다. 연결 리스트의 장점은 배열에 비해 메모리 활용이 자유롭고 크기 변화에도 유연하다는 점 입니다. 단점은 지난번부터 주구장창한 노드를 이용하게 되므로 배열 구현에 비해서 조금 복잡한 양상을 가지고 있다는 점입니다.

노드 정의

연결 리스트로 스택을 구현할 것이니 처음으로 해야 할 일은 노드 구조 정의하기 입니다.이 그림 지겹게 보시죠? 마찬가지로 이를 토대로 노드 구조를 정의합니다.

typedef int element;

typedef struct stackNode {
	element data;	//데이터 필드
	struct stackNode* link;	//링크 필드
} stackNode;

stackNode* top;	//top을 stackNode 형으로 선언

푸시 구현

푸시...라고는 하지만 사실상 연결 리스트의 원소 삽입하는 연산과 동일합니다. 아래에 최대한 쉽게 설명을 적으려고 노력했습니다. 만약 설명이 어렵다면 연결 리스트 삽입을 생각해보면서 이해해본다면 도움이 될 것 같습니다.

우선 임시로 노드 하나를 만들어줍니다(temp). 이 노드의 데이터 필드에는 우리가 실질적으로 푸시할 데이터인 elem을 넣고 링크 필드에는 top을 넣습니다. 왜 top을 넣냐면 이때 top이 현재 스택의 가장 마지막 자료, 즉 우리가 삽입할 원소의 바로 이전 노드가 되기 때문입니다. 이렇게 삽입을 마치면 데이터 필드에는 자료가 담겨있고 링크 필드에는 이전 원소의 주소를 가리키고 있게 됩니다.

그러고나서 마지막으로 top을 지금 삽입한 노드인 temp를 가리키게 하면 정상적인 푸시가 됩니다.

void push(element elem) {
	stackNode* temp = (stackNode*)malloc(sizeof(stackNode));

	temp->data = elem;
	temp->link = top;
	top = temp;
}

팝

스택에서 삭제(팝)는 맨 위의 원소만 가능하기 때문에 임시 노드 변수 temp에 top을 넣습니다. 그리고 top만 바꿔주면 되는데, temp의 링크 필드가 가리키는 노드를 top으로 바꿔주면 됩니다. 왜냐하면 temp = top으로 인해 temp->link 와 top->link가 같은 노드를 가리키고 있기때문입니다. 즉 temp->link는 top의 이전 노드를 가리키고 있습니다.

element pop() {
	stackNode* temp = top;

	if (top == NULL) {
		return 0;
	}
	else {
		top = temp->link;

		free(temp);

		return 0;
	}
}

피크

피크는 top의 데이터를 확인하는 것이기 때문에 top의 데이터를 출력하기만 하면 됩니다.

element peek() {
	if (top == NULL) {
		return 0;
	}
	else {
		return top->data;
	}
}

---

배열 스택과 연결 리스트 스택의 전체코드는 GitHub 에서 확인하실 수 있습니다.

참조

• 나무위키 - 프루팁스 사진