Stack

stack : LIFO 인 선형 구조. 한 쪽 끝에서만 자료를 넣고 뺄 수 있음.

pop() : 스택의 가장 윗 데이터를 삭제.
push() : 스택의 가장 윗 데이터로 top이 가리키는 자리 위에 메모리 생성 후 데이터를 넣는다.
peek() : 스택의 가장 윗 데이터를 삭제하지 않고 반환.
empty() : 스택이 비었다면 1 반환 아니면 0 반환.

stack의 시간 복잡도
push(), pop(), isEmpty(), peek() 모두 O(1) 시간이 걸린다.
-> 삽입 삭제는 항상 top에서만 일어나기 때문.

자바에서 stack은 대부분의 조건에서 성능 저하를 일으키기 때문에 사용을 지양한다. -> 그 해결책으로 deque의 구현체를 사용한다.

스택은 클래스, deque는 인터페이스 -> 객체지향관점에서 deque가 더욱 많은 유연성을 지원 (자바는 다중 상속을 지원하지 않기 때문)

deque 는 양방향 대기열을 지원함으로써 스택과 큐를 사용할 수 있다.