[25년 03차 / 문제풀이] 스택(Stack)
개념
☐ 스택을 이용한 연산
● 재귀 호출 연산
● 후위 표현 연산
● 깊이 우선 탐색 연산
☐ 스택의 언더플로(Underflow)
if Top = 0 Then
Underflow
Else {
remove S(Top)
Top = Top - 1
}
● Top = 0 : 스택이 비어 있음을 표시 > 항목을 제거하려고 하면 언더플로가 발생하므로 오류 메시지를 표현
☐ 스택의 특성
● 순서가 있는 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조
● 후입선출 방식(LIFO, Last In First Out) : 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 방식
● 스택의 응용 분야
- 함수 호출의 순서 제어
- 인터럽트의 처리
- 수식 계산 및 수식 표기법
- 컴파일러를 이용한 언어 번역
- 부 프로그램 호출 시 복귀주소 저장
- 서브루틴 호출 및 복귀 주소 저장
- 인터럽트 처리, 서브루틴 호출 작업 등에 응용
● 스택의 이상
- 오버플로(Overflow) : 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로가 발생
- 언더플로(Underflow) : 더이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로가 발생
☐ 스택 연산의 출력 결과
● 후입선출(LIFO) 방식 사용
● push : 데이터를 넣는 것
● pop : 데이터를 빼는 것
● 예시 : A, B, C, D - push, push, pop, push, push, pop, pop, pop 순서
- push : A를 push - 스택 : [A]
- push : B를 push - 스택 : [A, B]
- pop : B를 pop - 출력 : B, 스택 : [A]
- push : C를 push - 스택 : [A, C, D]
- pop : D를 pop - 출력 : D, 스택 : [A, C]
- pop : C를 pop - 출력 : C, 스택 : [A]
- pop : A를 pop - 출력 : A, 스택 : []
- 출력 : B, D, C, A
문제
☐ 스택을 이용한 연산
2021년-2차 40번. 다음 중 스택을 이용한 연산과 거리가 먼 것은?
① 선택 정렬
② 재귀 호출
③ 후위 표현(Post-Fix Expression)의 연산
④ 깊이 우선 탐색
정답 : 1
입력 답 : 4
☐ 스택의 언더플로(Underflow)
2021년-3차 27번. 다음은 스택의 자료 삭제 알고리즘이다. Ⓐ에 들어갈 내용으로 옳은 것은? (단, Top : 스택포인터, S : 스택의 이름)
<보기>
if Top = 0 Then ( ⓐ ) Else { remove S(Top) Top = Top - 1 }
① Overflow
② Top = Top + 1
③ Underflow
④ Top = Top
정답 : 3
입력 답 : 4
☐ 스택의 특성
2022년-1차 23번. 스택(Stack)에 대한 옳은 내용으로만 나열된 것은?
<보기>
ㄱ. FIFO 방식으로만 처리된다.
ㄴ.순서 리스트의 뒤(Rear)에서 노드가 삽입되며, 앞(Front)에서 노드가 제거된다.
ㄷ. 선형 리스트의 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조이다.
ㄹ. 인터럽트 처리, 서브루틴 호출 작업 등에 응용된다.
① ㄱ, ㄴ
② ㄴ, ㄷ
③ ㄹ
④ ㄱ, ㄴ, ㄷ, ㄹ
정답 : 3
입력 답 : 1
2022년-2차 39번. 순서가 있는 리스트에서 데이터의 삽입(Push), 삭제(Pop)가 한쪽 끝에서만 일어나며 LIFO(Last_In-First_Out)의 특징을 가지는 자료 구조는?
① Tree
② Graph
③ Stack
④ Queue
정답 : 3
입력 답 : 4
2022년-3차 29번. 스택(STACK)의 응용 분야로 거리가 먼 것은?
① 인터럽트의 처리
② 수식의 계산
③ 서브루틴의 복귀 번지 저장
④ 운영체제의 작업 스케줄링
정답 : 4
입력 답 : 2
☐ 스택 연산의 출력 결과
2022년-1차 35번. 순서가 A, B, C, D로 정해진 입력 자료를 push, push, pop, push, push, pop, pop, pop 순서로 스택 연산을 수행하는 경우 출력 결과는?
① B D C A
② A B C D
③ B A C D
④ A B D C
정답 : 1
입력 답 : 2
<풀이>
- push : A를 push - 스택 : [A]
- push : B를 push - 스택 : [A, B]
- pop : B를 pop - 출력 : B, 스택 : [A]
- push : C를 push - 스택 : [A, C, D]
- pop : D를 pop - 출력 : D, 스택 : [A, C]
- pop : C를 pop - 출력 : C, 스택 : [A]
- pop : A를 pop - 출력 : A, 스택 : []
- 출력 : B, D, C, A