STACK
스택은 가장 먼저 입력된 데이터가 맨 아래 쌓이고 가장 최근에 입력된 데이터는 가장 위에 쌓이는 구조를 가지고 있다. 즉 LIFO(Last In, Final Out) 구조를 가진다.
특징
- 후입선출 구조
- 깊이 우선 탐색에 이용
- 재귀 함수의 동작흐름과 같은 구조를 가진다
- 단방향 입출력 구조
연산
- PUSH : 데이터를 삽입하는 PUSH 연산
- POP : 데이터를 삭제하는 POPUP 연산
활용
- 역순 표기
- 브라우저 뒤로가기 undo/redo
구현방법
- 배열 기반 구현
- 연결 리스트 구현
스택 시간 복잡성
- 스택의 배열 기반 구현에 대해 Push와 Pop 연산은 상수 시간, O(1)이 걸린다.
Java Stack
- 자바의 Stack 클래스는 Vector클래스를 상속 받기에 Thread-Safe 하다.
- 스택 선언 및 함수
- ?