스택(Stack) - 배열로 구현하기

 

papago 번역

스택은 쌓아올린것을 뜻합니다.

일반적으로 쌓아 올린 것은 밑에서 부터 빼면 균형이 무너지지요. 식당에 컵을 보관하는 장치를 떠올려 보면 편합니다.

 

 

이러한 컵 보관함은 아래에 있는 컵을 꺼내려면 위에 있는 컵을 제거 해야만 합니다.

또는 이런 주차장을 상상해 보면 됩니다.

가장 안쪽에 있는 자동차가 나가려면 앞에 있는 차들을 모두 빼야 합니다.

전에 제가 일했던 회사에서는 주차장이 작고 이중삼중주차가 일상인 곳이라 모두 차키를 차안에 두고 다녔던 기억이 있네요.

 

 

스택은 삽입과 제거 연산이 핵심입니다.

 

삽입은 맨 위에 하나를 더 쌓는 일이고, 제거는 맨위에 있는 데이터를 하나 걷어 내는 일이죠.

배열기반으로 먼저 스택을 구현 해 보겠습니다.

 

---

배열 기반으로 스택 구현하기

 

배열 기반의 Stack인 ArrayStack 에는

Capacity , Top , Node* 가 필요합니다.

Capacity 는 배열의 크기, Top은 현재 가장 위에 있는 데이터 입니다.

Node*는 배열의 첫번째 요소의 위치를 담은 포인터입니다. 배열은 첫번째 위치만 알면 다른 구성원에게 접근하는 것이 자유롭기 때문에 첫번째 위치만 가지고 있도록 합니다.

typedef int ElementType;
typedef struct STNode
{
	ElementType Data;
}Node;

typedef struct STArrayStack
{
	int Top;
	int Capacity;
	Node* Nodes;
}ArrayStack;

Node의 맴버는 Data 뿐입니다. 접근하는데 필요한 요소는 Node* Nodes에서 전부 처리 가능하기 때문입니다.

 

스택 생성하기

void AS_CreateStack(ArrayStack** Stack, int Capacity)
{
	//스택을 Heap 영역에 생성합니다.
	(*Stack) = new ArrayStack;
	//스택의 맴버들을 초기화 합니다.
	//스택의 맴버중 Nodes는 동적으로 Capacity만큼 크기를 할당받은 배열입니다.
	(*Stack)->Nodes = new Node[Capacity];
	(*Stack)->Capacity = Capacity;
	(*Stack)->Top = -1;
}

스택을 생성합니다. 스택의 구성원으로는 Node들의 배열이 있고(실제 데이터들이 존재하는 부분입니다.)

해당 배열의 크기를 뜻하는 Capacity(Capacity는 생성 될 때 매개변수로 받게 됩니다.)

그리고 현재 가장 위에 있는 데이터의 위치를 뜻하는 Top가 있습니다.

생성과 동시에 -1 로 초기화가 되는데요, 이 이유는 프로그래밍 언어에서 배열의 Index가 0부터 시작하기 때문입니다.

데이터가 하나도 없을 때는 -1이어야 하는 것이죠.

스택 그 자체에는 데이터를 담는 그릇(배열)과 스택의 상태를 나타내 주는 맴버들로 구성되어 있음을 알 수 있습니다.

스택 소멸시키기

void AS_DestroyStack(ArrayStack* Stack)
{
	//Nodes 배열을 해제 합니다.
	delete[](Stack->Nodes);
	//Stack이 가리키는 주소를 해제 합니다.
	delete(Stack);
}

여기서는 스택 자체를 할당 해제 시키기 전에 동적으로 할당받은 Nodes 배열 부터 해제 해주고, 스택 본체를 해제 한다는 점만 기억하면 됩니다.

c++ 에서는 delete[] 와 같이 사용하면 똑똑하게 배열 전체가 delete 됩니다.

 

노드 삽입 하기

자, 이제 스택의 구성원 중 실질적인 데이터에 해당하는 Nodes 를 활용하여 노드를 삽입하는 연산을 구현해 봅시다.

void AS_Push(ArrayStack* Stack, ElementType NewData)
{
	Stack->Top++;	
	Stack->Nodes[Stack->Top].Data = NewData;
}

데이터를 스택에 삽입하는 것을 밀어넣는다고 해서 Push라고 합니다.

