English
Menu

What is Stack?

A last-in, first-out (LIFO) data structure in which the element added last is removed first. Adding an element is called push and removing one is called pop. Stacks are used to manage return addresses and local variables in function calls (the call stack), to evaluate expressions in Reverse Polish notation and for depth-first search.

Japanese name: スタック

Stack appears in 34 practice questions across 8 topics, including ISA & Assembly, Linkers, Loaders & Executables, Data Structures and Algorithms.

Field: Data Structures and Algorithms

Try it: questions about Stack

A function that calls no other functions (a leaf function) often does not need to save ra on the stack. Why?

  1. ABecause leaf functions do not use the ret instruction
  2. BBecause the CPU automatically pushes the return address of leaf functions
  3. CBecause it calls no one, ra is never overwritten and the return address stays intact
Show answer and explanation

Answer: C. Because it calls no one, ra is never overwritten and the return address stays intact

Every jal overwrites ra, so a function that calls others must first save its own return address on the stack. A leaf function never executes jal, so ra stays intact and it can ret without saving it. If it also avoids callee-saved registers, it does not even need a stack frame. x86's call instruction always pushes the return address on the stack, which is a difference from RISC-V.

In RISC-V, what happens if a recursive function (one that calls itself) forgets to save ra on the stack?

  1. AThe inner call overwrites ra, so the outer invocation cannot return to its real caller
  2. BNothing goes wrong, because the CPU saves ra automatically
  3. CThe result is doubled regardless of recursion depth
Show answer and explanation

Answer: A. The inner call overwrites ra, so the outer invocation cannot return to its real caller

The recursive jal overwrites ra with "the instruction after my own call". If ra was not saved, when the outer invocation executes ret it returns into itself instead of to its original caller, looping or misbehaving. That is why any function that calls another must save ra on the stack in its prologue and restore it in its epilogue.

Stack in the explanations

Questions that mention Stack (34)

  1. A function that calls no other functions (a leaf function) often does not need to save ra on the stack. Why?
  2. In RISC-V, what happens if a recursive function (one that calls itself) forgets to save ra on the stack?
  3. What is the advantage of laying out the heap and stack so they grow in opposite directions with a large gap between them?
  4. When recursion goes so deep that it exceeds the stack limit, what generally happens on Linux and similar systems?
  5. On a small microcontroller without an MMU, what should be kept in mind about excessive stack use?
  6. On an empty stack, the operations push 1, push 2, pop, push 3, push 4, pop, pop are performed in this order. In what order are the values removed by pop?
  7. The expression “3 4 + 2 * 5 −” in reverse Polish notation (postfix notation) is evaluated by pushing each number onto a stack and, for each operator, popping two values, computing the result and pushing it back. What is the result? The left operand of an operator is the value that was pushed earlier.
  8. A stack is represented by the 5-element integer array st and the integer variable top. All elements of st start at 0 and top starts at 0. push(v) adds 1 to top and then does st[top] ← v; pop() returns the value of st[top] and then subtracts 1 from top (the elements of st are not changed). What are top and st after the following program runs?
  9. What does a CPU's program counter (PC) hold?
  10. When a program calls a subroutine (function), which area is generally used to temporarily save the return address and similar information?
  11. What does the RISC-V instruction "lw t0, 8(sp)" do?
  12. What is the main purpose of defining a calling convention?
  13. In the standard RISC-V calling convention, which registers pass integer arguments and return values?
  14. In the standard RISC-V calling convention, when calling a function with ten integer arguments, where are the ninth and tenth passed?
  15. In the RISC-V calling convention, s0-s11 are callee-saved registers. What does that mean?

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

Comparisons that include this term

Semiconductor, Electronics and Computing Calculators

Pseudocode Runner and TracerRun programs written in the pseudocode of Japan's Fundamental IT Engineer Exam (Part B) and trace each executed line and the values of variablesReverse Polish notation converterConvert infix expressions to Reverse Polish notation (postfix) and Polish notation (prefix), with the stack steps, the syntax tree and step-by-step evaluation

Related terms

Variable Recursion Return address Heap memory Argument Calling convention Array Return value Stack frame Queue

Back to the glossary