스택

개발 초보 2022. 6. 27. 18:55

스택 알아보기

스택(stack)은 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(Last In First Out ; LIFO)다. 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. 스택에 데이터를 넣는 작업을 푸시(push)라 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라 한다. 스택은 마치 상자를 차곡차곡 쌓는 것처럼 데이터를 넣고 위에서부터 꺼낸다. 이렇게 푸시와 팝이 이루어지는 쪽을 꼭대기(top)라 하고, 가장 아래쫏을 바닥(bottom)이라 한다.

스택 만들기

기본 구조를 익히기 위해 스택을 생성할 때 용량(스택에 쌓을 수 있는 최대 데이터 수)을 결정하는 고정 길이 스택을 만든다. 여기서 스택은 int형이다.

스택용 배열 stk

푸시된 데이터를 저장하는 스택용 배열이다. 인덱스 0인 요소가 스택의 바닥이다. 가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0]이다.

스택 용량 capacity

스택의 용량을 나타내는 int형 필드다.

스택 포인터 ptr

스택에 쌓여 있는 데이터 수를 나타내는 필드다. 이 값을 스택 포인터(stack pointer)라 한다. 스택이 비어 있으면 ptr값은 0이 되고, 가득 차 있으면 capacity값과 같다.

생성자 IntStack

생성자는 스택용 배열 본체를 생성하는 등 준비 작업을 한다. 생성할 때 스택은 비어 있으므로 ptr값을 0으로 한다. 그리고 매개변수 maxlen으로 전달받은 값을 capacity에 대입하고 요솟수가 capacity인 배열 본체를 생성한다. 따라서 스택용 배열 본체의 개별 요소에 접근하는 인덱스식은 바닥부터 stk[0], stk[1], ..., stk[capacity - 1]이 된다.

푸시 메서드 push

스택에 데이터를 푸시하는 메서드다. 스택이 가득 차 푸시할 수 없는 경우 예외 OverflowIntStackException을 내보낸다. 예외 처리를 빼면 실질적으로 1행만으로 된 메서드다. 전달받은 데이터 x를 배열 요소 stk[ptr]에 저장하고 ptr값을 1 증가시킨다. 메서드의 반환값은 푸시한 값이다.

팝 메서드 pop

스택의 꼭대기에 있는 데이터를 팝(제거)하고 그 값을 반환하는 메서드다. 스택이 비어 있어 팝을 할 수 없는 경우 예외 EmptyIntStackException을 내보낸다. 푸시와 마찬가지로 실질적으로 1행만으로 된 메서드다. 먼저 ptr값을 1 감소시키고 그때 stk[ptr]에 저장되어 있는 값을 반환한다.

피크 메서드 peek

스택의 꼭대기에 있는 데이터를 '들여다보는' 메서드다. 스택이 비어 있으면 예외 EmptyIntStackException을 내보낸다.

스택이 비어 있지 않으면 꼭대기에 있는 요소 stk[ptr - 1]을 반환한다. 이때 데이터를 넣거나 빼지 않으므로 스택 포인터는 변화시키지 않는다.

스택의 모든 요소를 삭제하는 메서드 clear

스택에서 푸시하고 팝하는 모든 작업은 스택 포인터를 바탕으로 이루어진다. 따라서 스택의 배열 요솟값을 변경할 필요가 없다. 모든 요소를 삭제하는 작업은 ptr값을 0으로 하면 된다.

검색 메서드 indexOf

스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되었는지, 포함되었다면 배열의 어디에 들어 있는지를 조사하는 메서드다. 검색은 꼭대기부터 바닥으로 선형 검색을 수행한다. 즉, 배열 인덱스가 큰 쪽부터 작은 쪽으로 스캔한다. 꼭대기부터 스캔하는 이유는 '먼저 팝이 되는 데이터'를 찾기 위해서다. 검색에 성공하면 찾아낸 요소의 인덱스를 반환하고, 실패하면 -1을 반환한다.

용량을 확인하는 메서드 getCapacity

스택의 용량을 반환하는 메서드로, capacity값을 그대로 반환한다.