Stack 스택의 개념과 특성들

1. Stack의 정의

- Stack은 쌓아 올린다는 의미로서 마지막에 들어간 데이터가 먼저 나오는 자료구조 

  

입구와 출구가 같다

2. Stack의 기본연산

push - 스택의 맨 위에 데이터 추가

pop  - 스택의 맨 위 데이터의 반환과 + 삭제

peek - 스택의 맨 위 데이터의 반환

empty  - 데이터의 유무 확인

Method	Description
boolean isEmpty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 끼내지는 않음.(비었을 때는 EmptyStackException발생)
Object pop()	Stack의 맨 위에 저장된 객체를 삭제후 반환한다. (비었을 때는 Empty StackException 발생)
Object push(Object item)	Stack에 객체(item)를 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환. 못찾으면 -1을 반환. (배열과 달리 위치는 0이 아닌 1부터 시작)

3. Stack의 특성

1) 상수시간에 i번째 항목에 접근 불가

2) 하지만 스택에서 데이터 추가 삭제 연산은 상수시간 가능(입구와 출구가 같기 때문)

4. Stack의 구현

1) 순수 배열로 구현

2) ArrayList로 구현 ( 배열 기반 )

3) LinkedList로 구현 ( Node 객체 )

4) 자바 라이브러리

     - Stack 클래스 제공 ( vector의 상속, 배열 기반 )

     - LinkedList 클래스 제공 ( Node 객체 )

5. 배열과 연결리스트 기반의 Stack 비교

     

1) 공통점 - 추가, 삭제가 상수시간 연산 가능

2) 배열 기반  - 배열의 크기가 정해져 있기에 데이터가 증가하면 배열을 복사해줘야 하는점

3) 연결 리스트 - 크기에 제한 없음