-
[C언어/자료구조] 스택(Stack)의 개념CS/자료구조&알고리즘 2020. 1. 29. 22:21
※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.
리스트 vs 스택
리스트(List)
- 배열
- 연결리스트
리스트에서 데이터의 삽입/삭제는 어느 위치에서든 할 수 있다(자유롭다)
스택(Stack)
일종의 리스트이지만, 데이터의 삽입/삭제를 한 쪽 끝에서만 할 수 있다(LIFO, Last-In First-Out).
삽입/삭제가 일어나는 쪽을 스택의 top이라고 부른다.
스택의 연산
- push : 스택에 새로운 원소 삽입
- pop : 스택의 top에 있는 원소 제거하고 반환
- peek : 스택 top 원소를 제거하지 않고 반환
- empty : 스택이 비었는지 검사 (예외처리를 위해서)
스택의 응용 예 - 괄호 검사 문제
여는 괄호의 개수 = 닫는 괄호의 개수더라도, 괄호가 올바르지 않을 수 있다. (순서가 틀린 경우)
따라서 스택을 이용해 입력 수식의 괄호가 올바른지 검사한다.
여는 괄호는 스택에 push, 닫는 괄호가 나오면 스택에서 pop한 후 두 괄호가 같은 유형인지 확인하고, 마지막에 스택에 남는 괄호가 없어야 한다.
'CS > 자료구조&알고리즘' 카테고리의 다른 글
[자료구조(C언어)] 점근적 분석의 예시 (0) 2020.01.29 [C언어/자료구조] 시간복잡도와 점근적 분석의 개념 (0) 2020.01.29 [C언어/자료구조] 이중 연결리스트(double linked list) (0) 2020.01.29 [자료구조] 큐(Queue)의 개념 (0) 2020.01.25 [C언어/자료구조] 연결리스트 - 다항식 (0) 2020.01.19