[Theory] Stack

22 Feb 2022

스택(Stack)

후입선출(LIFO:Last In First Out)의 특성을 가지는 자료구조를 말한다.

스택의 연산종류

• Push : 스택에 가장 위에 데이터를 추가합니다. (입력연산)
• Pop : 스택의 가장 위의 데이터 원소를 제거 및 반환합니다. (출력연산)
• Peek : 스택의 맨 위 데이터 원소를 조회합니다. (조회연산)

스택의 시간복잡도

스택 데이터를 삽입하거나 제거시 가장 위의 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 O(1)의 시간복잡도를 가집니다. 하지만 특정 데이터를 조회시 찾을 때까지 수행을 해야 하므로 O(n)의 시간복잡도를 가진다.

스택의 구현

Java에는 Stack의 객체가 Object[]로 구현되어 있지만 자체적으로 Stack객체를 만들어 Stack 자료구조를 구현해 보았다.

• StactNode

Stack 데이터의 노드 객체

• StackList

Stack의 연산 객체