1. 정의
- LIFO(Last In First Out) 순서를 따르는 선형 자료 구조.
- 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조.
2. 스택의 시간 복잡도
- push, pop, isEmpty, peek 모두 O(1) 시간이 걸림. 항상 Top에서만 일어나기 때문
| Operation |
Worst Time |
| Read(Access) |
O(n) |
| Search |
O(n) |
| Insert |
O(1) |
| Delete |
O(1) |
3. 특징
- 자바의 ArrayDeque 를 사용한다면 스택의 크기는 무한이다.
| Operation |
Worst Time |
| push |
스택에 자료 넣기 |
| pop |
스택에서 자료 빼기 |
| peek or top |
스택 top 자료 확인 |
| isEmpty |
스택이 비었는지 확인 |
| isFull |
스택이 가득 찼는지 확인 |
| size |
스택 크기 확인 |
4. 스택을 사용하는 경우
5. java.util.Deque
- Stack 클래스를 사용하지 않고 Deque 클래스를 사용한다.
public static void main(String[] args) throws IOException{
Deque<T> deque = new ArrayDeque<>();
deque.push(T);
T popValue = deque.pop();
T peekValue = deque.peek();
deque.isEmpty();
deque.size();
}
6. 왜 Deque 를 사용하는가