7

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?

wwl
  • 2,025
  • 2
  • 30
  • 51
oneman
  • 811
  • 1
  • 13
  • 31
  • I think he means like a list so look into substrings and by top I bet they mean index 0 – thesonyman101 Oct 26 '16 at 22:57
  • According to https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues, there is only `one end called top of the stack.` and `the item at the front of the queue.`, doesn't seem like there's ambiguity it – chickity china chinese chicken Oct 26 '16 at 23:02
  • It very well depends on how you want to look at it. For someone, the top of the stack could be the last element of the list (since FIFO), so any `pop()` operation would mean taking out the most recently inserted element. On the other hand, stack top could be the first element, where after each `pop()` you have readjust all the subsequent elements to the left by 1 position. – Sreejith Menon Oct 26 '16 at 23:02
  • 1
    You might want to look at the answers to this question: [What is the basic difference between a stack and a queue?](http://stackoverflow.com/questions/10974922/what-is-the-basic-difference-between-stack-and-queue) Specifically, [this answer](http://stackoverflow.com/a/19241916/2566388) defines the terms "top" and "front" for you. – Samira N Oct 26 '16 at 23:04
  • If you're implementing stacks and queues on top of lists, the front of the queue or the top of the stack is whichever end you chose to use for that purpose. One choice might be more natural for whatever reason (especially for stacks), but it really depends on your implementation. – user2357112 Oct 26 '16 at 23:10
  • 1
    The "stack" metaphor is supposed to refer to a pile of plates. The top is where you add and remove plates. When you add a new plate, it goes on the top, and that's the one you get when you take a plate off the stack. – Barmar Oct 26 '16 at 23:14

3 Answers3

5

I think that, strictly speaking, neither end of a list has to be the top of a stack/front of a queue. The implementation of your data structure is separate from the expected behavior of the data structure.

For instance, a stack exhibits a last in, first out (LIFO) behavior. In other words, the last element that was stored in the stack is the "top" element. If you decide to implement your stack as a list where every new element is added at index 0, and all existing elements are shifted over by 1, then index 0 would be your top. On the other hand, if you implement your stack as a list where every new element is appended to the end of the list, then index -1 would be your top.

With that said, the former implementation is quite inefficient because every time you push/pop values on/off the stack, you have to shift your entire list, whereas the latter implementation is more efficient because you can simply append/remove elements to/from the end of the list.

Also, just to point out something mentioned in other answers/comments that I didn't make explicitly clear, your implementation doesn't have to be a list either. When I said that implementation and behavior are separate, that also goes for underlying data structure.

beeftendon
  • 876
  • 7
  • 14
5

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.

wim
  • 338,267
  • 99
  • 616
  • 750
  • Thank you that makes sense. I should have considered the LIFO and FIFO natures. But I'm sure you can understand where I am coming from in saying that "top" and "front" are quite ambiguous. – oneman Oct 26 '16 at 23:16
  • In my opinion a stack and a queue are not the same, as a list. These are different structures as a tree or anything else. So there is no reason to decide, which end of the list is top of stack or front of queue. Of course it could be usefull to implement a stack and a queue with a list as base structure and sure the end of the list could be prefered as top of stack, but an implementation can do it, as is wants to. The question is useful, o.k. but my answer would be: lists are other basic structures and so they in fact dont have a front, an end or a top. – am2 Oct 26 '16 at 23:26
  • it sounds as to take a blank sheet of paper and ask, which side has to be the upper. If you want to draw anything you will determine this fact, but earlier there is no upper side. – am2 Oct 26 '16 at 23:29
  • @am2 I partially disagree. Lists are ordered, are they not? If we iterate through the list (printing each item for example), then by default, it starts at index[0] and it will keep on iterating until it gets to the "end of the list" index[-1]. So in my opinion, I believe that lists have a start (index[0]) and an end (index[-1]) but I can not relate this to "front" or "top" as in my mind, either end can be the front or top – oneman Oct 26 '16 at 23:30
  • @oneman: sorry, I didn't explain as I meant. Of course has a list a start and an end. But both of them have nothing to do with front and and of a queue unless you implement this that way. It might be useful to use the start of a list as front of a queue, but It depends on you – am2 Oct 27 '16 at 07:17
1

It depends on how you are appending to the list. If you are doing 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 appending from the front of the list then the front or index 0 is the top. Here is an example for 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" % (
Preston Hager
  • 1,514
  • 18
  • 33