스택은 아래에서부터 위로 쌓아 얹어 올리도록 하는 자료구조이다. 중간에 데이터를 삽입하거나 삭제하는 것을 허용하지 않는다. 데이터의 입/출력은 오로지 스택의 꼭대기에서만 이루어진다. 스택에서 가장 마지막에 들어간 데이터가 제일 먼저 나오고(Last In - First Out) 가장 먼저 들어간 데이터는 나중에 나오게(First-In - Last Out)된다.
즉, 이런 구조를 일컬어 FILO, LIFO이라고 부르는데, 요소의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어지는 것이 특징이다.
스택의 주요 기능
삽입(Push)과 제거(Pop) 두 가지 뿐이다. 그 외 기능들은 이들 두 연산을 위한 보조 연산에 지나지 않는다.
삽잆 연산은 스택 위에 새로운 노드(또는 요소)를 '쌓는' 작업이다.
링크드 리스트로 구현하는 스택
삽입(Push) 연산
링크드 리스트 버전의 삽입 연산은 링크드 리스트의 추가 연산과 비슷하다. 최상위 노드(테일)를 찾은 다음, 여기에 새 노드를 얹기만 하면 된다. 이렇게 하면 새 노드가 최상위 노드가 된다.
제거(Pop) 연산
링크드 리스트 기반의 스택에서 제거 연산은 다음 네 단계로 수행된다.
1. 현재 최상위 노드의 주소를 다른 포인터
2. 새로운 최상위 노드, 즉 현재 최상위 노드의 바로 이전 노드를 찾는다.
3. LinkedListStack 구조체의 Top 필드에 새로운 최상위 노드의 주소를 등록한다.
4. (1)에서 포인터에 저장해둔 옛 최상위 노드의 주소를 반환한다.
수식의 중위 표기법과 후위 표기법
후위 표기식을 계산하는 알고리즘
피연산자인 1 스택에 삽입 > 두 번째 요소도 피연산자이므로 스택에 삽입 > 세 번째 요소도 스택에 삽입 2
연산자가 나왔을 경우 스택에서 피연산자 두 개를 꺼내 연산 실행 > 그 연산 결과 다시 스택에 삽입
스택에서 후위 표기법으로 바꾸는 법
'C++ > 뇌를 자극하는 알고리즘' 카테고리의 다른 글
| 5장 정렬 (0) | 2022.02.14 |
|---|---|
| 4장 트리 (1) | 2022.02.02 |
| 3장 큐 (0) | 2022.02.02 |