Does a call stack grow first in / first out in C++?

Question

Each time we call the function, the stack of activation records (usually just called the stack) grows with one record. Conversely, when the function returns, its record is no longer used and so on. The stack (also called the call stack) is a data structure that grows and shrinks at one end according to the rule first in and first out.

Is the last line correct? I read it in the book programming principles and practices using C++, by Bjarne Stroustrup.

Answer 1

It is a mistake. A stack is, by definition, last in first out (LIFO). A first in first out (FIFO) data structure would be a queue, not a stack.

Answer 2

Let me show you how a call stack works: imagine you have a program, which contains some functions and subfunctions, like f1(), f1.1(), f1.2(), f1.1.1(), f1.2.1() and f1.2.2(), and you have following pieces of code:

int f1(){
  if (<condition>){ // B1
    return f1.1();
    } else {
    return f1.2();
  }
}

int f1.1(){
  int temp = -1; // B2
  return f1.1.1();
}

int f1.2(){
  if <other_condition>{
    return f1.2.1(); // B3
  } else {
    return f1.2.2();
  }
}

int f1.1.1(){
  int temp = 1001001;
  return temp;
}

int f1.2.1(){
  int temp = 1002001;
  return temp;
}

int f1.2.2(){
  int temp = 1002002; // B4
  return temp;
}

The B1-B4 mean that you put a breakpoint on that line, and the execution is done in such a way, that those breakpoints get hit. Let's see how the callstack look at those moments:

B1: Callstack:

f1()

B2 : Callstack:

f1.1()
f1()

B3 : Callstack:

f1.2() // at the moment of the breakpoint, f1.2.1() not yet executed.
f1()

B4 : Callstack:

f1.2.2()
f1.2()
f1()

The callstack gets filled from bottom to top: first f1() gets added (this function is being executed), when a subfunction (f1.1() or f1.2()) get executed, that one is added in top of the callstack. Once the execution is finished, it gets removed.