개념

데이터를 쌓아 올리는 저장 방식을 가지고 있는 선형 자료구조

• 나중에 들어온 데이터가 가장 먼저 나오는 후입선출
• LIFO(LastInFirstOut) 이라고 한다.

기능

push()

데이터를 저장하는 기능

• resize()는 스택 내부 배열의 크기가 가득 찼을 때 용량을 늘려주는 메서드이다.

• 처음 비어있는 스택이 생성되면 top의 값은 -1을 가리키고 있다.

• 전위 연산자를 통해서 top을 먼저 1 증가 시키고 해당 위치에 element를 저장한다.

resize()

• top의 값은 마지막 저장한 요소의 인덱스이다.
• 마지막 저장한 요소의 인덱스 top이 스택 내부 배열의 마지막 인덱스와 같다면 배열의 용량을 늘려준다.
• Arrays.copyOf()를 사용해 elementData가 참조하고 있는 배열의 크기를 늘리고 기존에 저장된 데이터를 복사하여 다시 elementData로 참조 시켜 준다.

pop()

마지막 데이터를 꺼내고 삭제하는 기능

• 스택이 비어있다면 예외를 발생시킨다.

• 현재 top은 마지막 요소가 저장된 인덱스를 가리키고 있다.

• 먼저 마지막 위치에 저장되어 있는 데이터를 반환한다.

• 마지막 인덱스 값을 null로 할당하여, 저장되어 있던 객체가 가비지 컬렉션에 정리될 수 있게 참조를 끊어 준다.

• 후위 연산자를 통해 먼저 마지막 인덱스의 값을 null로 할당하고 그 이후에 top의 인덱스 값을 조정시켜준다.

• top은 이제 기존의 마지막에서 두번째 요소를 마지막 요소로 가리킨다.

peek()

데이터를 꺼내고 삭제하지 않고, 조회만 하는 기능

• 스택이 비어있다면 예외를 발생시킨다.
• top은 현재 마지막 요소의 위치를 저장하고 있는 값으로 바로 배열로 꺼내 반환한다.

isEmpty()

스택이 비어있는지 검사한다.

• top이 0보다 작다면 스택이 비어있다고 정의한다.

init()

스택을 초기화 한다.

• top을 -1로 변경한다.
• 기존에 elementData 변수가 참조하던 배열 값을 참조연결을 해제해주고 기본 크기의 배열을 생성하여 다시 참조를 연결해준다.

시간복잡도

push와 pop 모두 O(1)이다.

배열 VS 연결리스트

배열은 push, pop 모두 O(1)이지만, 배열이 가득 찼을 경우 더 큰 배열을 생성하여 복사하는 비용이 발생한다.