동적 배열을 사용하는 스택

이전 글에서 설명한 스택 구현의 단점은 스택이 얼마나 크게 될지 그 범위(MAXSIZE)를 미리 알아야 된다는 것이다. 이 단점은 동적으로 할당된 배열을 이용하고 필요할 때 이 배열의 크기를 증대시킴으로써 극복할 수 있다.

스택이 비는 경우와 스택이 가득 차는 경우 중, 스택이 비는 경우는 top == -1로 기존과 같다. 따라서 함수 pop은 수정할 필요가 없다.

하지만 함수 push의 코드는 변경해 주어야 한다. 기존에는 에러 메시지를 출력하고 프로그램을 종료했다면, 새로운 코드는 배열 stack의 크기를 확장시켜서 스택에 원소를 추가로 삽입할 수 있도록 한다.

이때 배열의 크기를 확장시키기 전에 새로운 크기를 결정해야 된다. 배열 배가(array doubling)에서는 배열의 크기를 늘릴 필요가 있을 때는 항상 배열 크기를 2배로 만든다. lozenia64/DataStructuers C로 쓴 자료구조론.

Contribute to lozenia64/DataStructuers de...