한국어
메뉴

스택(Stack)란?

마지막에 넣은 원소를 가장 먼저 꺼내는 후입선출(LIFO) 자료 구조. 원소를 쌓는 조작을 push, 꺼내는 조작을 pop이라고 한다. 함수 호출의 복귀 주소나 지역 변수의 관리(콜 스택), 역폴란드 표기법의 수식 계산, 깊이 우선 탐색 등에 쓰인다.

일본어 명칭: スタック

스택(Stack)은(는) ISA와 어셈블리, 링커, 로더, 실행 파일, 자료 구조와 알고리즘 등 8개 분야의 연습 문제 34개에 나와요.

분야: 자료 구조와 알고리즘

도전해 보기: 스택(Stack) 관련 문제

다른 함수를 호출하지 않는 함수(리프 함수)에서는 ra를 스택에 저장하지 않아도 되는 경우가 많다. 그 이유로 올바른 것은?

  1. A리프 함수에서는 ret 명령어를 사용하지 않기 때문
  2. B리프 함수의 복귀 주소는 CPU가 자동으로 스택에 쌓기 때문
  3. C다른 함수를 호출하지 않으므로 ra가 덮어써지지 않아 복귀 주소가 그대로 남아 있기 때문
정답과 해설 보기

정답: C. 다른 함수를 호출하지 않으므로 ra가 덮어써지지 않아 복귀 주소가 그대로 남아 있기 때문

ra는 함수를 호출하는 jal마다 덮어써지므로, 다른 함수를 호출하는 함수는 자신의 복귀 주소를 처음에 스택에 저장해야 합니다. 리프 함수는 jal을 사용하지 않으므로 ra가 망가지지 않아 저장 없이 ret할 수 있습니다. 게다가 호출 대상 저장 레지스터도 사용하지 않는다면 스택 프레임을 만들 필요조차 없습니다. x86의 call 명령어는 복귀 주소를 반드시 스택에 쌓으므로 이 점이 RISC-V와의 차이입니다.

RISC-V에서 자기 자신을 호출하는 재귀 함수를 작성할 때 ra를 스택에 저장하는 것을 잊으면 어떻게 되는가?

  1. A안쪽 호출에서 ra가 덮어써져 바깥쪽 함수가 올바른 호출 원본으로 복귀하지 못하게 된다
  2. BCPU가 자동으로 ra를 저장하므로 아무 문제도 일어나지 않는다
  3. C재귀의 깊이와 관계없이 계산 결과가 2배가 된다
정답과 해설 보기

정답: A. 안쪽 호출에서 ra가 덮어써져 바깥쪽 함수가 올바른 호출 원본으로 복귀하지 못하게 된다

재귀 호출의 jal은 ra를 '자신 안의 호출 다음 명령어'로 덮어씁니다. 저장하지 않으면 바깥쪽 함수가 ret할 때 원래 호출 원본이 아니라 자신 안으로 되돌아가 버려 같은 곳을 반복하거나 오동작합니다. 그래서 다른 함수를 호출하는 함수는 프롤로그에서 ra를 스택에 저장하고 에필로그에서 되돌리는 것이 규칙입니다.

해설 속 스택(Stack)

스택(Stack)이(가) 나오는 문제 (34)

  1. 다른 함수를 호출하지 않는 함수(리프 함수)에서는 ra를 스택에 저장하지 않아도 되는 경우가 많다. 그 이유로 올바른 것은?
  2. RISC-V에서 자기 자신을 호출하는 재귀 함수를 작성할 때 ra를 스택에 저장하는 것을 잊으면 어떻게 되는가?
  3. 프로세스의 힙과 스택을 사이에 넓은 빈 공간을 두고 반대 방향으로 늘어나는 배치로 하는 이점으로 올바른 것은 무엇입니까?
  4. 재귀가 너무 깊어져 스택 상한을 넘었을 때 Linux 등에서 일반적으로 일어나는 일로 올바른 것은 무엇입니까?
  5. MMU가 없는 작은 마이크로컨트롤러에서 스택 과다 사용에 대해 주의해야 할 점으로 올바른 것은 무엇입니까?
  6. 빈 스택에 대해 push 1, push 2, pop, push 3, push 4, pop, pop의 순서로 조작했다. pop으로 꺼낸 값을 차례로 나열한 것은?
  7. 역폴란드 표기법(후위 표기법)으로 쓴 식 '3 4 + 2 * 5 −'를, 수가 오면 스택에 쌓고 연산자가 오면 두 값을 꺼내 계산하여 결과를 쌓는 방법으로 평가했다. 결과는 얼마인가? 여기서 연산자의 왼쪽 값은 먼저 쌓인 쪽의 값으로 한다.
  8. 요소 수 5인 정수형 배열 st와 정수형 변수 top으로 스택을 나타낸다. st의 요소는 모두 0, top은 0에서 시작한다. push(v)는 top에 1을 더한 후 st[top] ← v를 수행하고, pop()은 st[top]의 값을 반환한 후 top에서 1을 뺀다(st의 요소는 바꾸지 않는다). 다음 프로그램을 실행한 후의 top과 st의 조합은?
  9. CPU의 프로그램 카운터(PC)가 보유하고 있는 것은?
  10. 프로그램에서 서브루틴(함수)을 호출할 때 복귀 주소 등을 일시적으로 저장하기 위해 일반적으로 사용되는 영역은?
  11. RISC-V 명령어 'lw t0, 8(sp)'의 동작으로 올바른 것은?
  12. 호출 규약(콜링 컨벤션)이 정해져 있는 주된 목적은?
  13. RISC-V의 표준 호출 규약에서 정수 인자와 반환값을 전달하는 데 사용하는 레지스터로 올바른 것은?
  14. RISC-V의 표준 호출 규약에서 정수 인자가 10개인 함수를 호출할 때 9번째와 10번째 인자는 어디로 전달되는가?
  15. RISC-V 호출 규약에서 s0~s11이 '호출 대상 저장(callee-saved)' 레지스터라는 의미로 올바른 것은?

이 용어가 포함된 비교

관련 용어

변수(Variable) 재귀(Recursion) 복귀 주소(return address) 배열(Array) 호출 규약(Calling Convention) 반환값(Return Value) 스택 프레임(Stack Frame) 스택 포인터(stack pointer) 포인터(Pointer) 인수(Argument)

용어집으로 돌아가기