Ohh...I know. Trust me I know. All this talk about non-primitive data structures without stacks and queues? Impossible. How would we ever?
We've already covered lists and gotten linked lists under our sleeves. Still unfamiliar? Go ahead with this primer. Handling these two at once pairs beautifully to remove some of the confusion that lingers. For this piece, we'll detail the next set.
Stacks
Consider, for a moment, a literal haystack. Our horses are hungry, and food needs to be stored. We place these square bits of nicely packaged treats, one on top of the other - a stack. Getting them out for delivery, we'll take the very first we get from the whole pile. Just like that.
Now for the relevance of this in engineering. Items in a stack are of fixed size, that is, their sizes are known beforehand rather than the compiler trying to figure this out and finding the next available space. Since we have one point of entry and exit, this saves time, making their use fast.
Hence, local function variables are stored in a stack and popped off the stack when the function is done with its task. The differences between this and a heap are just discussed before. Like a pile of clothes, well push new items to it and like any cap, pop the first item off.
Note:
A stack is dynamic. It grows or shrinks in size. Items being placed in a stack, however, already have a known size. We do not intend to have our compiler second guess.
Queues
As opposed to stacks, here the first item in will be the first one out. (FIFO). Think of it as 'first come first served'. Adding an item to the eternal queue is, in its basic form enqueuing while getting an item off the queue would be dequeuing.
So my computer is running a lot of processes right now. We debunked the myth of doing many things all at once in a word on multi-threading, where we showed how the CPU will do context switching to give the feel of running multiple things at once. All these actions, need to be tracked. they would be placed ina queue - where the first to request resources gets access.
A little systems programming here.
You've got your program that does 123 things. It spawns one or two processes from within itself. Remember that your program is also a process when you run it! Now one of the child processes within it says :
'Hey! A software event occurred. You messed up with the type of parameter you gave!'
(Or something like that).
Based on how many interrupts your program gets; hardware, terminal special character(Ctrl + C), and so on, the system has to place them in a queue and show the messages appropriately based on what came first.
We can, if we wanted to, see what the first item is with peek(), check if we are done with items in the queue, hence an empty queue with isEmpty or check if we are swamped and probably not going out soon since we have a full queue with isFull.
A simple queue implementation such as defining an array(which are items of fixed size), would serve as an example.
As you might have noticed. We have re-used the array data structure to show how, all these structures, are used side by side to form more complex structures. Layers upon layers with different implementations.Building blocks.
Let's do more of this in the next session. Going to the non-linear, where everything seems to be falling off trees with weird graphs.
