2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Stacks are a natural mapping for recursion. $\endgroup$ – vonbrand Sep 20 '15 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 '15 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 '15 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 '15 at 9:17
5
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ There is a very nice stack-less programming paradigm. $\endgroup$ – peterh says reinstate Monica Sep 19 '15 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$ – NL - Apologize to Monica Sep 19 '15 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$ – David Richerby Sep 19 '15 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$ – David Richerby Sep 19 '15 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$ – NL - Apologize to Monica Sep 19 '15 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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