Search code examples
pythonliststackqueue

Which end of a list is the top?

Admittedly this seems like a silly question, but bear with me.

In a question I'm given relating to a Stack, we are to define a function that returns the item "on top" of the stack. To me, I don't know which side is the "top" because really, either side could be.

Also, I'm given a question relating to a Queue which asks us to define a function that returns the item "on the front" of the queue. Again, either side can be interpreted as the "front"

If the questions were reworded to ask "return the last item on the list" or the "first item on the list" this makes perfect sense, but unfortunately that is not the case.

So I would like to know: is there a definition for both "front" and "top" in terms of stacks/queues which are basically just lists, or are these terms ambiguous?

Solution

  • Is there a definition for both "front" and "top" in terms of stacks/queues which are basically just lists or are these terms ambiguous

    The question is built on a false premise, that stacks/queues are "basically just lists".

    Take a look at this picture, which shows how lists are stored in memory (CPython)

    it's a python list, dawg!

    (image source: here)

    The implementation is actually nothing much like a stack or a queue, it's more like an array of pointers. This array is contiguous, but the actual list elements referenced by those pointers may be all over the place in memory.

    What is the top of a stack?

    This one's pretty clear-cut: if someone speaks about the "top" of the stack, they would be referring to the item that was most recently added ("pushed") to the stack. That's the item you'll get if you "pop" off the stack.

    What is the front of a queue?

    This one's a bit more vague. If someone refers to the front of the queue, they probably mean the item which was added earliest, since queues are usually implemented "FIFO" (first in first out). However, there is also a less commonly-used LIFO Queue, which orders more like a stack. To make matters worse, there are also deques (double-ended queues) so you really need to have more context to understand this bit of CS jargon.