Which end of the list is the top?

Admittedly, this seems like a dumb question, but carry me.

In the question I was asked about Stack, we need to define a function that returns an element "on top" of the stack. For me, I don’t know which side is the “top”, because actually any side can be.

In addition, I have a question related to the queue, which asks us to define a function that returns the element "on the front panel" of the queue. Again, both sides can be interpreted as “front”

If the questions were reformulated to ask “return the last element in the list” or “first element in the list”, this makes sense, but unfortunately this is not so.

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

+6
source share
3 answers

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

The question is based on the false premise that stacks / queues are "basically just lists."

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

this is a python list, dawg!

(image source: here )

The implementation is not really like a stack or a queue, and the actual list objects can be everywhere in memory.

Stacks

This is pretty clear: if someone talks about the "top" of the stack, they will refer to an item that was recently added to the stack. This is the item that you will get if you "jump" off the stack.

Queues:

This is a little more airy fairy. If someone refers to the front of the queue, they probably mean the element that was added before, because queues are usually implemented with "FIFO" (first in first order). But it depends on the implementation, for example, python also has a LIFO Queue , which looks more like a stack. Worse, there are also deques (double-ended queues), so you really need to have more context to understand this bit of CS jargon.

+5
source

I think, strictly speaking, not one end of the list should be the top of the stack / front row. The implementation of your data structure is separate from the expected behavior of the data structure.

For example, the last in, first out (LIFO) behavior appears on the stack. In other words, the last item that was saved on the stack is the "top" item. If you decide to implement your stack as a list, where each new element is added to index 0, and all existing elements are shifted by 1, then index 0 will be your top one. On the other hand, if you implement your stack as a list, where each new element is added to the end of the list, then the -1 index will be your top.

With that said, the previous implementation is pretty inefficient, because every time you insert / set values ​​on the stack, you have to move your entire list, while the last implementation is more efficient, because you can just add / remove items to / from the end list.

Also, just to point out what was mentioned in other answers / comments that I did not explicitly do, your implementation should also not be a list. When I said that implementation and behavior are separate, this also applies to the underlying data structure.

+5
source

It depends on how you add to the list. If you do it as such,

stack = [] numbers = [1, 2, 3, 4, 6, 5] for n in numbers: stack.append(n) print(stack) 

Then the top of the stack is the end. When added from the front of the list, the front or index 0 are vertices. Here is an example of a calculator.

 addStack = [] curNumber = 0 while True: n = raw_input("Enter a number or operation.") if n.isdecimal(): addStack.append(int(n)) if n == "=": print("Top number(or last number entered): %i" % ( 
+1
source

Source: https://habr.com/ru/post/1011737/


All Articles