oneman oneman - 1 month ago 5
Python Question

Which end of a list is the top?

Admittedly this seems like a silly question, but bare 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 ?

wim wim
Answer

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 python 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, and the actual list objects can be all over the place in memory.

Stacks:

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 to the stack. That's the item you'll get if you "pop" off the stack.

Queues:

This one's a bit more airy-fairy. 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). But, it does depend on the implementation, for example there is also a LIFO Queue in python, 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.

Comments