자바 Stack 스택 개념 정리

바킹독 스택 개념을 보고 정리한 글입니다

스택

스택은 먼저 들어간 애가 나중에 나오는 구조다 FILO 구조 

 

스택의 성질

1.원소의 추가가 O(1)

2.원소의 제거가 O(1)

3.제일 상단의 원소 확인이 O(1)

4.제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가

 

스택 구현

배열, 연결리스트로 구현 가능

 

스택을 배열로 구현할 때는 원소를 담은 큰 배열 한 개와 인덱스를 저장할 변수 한 개만 필요하다.

pos 값이 스택의 길이, 즉 스택 내의 원소의 수를 의미함

 

push 함수

pos 값 +1 증가

 

pop 함수

pos값만 1 줄이면 된다. 나중에 원소를 넣는다면 arr[pos]에 원소가 들어가면서 알아서 값이 바뀐다

 

top 함수

제일 위의 원소를 확인하는 top 함수다

 

STL stack을 쓸 수 있으면 쓰는 것이 좋다.

 

런타임 에러 발생 -> 스택이 비어있는데 top이나 pop을 하진 않았는지 의심해볼 것

 

스택 기본 선언

Stack<Integer> stack = new Stack<>();

 

스택 메서드 정리

push(T t)

데이터를 스택에 추가하고, 해당 값을 반환

 

peek()

스택의 마지막 요소를 반환, 스택에는 영향 X

스택이 비어있는데 peek() 메서드 호출시 NoSuchElementException 예외가 발생

 

pop()

스택의 마지막 요소를 제거함과 동시에 해당 값 반환

 

empty()

스택이 비어있는지의 여부를 반환, 비어있을 경우 true, 비어있지 않을 경우 false 반환

 

출처