자료구조 4장 스택(STACK)

스택이란?

• 스택이란 일종의 리스트
• 단, 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어짐
• LIFO(Last-In, First-Out)
• 삽입/삭제가 일어나는 쪽을 스택의 top이라고 부름

스택이 지원하는 연산

• push : 스택에 새로운 원소를 삽입
• pop : 스택의 top에 있는 원소를 스택에서 제거
• top 혹은 peek : 스택 top의 원소를 제거하지 않고 반환
• empty : 스택이 비어있는지 검사
• size : 저장된 원소의 개수를 반환

스택 응용 예 : 괄호 검사 문제

입력 수식의 괄호가 올바른지 검사

 

예) [a + b * {c / ( d - e ) } ] + ( d / e ) 

 

단순히 여는 괄호와 닫는 괄호의 개수 비교 만으로는 부족해 스택을 이용해서 검사합니다.

• 여는 괄호는 스택에 push
• 닫는 괄호는 스택 top과 같은 유형의 괄호인지 검사한 후 스택에서 pop한다.
• 마지막에 스택에 남는 괄호가 없어야