1. 개념

• 스택(Stack)은 선형 자료구조의 일종으로, 데이터를 일시적으로 저장하는 임시 저장소입니다. 데이터를 쌓아 올리듯이 쌓아서 저장하고, 나중에는 마지막에 저장된 데이터부터 역순으로 차례대로 꺼내어 사용합니다. 이러한 방식을 후입선출(LIFO, Last In First Out)이라고 합니다.

• 자바에서 스택은 자바 컬렉션 프레임워크에서 제공되는 인터페이스인 java.util.Stack 클래스를 사용하여 구현할 수 있습니다. 스택 클래스는 Vector 클래스를 상속받기 때문에, Vector가 가지고 있는 모든 메소드를 상속받아 사용할 수 있습니다.

2. Method

• push(element) : 스택에 원소를 삽입합니다. 삽입한 원소는 스택의 맨 위에 위치하게 됩니다.
• pop() : 스택의 맨 위에 있는 원소를 꺼냅니다.
• peek() : 스택의 맨 위에 있는 원소를 반환합니다. 이 메소드는 원소를 꺼내지 않고도, 현재 스택의 맨 위에 있는 원소를 확인할 수 있습니다.
• empty() : 스택이 비어있는지 확인합니다. 스택이 비어있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
• search(element) : 스택에서 특정 원소를 찾아서, 그 원소가 스택 맨 위에서부터 몇 번째 위치에 있는지 반환합니다.

3. 시간 복잡도

• push(element) : O(1), 스택의 맨 위에 새로운 원소를 추가하기 때문에, 시간 복잡도는 O(1)입니다.
• pop() : O(1), 스택의 맨 위에 있는 원소를 제거하기 때문에, 시간 복잡도는 O(1)입니다.
• peek() : O(1), 스택의 맨 위에 있는 원소를 반환하기 때문에, 시간 복잡도는 O(1)입니다.
• empty() : O(1), 스택이 비어있는지 확인하기 위해서는 스택에 원소가 있는지 없는지 확인하면 되기 때문에, 시간 복잡도는 O(1)입니다.
• search(element) : O(n), 스택의 맨 위에서부터 원소를 찾아야 하기 때문에, 최악의 경우 스택의 모든 원소를 확인해야 합니다. 따라서 시간 복잡도는 O(n)입니다.