스택

스택이란?

한 쪽 끝에서만 자료를 처리할 수 있는 구조로 이루어져있어 흔히, LIFO(Last- In-First-Out) 구조라고 말한다.
스택이 모두 차있는데 데이터를 추가하면 overflow 스택이 비어있는데 데이터를 꺼내는 경우 underflow가 발생하므로 사용시 주의가 필요하다.

연산

• push: 자료를 스택에 추가
• pop: 가장 위에 있는 자료를 꺼내고 스택에서 삭제
• peek or top: 가장 위에 있는 자료를 반환(스택은 유지)
• isEmpty: 스택이 비어있는지 확인
• isFull: 스택이 가득 차있는지 확인
• getSize: 스택의 크기를 반환

시간 복잡도

Operation	Average	Worst
Access	Θ(n)	O(1)
Search	Θ(n)	O(n)
Insert	Θ(1)	O(1)
delete	Θ(1)	O(1)

구현

스택을 구현하는 방법에는 두 가지가 있다.

배열 사용

• 장점 : 구현하기 쉽다.
• 단점: 크기가 동적이 아님. 런타임시 필요에 따라 늘어나거나 줄어들지 않는다.

연결 리스트 사용

• 장점 : 크기가 동적임. 런타임시 필요에 따라 크기가 확장 및 축소될 수 있다.
• 단점 : 포인터를 위한 추가 메모리 공간이 필요하다.