그래서 Push의 동작 방식 을 보면 Top의 값을 먼저 증가 시킨 뒤에 Nodes 배열중에서 Top 번째 구성 요소에 있는 데이터를 매개 변수로 받은 NewData로 설정해주는 과정을 볼 수 있습니다.

위 코드는 정확하게 동일한 의미를 가지는 아래와 같은 코드로 교체하는 것도 가능 합니다.

void AS_Push(ArrayStack* Stack, ElementType NewData)
{
	Stack->Nodes[++(Stack->Top)].Data = NewData;
}

 

노드 꺼내기

노드를 꺼내는것을 Pop 이라고 합니다. Pop은 팝콘에서 뜻을 유추할 수 있듯이, 영어로 튀어오르는 것을 표현한 의태어에 가깝습니다. 아무튼 스택에서 데이터를 꺼내는 작업을 영어권에서는 Pop 이라고 합니다.

ElementType AS_Pop(ArrayStack* Stack)
{
	int Position = Stack->Top--;
	return Stack->Nodes[Position].Data;
}

Node AS_PopNode(ArrayStack* Stack)
{
	int Position = Stack->Top--;
	return Stack->Nodes[Position];
}

노드를 꺼낼 때는 노드에 있는 데이터를 꺼낼 수도 있고 노드 그 자체를 꺼낼 수도 있겠지요.

위 코드를 굳이 명시적으로 Position을 사용하지 않고 한줄로 줄여 보면 이렇게 표현할 수도 있습니다.

ElementType AS_Pop(ArrayStack* Stack)
{	
	return Stack->Nodes[--(Stack->Top)].Data;
}

Node AS_PopNode(ArrayStack* Stack)
{
	return Stack->Nodes[--(Stack->Top)];
}

두 코드는 완벽하게 동일한 동작을 수행합니다. 위의 코드는 Position이라는 변수를 사용해서 Stack->Top의 크기를 줄인다는 점을 좀더 명확하게 표현해준 대신 코드의 길이가 길어졌습니다.

위의 경우 한줄 코드가 늘어난다고해서 성능에 큰 차이가 있는 것은 아니라서 가독성이나 유지보수 측면을 고려해서 둘중 하나를 선택하는 경우가 좋겠습니다.

---

ArrayStack.h 헤더 파일 입니다. 

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H
#include <cstdio>
#include <cstdlib>

typedef int ElementType;
typedef struct STNode
{
	ElementType Data;
}Node;

typedef struct STArrayStack
{
	int Top;
	int Capacity;
	Node* Nodes;
}ArrayStack;

void AS_CreateStack(ArrayStack** Stack, int Capacity);
void AS_DestroyStack(ArrayStack* Stack);
void AS_Push(ArrayStack* Stack, ElementType Data);
ElementType AS_Pop(ArrayStack* Stack);
ElementType AS_Top(ArrayStack* Stack);
int AS_GetSize(ArrayStack* Stack);
int AS_IsEmpty(ArrayStack* Stack);

#endif // !ARRAYSTACK_H

함수 선언부분만 따로 복사하여 ArrayStack.cpp 파일로 이동합니다.

ArrayStack.cpp 파일을 이렇게 만들어 놓고 정의부를 완성해 봅니다. 최대한 답을 보지 않고 혼자서 구현 해 보는 연습을 반복해서 하도록 합니다.

배열은 가져오고, 값을 복사하는 과정 자체가 간단하기 때문에 알고리즘이 링크드리스트에 비하면 매우 간단합니다.

 

아래는 완성한 ArrayStack.cpp 파일입니다.

#include "ArrayStack.h"

void AS_CreateStack(ArrayStack** Stack, int Capacity)
{
	(*Stack) = new ArrayStack;
	(*Stack)->Nodes = new Node[Capacity];
	(*Stack)->Capacity = Capacity;
	(*Stack)->Top = -1;	
}
void AS_DestroyStack(ArrayStack* Stack)
{
	delete[] Stack->Nodes;
	delete(Stack);
}
void AS_Push(ArrayStack* Stack, ElementType Data)
{
	Stack->Nodes[++(Stack->Top)].Data = Data;
}
ElementType AS_Pop(ArrayStack* Stack)
{
	return Stack->Nodes[--(Stack->Top)].Data;
}
ElementType AS_Top(ArrayStack* Stack)
{
	return Stack->Top;
}
int AS_GetSize(ArrayStack* Stack)
{
	return Stack->Top + 1;
}
int AS_IsEmpty(ArrayStack* Stack)
{
	return (Stack->Top == -1);
}