[선형구조] 스택(Stack)

 

외우자. 프링글스는 스택이다.

 

스택이란 LIFO(Last In, First Out) 선입후출 형태를 가지는 자료 구조이다.

 

스택에서 새로운 데이터를 삽입하는 것을 PUSH 연산

 

데이터를 삭제하는 것을 POP 연산이라고 한다.

 

그리고 맨 위의 값을 보는 것을 TOP 연산이라고 한다.

 

 

추가적으로 스택이 Empty 상태일 때, pop이나 top 연산을 하게 되면

Underflow, 즉 예기치 않은 연산으로 취급한다.

 

스택은 특정 쪽에서만 삽입, 삭제 연산이 이루어지므로 연결 리스트로 구현해야 한다.

그리고 push, pop, top 연산은 O(1)이 된다.