[자료구조] 스택 (Stack)

스택 (Stack)

• 후입선출 (Last In First Out; LIFO) 자료구조

    - 마지막에 들어온 데이터가 먼저 나가는 구조

    - First In Last Out (FILO) 라고 하기도 한다.

• 순차적으로 데이터를 추가하고 삭제하기 때문에 ArrayList와 같은 배열 기반의 클래스를 사용하는 것이 적합하다.

스택의 기본 구조

스택의 기본 연산

• push(item) - 스택의 Top에 요소 저장
• pop() - 스택의 가장 마지막 요소를 반환하며 삭제 - 만약 스택이 비어있을 때 pop()을 한다면 EmptyStackException 발생
• peek() - 스택의 가장 마지막 요소를 반환하지만 삭제는 하지 않는다.
• contains(item) - 스택 안에 요소가 있는지 확인
• search(item) - 스택에서 주어진 객체를 찾아서 그 위치를 반환, 못찾으면 -1을 반환 (1부터 시작한다)
• empty() - 스택이 비어있는지 확인
• clear() - 스택의 모든 요소 삭제

스택 시간 복잡도

• 조회: O(N)
• 삽입, 삭제: O(1)