C++ Stack 만들기 (version.2 - GrowableArray Stack)

Stack 만들기 version 2

 

Growable Stack을 C++로 구현해 보도록 하겠다.

자료구조의 저장 공간을 모두 사용해 갈 때 자료구조의 크기를 늘려줌으로써 Overflow와 같은 문제를 예방할 수 있는 array이다. ArrayList가 이런 메커니즘을 가지고 있다.

 

크기가 4인 Stack이 아래와 같이 있다.

 

스택에 1부터 증가하는 값을 넣다보면 아래와 같이 될 것이고 스택은 가득 찬 상태가 될 것이다.

 

 

이 스택의 값을 유지한 채로 값을 더 넣고 싶다면, 현재 스택 사이즈 2배만큼의 배열을 만들어주고 원래 스택에 있는값을 두 배 크기로 만든 스택의 앞부분에 값을 옮겨준다.

 

옮겨 준 자료구조를 이제 스택으로써 사용하면 되고 뒤의 빈 공간은 0으로 초기화 시켜준다.

 

이런식으로 자료구조가 가득 찰 때마다 두배씩 늘려줌으로써 Overflow와 같은 문제는 완전히 예방 할 수 있다.

 

 

메인 함수로 들어가 보겠다.

#include <stdio.h>
#include "Stack.h"

void main() 
{
	/*Stack a;
	a.push(10);
	a.push(20);
	a.push(30);
	int x = a.pop();
	a.push(40);
	printf("%d\n", x);
	printf("%d\n", a.pop());*/

	Stack *a;
	a = new Stack();

	a->push(10);
	a->push(20);
	a->push(30);
	int x = a->pop();
	a->push(40);

	for (int i = 100; i < 120; i++) {
		a->push(i);
	}

	printf("%d\n", x);
	printf("%d\n", a->pop());

	a->print();
	delete a;
}

push와 pop, print 등을 하는 것은 다른 방식의 queue와 같다.

 

#define INIT_SIZE		(4)

class Stack {
	int *s;
	int top;
	int sz;
	void stackEmptyError();
public:
	Stack();
	void push(int x);
	int pop();
	int peek();
	void print();
};

헤더 파일도 마찬가지이다. 

하지만 배열 사이즈를 고정시켜놓고 사용할 것이 아니기 때문에 초기 배열 사이즈를 INIT_SIZE로써 지정해두고 필요할 때마다 사이즈를 늘려나갈 것이다.

그런 이유로 Stack 클래스에 변수 sz(사이즈)가 데이터 멤버로서 추가되었다.

 

#include "Stack.h"
#include <stdio.h>
#include <stdlib.h>

Stack::Stack() 
{
	top = -1;
	sz = INIT_SIZE;

	s = new int[sz];

	for (int i = 0; i < sz; i++) s[i] = 0;
}

void Stack::print()
{
	printf("top = %d\n", top);
	for (int i = 0; i < sz; i++) {
		printf("%d ", s[i]); 
	}
	printf("\n");
}

void Stack::push(int x) 
{
	if (top >= sz-1) {
		int *tmp = new int[sz*2];
		for (int i = 0; i < sz; i++) {
			tmp[i] = s[i];
		}
		for (int i = sz; i < 2*sz; i++) tmp[i] = 0;
		s = tmp;
		sz *= 2;
	}
	top++;
	s[top] = x;
}

int Stack::pop()
{
	if (top == -1) stackEmptyError();

	top--;
	return s[top+1];
}

int Stack::peek()
{
	if (top == -1) stackEmptyError();

	return s[top];
}

void Stack::stackEmptyError()
{
	printf("Stack Empty!!!\n");
	exit(-1);
}

Stack의 constructor에는 top을 -1로 세팅해주고, sz는 INIT_SIZE로, 그리고 배열의 선언 및 초기화 작업을 해준다.

 

print 함수는 배열의 사이즈만큼 값들을 출력주는 용도이다.

 

push 함수는 이제 값을 넣는 index가 sz-1에 해당하면 임시 배열 tmp 를 sz의 2배 크기만큼 생성해준다. tmp에 원래 stack에 있던 값들을 옮겨주고 그 뒷 부분을 0으로 초기화 시켜준다. s는 tmp로 지정해주고 sz도 2배한것 만큼 적용시켜준다.

그리고 top을 1 증가시켜주며 그 위치에 새로운 값을 넣는다.

top 위치가 sz-1보다 작다면 위의 과정은 무시하고 값을 넣어준다.

 

pop과 peek 작업은 growable과 관계없으므로 다른 여느 stack과 같다.

 

이상 growable array 방식의 Stack이다.