스택이란?
스택이 무엇인지 살펴보기 전에 먼저 사전적 의미부터 알아보자
사전적 의미로는 (물건이 쌓여있는) 더미라고 한다.
물건이 쌓여있다면 내가 제일 먼저 놓은 물건 위에 또다른 물건들이 쌓이고 쌓이다보면 결국 최근에 놓은 물건을 먼저 빼내고, 제일 먼저 놓은 물건은 제일 나중에 빼낼 수 있을 것이다.
그래서 스택이 가장 최근에 들어온 입력이 가장 위에 위치하고, 가장 먼저 나가게되는 후입선출 방식(LIFO, Last-In First-Out)을 특성으로 가진다.
스택을 사용하는 이유 중 하나는 실제 현실세계의 시스템을 표현하기 위해서이기도 하다.
후입선출을 특징으로 가지고 있는 알고리즘에서 필수적으로 사용한다.
ex) 계산, 복잡한 미로에서 길 찾는 알고리즘, 트리나 그래프 같은 복잡한 다른 자료구조에서 내부적으로 사용 등
스택 구조
스택은 앞서 배운 리스트와 같은 선형 자료 구조이다.
입출력은 맨 위에서만 일어나고, 중간에서는 데이터를 삭제할 수 없다.
요소(element) : 스택에 저장되는 것
push : 새로운 자료를 스택에 추가하는 과정
pop : 스택에 저장된 자료를 가져오는 과정
-> 자료 제거 및 자료 가져오기 연산이 동시에 수행
peek : 기존 자료 제거하지 않고 자료 가져오는 과정
C코드로 스택 구현
1번째 스택 ADT 정의
create() : 스택을 생성
is_full(s) : 스택이 포화상태인지 검사
is_empty(s) : 스택이 공백상태인지 검사
push() : 스택에 데이터를 추가
pop() : 스택에서 데이터를 삭제
peek(s) : 요소를 스택에서 삭제하지 않고 반환
2번째 C코드 작성
스택 응용
<<괄호 검사 문제>>
- 프로그램에서 사용되는 괄호가 올바르게 사용되었는지를 스택을 사용하여 검사하는 프로그램
- 대괄호 [] , 중괄호{} , 소괄호() 등
검사 조건
- 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같음
- 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함
- 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안됨
괄호 검사할 때 문자가 나와도 무시하고 괄호들만 스택에 넣으면 된다.
- 정상 수식
왼쪽 괄호부분이 나오면 스택에 저장한다
오른쪽 괄호부분이 나오면 스택에 저장되어 있는 top에 있는 왼쪽 괄호와 비교하고, 같으면 top에 있던 데이터 삭제
위의 두 줄을 반복한다.
스택에 데이터가 다 사라지면 성공!
- 비정상 수식
1) 정상수식과 마찬가지로 진행하다가 스택에 데이터가 남아있으면 오류이다.
2) 정상수식과 마찬가지로 진행하다가 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호를 비교하게 되면, Return 0 되어 프로그램 종류되어 오류이다.
'자료구조' 카테고리의 다른 글
| [C 자료구조] 큐(Queue) (0) | 2021.04.12 |
|---|---|
| [C 자료구조] 리스트 (0) | 2021.03.29 |
댓글