From low OS-level function calls, to memory allocated to an application, all will primarily take a stack to perform LIFO operations.

Why don't we use queues and FIFO operations? It's just a matter of moving pointers anyway.

  • $\begingroup$ Stacks are a natural mapping for recursion. $\endgroup$
    – vonbrand
    Sep 20, 2015 at 0:50
  • $\begingroup$ I don't understand what you're asking. You seem to have an assumption that the kernel uses stacks everywhere but no queues anywhere. What is the basis for this assumption? Please list at least one example of a place in a kernel that you think should use a queue but actually uses a stack, explain why you think it should use a queue, and explain which kernel uses a stack. Are you asking about the call stack for function calls, or about explicitly programmed data structures? $\endgroup$
    – D.W.
    Sep 20, 2015 at 4:12
  • $\begingroup$ @D.W. : The call stack basically. Why was it made a stack in the first place? To minimize pointer movement? $\endgroup$
    – Spandan
    Sep 20, 2015 at 7:21
  • $\begingroup$ OK. Please edit the question to clarify that, as I didn't find that clear. Thank you! $\endgroup$
    – D.W.
    Sep 20, 2015 at 9:17

1 Answer 1


Because some things need to be done LIFO and some things FIFO.

For example, when a function call returns, it needs to return to the last item on the call stack, i.e., the function that called it. It would make no sense to return to the first item on the call-stack. Conversely, if you're serving requests, the next request you serve is the first one to enter the service queue. (It turns out that, actually, serving queues from the back can be more efficient but that has the obvious disadvantage that it risks starvation for things at the front of the queue and, in real-life queues of people, it just gives people a huge incentive to leave the queue and re-join.)

  • $\begingroup$ There is a very nice stack-less programming paradigm. $\endgroup$
    – peterh
    Sep 19, 2015 at 14:01
  • $\begingroup$ Some of this is historical. Because there was a function call stack, memory was often allocated either as stack memory (local variables allocated with the function are stored here) and heap memory which required memory allocation and a pointer. Stack overflows could happen on stacks allocated from the heap, but the real stack overflow you wanted to avoid was calling too many functions and overflowing the stack memory. $\endgroup$ Sep 19, 2015 at 14:17
  • 1
    $\begingroup$ I don't understand what you're asking. My example of function calls shows that stacks are more or less necessary in some situation. Such stacks are implemented as stacks because they're stacks, in just the same way that windows (on buildings, I mean) are made of transparent substances because they're windows. So I don't understand your question of why stacks were implemented as stacks in the first place. $\endgroup$ Sep 19, 2015 at 14:57
  • 2
    $\begingroup$ Or are you asking why stacks are implemented using the data structure where each entry on the stack is some kind of record with a pointer to the previous one, and you keep track of the head, rather than, e.g., storing the elements in an array. If so, that's just an implementation decision. You can implement your stack in memory any way you want, as long as it provides the LIFO functionality you need. $\endgroup$ Sep 19, 2015 at 15:01
  • 1
    $\begingroup$ @Spandan have you ever written assembly code or machine code on a primitive machine? With higher level languages, the answer doesn't seem so obvious, but this was part of my allusion to historical decisions. Maybe there is enough explanation left for me to go ahead and write an answer, but I won't take the time to do that today. $\endgroup$ Sep 19, 2015 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.