5

I don't see the reason to have classes for stacks, queues and deques if we have the data structure linked list, since a linked list can act as both a stack and a queue (and always has the functions of both, if not just named differently).

So this brings forth my question,

Is there a specific reason I should use stacks and queues over a linked list besides readability?

last tidbit, I program in Java and .Net

  • 10
    It is often useful to describe a contract (e.g. a data structure, or an interface in general) in terms of both "what can we do" together with "what we cannot (not allowed to) do". Stacks, queues and deques are conceptual things (what human thinks of), whereas linked list is an underlying mechanism (how it is implemented). Stacks, queues and deques gives some meaningful names to the underlying operations, that human can associate with everyday life (think physical movements in terms of a stack of boxes, queue of shoppers, etc.) So, yeah, it's all anthropocentric. – rwong Oct 16 '16 at 1:57
  • Makes sense now, thank you. Makes me feel a little better about picking one over the other. – NightSkyCode Oct 16 '16 at 2:11
  • An answer to a similar question – radarbob Oct 16 '16 at 2:52
  • 4
    Also, just because a stack or queue can be implemented in a linked list, doesn't mean it's the most efficient way to do it. If you know that a stack will never exceed a dozen entries, it might be more efficient to allocate an array and keep track of the index of the last entry (a stack pointer, as it were). All of this is an implementation detail, which is as it should be. Expose the intention, not the implementation (as @rwong alluded to). – mgw854 Oct 16 '16 at 2:52
18

Stacks and queues are ways of working with contiguous memory. Linked lists are not. Now sure, any problem that you can solve with one structure you could solve with another and slap enough abstraction on it that you couldn't tell the difference. So what's the real difference? Performance. Choosing between these structures is about what you DON'T do with them because they don't do that well.

Linked lists make insertions into their middle easy. They make traversing hard.

Stacks and queues prefer to do insertions and removal at an end.

None make it impossible to do anything since you can rebuild the entire structure. The issue is the cost that comes at.

One thing that's helped me along the way is this little guy:

enter image description here

Here's one that includes the less popular structures:

enter image description here

Under the hood it's all one big array called random access memory. Using these structures doesn't change that. But if you can predict what you don't need you can choose the right structure that will help you use that memory very well.

  • 5
    I don't think they are all one big array. If I'm correct, I think linked list use "nodes" that have a reference to each other, which is far from an array. – NightSkyCode Oct 16 '16 at 3:12
  • 1
    Eh, technically, but answering a question about the difference of memory structures by saying "it's all just memory anyway" isn't particularly helpful. Stacks and queues are likely contiguous, but without the implementation in hand, you'd never know that (they're an abstraction, after all). There's much more to it than performance (although that is a consideration)--it's really about what we (as programmers) want to expose about the intent of the object. – mgw854 Oct 16 '16 at 3:16
  • 1
    @mgw854 remember the question NightSkyCode asked though. Why have different ones? Can't we design one god like structure that does everything and use it however we want? The truth is we can. The reason we don't isn't because objects should express their intent. It's because things work better when you use the right tool. I can drive nails with a screwdriver or a swiss army knife but I'd much rather use a hammer. I can express my intent by labeling my hammer "nail driving thingy" if I have to. – candied_orange Oct 16 '16 at 3:33
  • 2
    A stack and a queue probably have the same logical layout in memory. They require either one index (for a stack pointer) or two (for a queue head and tail). Performance-wise, they're nearly identical. What operations they express, however, are wildly different. A queue is FIFO. A stack is LIFO. Although they look very similar internally, what they do externally is very different. That's what I mean about intent: a stack and a queue can't do the same things. That's safety that you don't get with using an array or linked list. – mgw854 Oct 16 '16 at 3:42
  • 3
    Let me rephrase it this way--we have God structures, but they're not very useful by themselves. It's much better to state your intent and use a structure which conforms to that intent to provide type safety. If I use a queue, it behaves in only one way because I enforce that behavior. If I just use a linked list directly, none of the invariants of a queue are enforced. You could just as easily pull from the middle, which makes no sense. Using a proper class would only allow taking from the head. – mgw854 Oct 16 '16 at 3:54
9

I love CandiedOrange's answer though a queue or stack could be implemented using a linked list, or an unrolled linked list, or a fully contiguous array representation, or something else.

But I want to wholeheartedly agree and echo and hone in on a part which is really about designs doing less. Minimalism is very beneficial to a design in all kinds of ways, from having fewer ways to misuse a design to providing it more room to be implemented efficiently, to even expressing your requirements better in code that uses a particular design (one that does less tells the readers of your code all the things you aren't going to be doing).

LIFO stacks and FIFO queues typically do less than, say, a doubly-linked list, and that doesn't make their designs inferior whatsoever. In a number of cases, it could make them superior. And that applies to tangible objects as well in the real world. For example, someone might ask: "why use one of these"?

enter image description here

... "when you have one of these?"

enter image description here

And it should be pretty obvious in this case. But that also applies to designs in software. Doing more isn't necessarily equivalent to superior. When it comes to daily efficiency, it's also not always about using cutting-edge algorithms and parallelized, vectorized code. Sometimes it's just about making sure you aren't paying for things you don't need. Using designs which provide way more than what you need will often extract that kind of cost, like that multitool above when all you really need is a sharp knife to cut sashimi.

And naturally when you state your design requirements clearly and say, "All I need is a sharp knife to cut sashimi", then the implementers can come up with far more efficient, more reliable implementations in a short period of time for that narrow set of requirements than if you said, "Uhh, I don't know what I need. Here's a list of all the possibilities of things I may or may not need," at which point they might take ages and then hand you that analogical multitool. And naturally if I see you carrying a sushi knife around, I can more easily deduce that you're probably going to be dicing up fish and figure out your intentions than if you were carrying a multitool around.

  • 3
    I love how this was answered. +1 for team upvote! – NightSkyCode Jan 19 '18 at 15:17
  • Oh thanks but I feel bad when the accepted answer is changed. I just wanted to chime in. I think CandiedOrange's answer is better. I just wanted to kind of echo a big part of it! – user204677 Jan 19 '18 at 15:22
  • 1
    @TeamUpvote oh don't feel bad. I actually gained rep because of the traffic you brought here. Not that that's at all important. You've eloquently made the point that getting the abstraction wrong comes with a cost of its own. +1 – candied_orange Jan 20 '18 at 4:46
  • @CandiedOrange Yay, thank you! I feel bad sometimes bumping these old threads. – user204677 Jan 20 '18 at 5:32
  • 1
    @TeamUpvote old threads need bumping. If you can overcome stackexchanges natural resistance to it then more power to you. Some of the answers I'm most proud of were late answers like this. – candied_orange Jan 20 '18 at 10:31
1

Echoing @rwong comment, using a Queue or Stack

  1. Documents the contract
  2. Is a better name - might avoid the need for a comment
  3. Makes your intentions clear.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.