[C++] 동적 배열 스택(Stack) 구조 구현

스택 (Stack)

스택이란

자료의 입출력이 후입선출(Last-in First-Out)인 형태로 구성된 자료구조
가장 늦게 들어온 자료가 가장 먼저 나가게 되는 형태

 

이를 C로 구현해 보면 

#include <iostream>

using namespace std;

#define MAX_STACK_SIZE 100
typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;

int is_empty() {
	return (top == -1);
}

int is_full() {
	return (top == MAX_STACK_SIZE - 1);
}

void push(element item) {
	if (is_full())
	{
		cerr << "스택 포화 에러\n";
		return;
	}
	else
		stack[++top] = item;
}

element pop() {
	if (::is_empty()) {
		cerr << "스택 공백 에러\n"; // cerr을 제대로 사용
		return -1; // 오류 표시를 위해 반환값 설정
	}
	else
		return stack[top--];
}

element peek() {
	if (::is_empty()) {
		cerr << "스택 공백 에러\n";
		return -1;
	}
	else
		return stack[top];
}

int main() {
	push(1);
	push(2);
	push(3);
	cout << pop() << "\n";
	cout << pop() << "\n";
	cout << pop() << "\n";
}

베이스는 C++이지만 기본문법만 다를뿐 C로 바꾸면 가동합니다.

 

스택에는 대표적인 2가지 연산이  있습니다.

push : 값을 추가

pop : 값을 꺼내기

 

하지만 스택도 무한한 메모리가 아니기에 두 연산시에 스택이 비어있는지 가득찼는지 반드시 검사를 해주어야 합니다.

is_Empty와 is_Full로 top가 -1로 비어있는지, top가 스택의 최대 사이즈와 같은지 비교하여 값을 반환합니다.

 

이 스택 코드를 동적할당으로 

#include <iostream>
#include <malloc.h>

using namespace std;

#define MIN_STACK_SIZE 3

typedef int element; //item

//구조체로 스택을 포현
typedef struct {
	element *data;
	int top; //4바이트
	int capacity; //4바이트
}stackType;

//스택 초기화
void init_stack(stackType* s) {
	s->top = -1;
	s->capacity = MIN_STACK_SIZE; //자료가 들어올 수 있는 갯수 최대 3개
	s->data = (element *)malloc(s->capacity * sizeof(element)); //메모리 크기 할당
	if (s->data == NULL) {
		cerr << "메모리 할당 실패\n";
		exit(1);
	}
}

//비었는지 확인
int is_empty(stackType* s) {
	return (s->top == -1);
}

//가득찼는지 확인
int is_full(stackType* s) {
	return (s->top == (s->capacity - 1));
}

//넣기
void push(stackType* s, element item) {
	if (is_full(s))
	{
		// 임시 포인터에 재할당 결과 저장
		element* temp = (element*)realloc(s->data, (s->capacity + 1) * sizeof(element));
		if (temp == NULL) {
			cerr << "메모리 재할당 실패\n";
			exit(1);
		}
		s->data = temp;
		s->capacity += 1; // 용량 증가
		cout << "메모리 오버로 재할당. 새로운 용량: " << (s->capacity * sizeof(element)) << "\n";
	}
	s->data[++(s->top)] = item;
}

//꺼내기
element pop(stackType* s) {
	if (::is_empty(s)) {
		cerr << "스택 공백 에러\n";
		exit(1);
	}
	else {

		// 요소 반환 전에 용량 감소 체크
		element item = s->data[(s->top)--];

		if (s->capacity > MIN_STACK_SIZE) {
			// 임시 포인터에 재할당 결과 저장
			element* temp = (element*)realloc(s->data, (s->capacity - 1) * sizeof(element));
			if (temp == NULL) {
				cerr << "메모리 재할당 실패\n";
				exit(1);
			}
			s->data = temp;
			s->capacity -= 1; // 용량 감소
			cout << "메모리 축소로 재할당. 새로운 용량: " << (s->capacity * sizeof(element)) << "\n";
		}
		return item;
	}
}

//가장 위 아이템 집기
element peek(stackType* s) {
	if (::is_empty(s)) {
		cerr << "스택 공백 에러\n";
		exit(1);
	}
	else
		return s->data[s->top];
}

int main() {
	stackType s;

	init_stack(&s); 
	cout << "현재 s.data의 스택 사이즈: " << (s.capacity * sizeof(element)) << "\n";
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	push(&s, 4);
	push(&s, 5);
	cout << pop(&s) << "\n";
	cout << pop(&s) << "\n";
	cout << pop(&s) << "\n";
	free(s.data);
}

 

결과

 

처음 스택의 크기는 capacity의 초기 최대 스택갯수인 int(4바이트) * capacity(3바이트)로 12바이트가 할당되어있었습니다.

push 1 2 3까지는 메모리가 여유 있기에 오버되지 않고 잘 들어갔을 것 입니다.

 

메모리 (+) 재할당

하지만 4부터는 int형이 4개가 들어가게되어 16바이트가 필요로 하게됩니다.

push에서 is_Full 검사로 가득차게되면 capacity갯수를 1 증가시킨 메모리 크기를 재할당 해주고 있습니다.

그래서 기존 12바이트에서 16바이트로 메모리 크기가 바뀌게 됩니다.

5가 들어가서도 똑같습니다.

 

메모리 (-) 재할당

이제 pop을 시도하는데 현재 스택에는 5까지 들어가있어서 capacity가 2번 증가해 20바이트가 할당되어 있습니다. 필요한 만큼의 메모리크기를 가지고 있기 위해 임시 포인터에 capacity에 1을 뺀 만큼의 16바이트 메모리를 할당해주고 NULL검사로 할당이 제대로 됐을때 data에 할당해주어 메모리 축소로 16바이트의 메모리를 갖고 있는 것을 볼 수 있습니다.

스택의 최소 사이즈는 3으로 해놨기에 4가 pop될때 까지 메모리를 축소시켜주었습니다.

 

메모리에 대한 코드에는 항상 NULL검사를 해주어야 합니다!

 

이렇게 동적으로 필요한만큼의 메모리를 할당해주는 구조체로 스택구조를 활용한 동적할당이였습니다.

 

C언어로 쉽게 풀어쓴 자료구조 프로그램4.5의 동적 할당을 C++ 베이스로 capacity의 크기를 2배로 늘린 코드를 딱 필요한 만큼의 크기만큼 재할당 하는 식으로 고쳐보았습니다.