std::stack vs std::deque (stacked deck?)

Discussion in 'C++' started by DevNull, Feb 27, 2007.

  1. DevNull

    DevNull Guest

    Hello everyone,
    I decided to pick c++ back up after not really having used it much in
    10 years.
    Just as a point of refference, there was no standard C++ last time I
    used regularly.

    Anyways coming back, I've fallen in love with all the improvements in
    the language such as the STL. Congrats to anyone who worked on it,
    you did an excellent job.

    To teach myself c++ again, I decided a good first project would be to
    implement a scripting language against a MUD server/client system I
    originally designed in C.

    Thus far I've made what I feel is incredible headway, and thanks to
    this newsgroup I've gotten over a number of humps.

    To make a long story short, I'm a bit confused. I went head first,
    and decided the std::deque would be an ideal structure for
    implementing my scripting languages stack.

    Now I've had a chance to look at the boost spirit library and numerous
    others, and it looks like a structure called std::stack is the
    preffered method of implementing alot of the things I've implemented.

    But there's a problem and I can't quite get my head around it.
    std::stack is a FILO object whereas std::deque at least as I'm using
    it, can be FIFO or FILO. In my case, instructions go in via push_back
    and get removed via pop_front making it effectively a FIFO object.
    But std::stack has push and pop methods which operate only on the top
    of the stack.

    To me at least it seems more natural to push an object to the bottom
    and pop it from the top, which means that instructions get executed in
    the order they are added.

    But it looks like I'm wrong here, as I said almost every example I can
    find uses std::stack, can someone smarter than me (pretty much
    everyone except the guy selling viagra), explain why the std::stack
    implementation is considered superior so much so that I cannot find a
    single example of a VM using std::deque?

    Thanks in advance!
    DevNull, Feb 27, 2007
    #1
    1. Advertising

  2. DevNull

    Guest

    On Feb 26, 8:49 pm, "DevNull" <> wrote:
    > Hello everyone,
    > I decided to pick c++ back up after not really having used it much in
    > 10 years.
    > Just as a point of refference, there was no standard C++ last time I
    > used regularly.
    >
    > Anyways coming back, I've fallen in love with all the improvements in
    > the language such as the STL. Congrats to anyone who worked on it,
    > you did an excellent job.
    >
    > To teach myself c++ again, I decided a good first project would be to
    > implement a scripting language against a MUD server/client system I
    > originally designed in C.
    >
    > Thus far I've made what I feel is incredible headway, and thanks to
    > this newsgroup I've gotten over a number of humps.
    >
    > To make a long story short, I'm a bit confused. I went head first,
    > and decided the std::deque would be an ideal structure for
    > implementing my scripting languages stack.
    >
    > Now I've had a chance to look at the boost spirit library and numerous
    > others, and it looks like a structure called std::stack is the
    > preffered method of implementing alot of the things I've implemented.



    std::stack and std:queue are usually just specializations of
    std::deque (double ended queue). They implement stacks and queues,
    just like the name implies.


    > But there's a problem and I can't quite get my head around it.
    > std::stack is a FILO object whereas std::deque at least as I'm using
    > it, can be FIFO or FILO. In my case, instructions go in via push_back
    > and get removed via pop_front making it effectively a FIFO object.
    > But std::stack has push and pop methods which operate only on the top
    > of the stack.
    >
    > To me at least it seems more natural to push an object to the bottom
    > and pop it from the top, which means that instructions get executed in
    > the order they are added.



    If you want FIFO behavior, you want a queue. If you want LIFO (FWIW,
    "FILO" is pretty rare usage), then you want a stack. If you want
    both, you want a double ended queue.

    std::deque support push/pop_front/back since you can work on both
    ends. std::queue and std::stack only support push and pop because
    there's only one end each operation applies to (the same end in the
    case of a stack, opposite ends in the case of a queue). You can use a
    deque as either, by using the right combination of push/pop front/back
    operators, or you do both, and then a dequeue becomes more than either
    a stack or a queue.


    > But it looks like I'm wrong here, as I said almost every example I can
    > find uses std::stack, can someone smarter than me (pretty much
    > everyone except the guy selling viagra), explain why the std::stack
    > implementation is considered superior so much so that I cannot find a
    > single example of a VM using std::deque?



    Presumably because the samples want a stack (LIFO) data structure.
    Also, std::stack and std::queue are a simpler to use in many cases
    (although they have a number of limitations when compared to
    std::deques).
    , Feb 27, 2007
    #2
    1. Advertising

  3. DevNull wrote:
    > [..]
    > To teach myself c++ again, I decided a good first project would be to
    > implement a scripting language against a MUD server/client system I
    > originally designed in C.
    >
    > Thus far I've made what I feel is incredible headway, and thanks to
    > this newsgroup I've gotten over a number of humps.
    >
    > To make a long story short, I'm a bit confused. I went head first,
    > and decided the std::deque would be an ideal structure for
    > implementing my scripting languages stack.
    >
    > Now I've had a chance to look at the boost spirit library and numerous
    > others, and it looks like a structure called std::stack is the
    > preffered method of implementing alot of the things I've implemented.


    std::deque is a true container. std::stack is a container adapter.
    What book are you reading that doesn't explain the difference?

    > But there's a problem and I can't quite get my head around it.
    > std::stack is a FILO object whereas std::deque at least as I'm using
    > it, can be FIFO or FILO. In my case, instructions go in via push_back
    > and get removed via pop_front making it effectively a FIFO object.
    > But std::stack has push and pop methods which operate only on the top
    > of the stack.


    Well, a car can go forward or backward as the driver wants it to.
    However, when towing something on a rope, going backward does not
    make much sense. In that case the car only goes forward. The rope
    is the additional constraint that make a bi-directional mechanism
    uni-directional. A std::deque is like a car, you can use it as
    a queue and push and pop from either end, or you can limit yourself
    and only use one end of it (the end or the beginning). Then it
    loses its bi-directionality. That's what std::stack does. It
    essentially _hides_ the push_front and pop_front stuff, even if
    it's available in the underlying container.

    > To me at least it seems more natural to push an object to the bottom
    > and pop it from the top, which means that instructions get executed in
    > the order they are added.


    But that's not a stack model...

    > But it looks like I'm wrong here, as I said almost every example I can
    > find uses std::stack, can someone smarter than me (pretty much
    > everyone except the guy selling viagra), explain why the std::stack
    > implementation is considered superior so much so that I cannot find a
    > single example of a VM using std::deque?


    Nothing is superior to anything. You can organize your std::stack to
    use std::deque as the underlying container. Get a decent book and
    read a bit about those things.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Feb 27, 2007
    #3
  4. DevNull

    kwikius Guest

    On 27 Feb, 03:29, "Victor Bazarov" <> wrote:

    <..>

    > Well, a car can go forward or backward as the driver wants it to.
    > However, when towing something on a rope, going backward does not
    > make much sense.


    Hmm. I prefer the following analogy. Suppose you have a guy sitting at
    a table. Now you keep feeding this guy stuff.

    Important warning: BTW Its useful when performing this experiment to
    use food which can be identified after it has passed through the guys
    guts. For this sweetcorn is quite suitable, peas, beetroot, that sort
    of thing. If you dont do this you could be wasting a lot of time
    sifting the results...

    Now the experiment works because its not possible for the guy to keep
    eating for ever. At some point stuff has to come out..

    >From which end it comes out first you can tell if the guy is acting

    like a queue or a stack.

    regards
    Andy Little
    kwikius, Feb 27, 2007
    #4
  5. DevNull

    DevNull Guest

    On Feb 26, 8:56 pm, "kwikius" <> wrote:
    > On 27 Feb, 03:29, "Victor Bazarov" <> wrote:
    >
    > <..>
    >
    > > Well, a car can go forward or backward as the driver wants it to.
    > > However, when towing something on a rope, going backward does not
    > > make much sense.

    >
    > Hmm. I prefer the following analogy. Suppose you have a guy sitting at
    > a table. Now you keep feeding this guy stuff.
    >
    > Important warning: BTW Its useful when performing this experiment to
    > use food which can be identified after it has passed through the guys
    > guts. For this sweetcorn is quite suitable, peas, beetroot, that sort
    > of thing. If you dont do this you could be wasting a lot of time
    > sifting the results...
    >
    > Now the experiment works because its not possible for the guy to keep
    > eating for ever. At some point stuff has to come out..
    >
    > >From which end it comes out first you can tell if the guy is acting

    >
    > like a queue or a stack.
    >
    > regards
    > Andy Little


    The analogies are getting a bit silly. I guess in a nutshell I'm
    asking a theory question that I haven't seen covered anywhere, in any
    of the docs I've read.
    Why is a stack implementation LIFO used instead of FIFO which appears
    on the surface to make more sense.

    So I created a simple test problem, using a normal source file, and
    general scoping rules I wrote a simple parser.

    Turns out both implementations are acceptable in a simplistic VM at
    first. However, a LIFO stack gives you scoping for free!

    Look at how this simple script code breaks down.

    a = 1;
    b = 2;
    c = a + b;
    print("A + B + C =", a+b+c);

    Now if you have a LIFO stack, you get VM code that looks like this
    (assuming exec is called automatically)

    push(assign, a, 1);
    pop();
    push(assign, b, 1);
    pop();
    push(add, a,b,result);
    pop();
    push(assign,c,result);
    pop();
    push(add,a,b,result);
    pop();
    push(add,c,result,result);
    pop();
    push(funcPrint, "A + B + C ",result);
    pop();


    Now lets look at this example in a FIFO stack.
    push(assign,a,1);
    push(assign,b,2);
    push(add,a,b,result);
    push(assign,c,result);
    push(add,a,b,result);
    push(add,c,result,result);
    push(funcPrint,"A + B + C",result);
    pop();
    pop();
    pop();
    pop();
    pop();
    pop();
    pop();

    As you can see scoping becomes much harder in a FIFO stack since we
    have to keep pushing the result to the bottom and continue execution.
    Compare this to a LIFO where scope becomes essentially an automatic
    function.

    Anyways I think I've managed to answer my own question on this, thanks
    for the info and setting me straight on std::stack being LIFO.

    When it comes down to it though I wonder if there is/was any
    performance gains to using stack vs a deque in a LIFO manner, or if
    it's just syntactic sugar.

    Regards,
    DevNull, Feb 27, 2007
    #5
  6. On Feb 27, 9:49 am, "DevNull" <> wrote:
    > But it looks like I'm wrong here, as I said almost every example I can
    > find uses std::stack, can someone smarter than me (pretty much
    > everyone except the guy selling viagra), explain why the std::stack
    > implementation is considered superior so much so that I cannot find a
    > single example of a VM using std::deque?


    Sounds like you are storing the code that is being executed in the
    deque, i.e. using it as an internal representation of the program
    code. This is fine, sort of... (see below). The stack is used to store
    program state which is a slightly different thing.

    Sounds like you have the two different things a little confused?

    You don't say what the characteristics are of the scripting language,
    but if it features local variables, function calls or anything like
    that then a stack is the structure used to determine what values these
    name have in scope at that time (this gets potentially a lot more
    complex if your language has closures).

    The reason why I say the deque is sort of OK for storing the program
    is that it is awkward to use with any language that offers complex
    control flow (or even any control flow, like if statements, loops and
    function calls). You'll find a more complex structure will be easier
    to work with in that case. Using it as an intermediate to queue the
    next instructions (e.g. if you have some sort of operation
    interleaving going on to simulate multiple threads in the script
    language) is probably a good choice.


    K
    =?iso-8859-1?q?Kirit_S=E6lensminde?=, Feb 27, 2007
    #6
  7. DevNull

    Guest

    On Feb 26, 10:57 pm, "DevNull" <> wrote:
    > On Feb 26, 8:56 pm, "kwikius" <> wrote:
    > The analogies are getting a bit silly. I guess in a nutshell I'm
    > asking a theory question that I haven't seen covered anywhere, in any
    > of the docs I've read.
    > Why is a stack implementation LIFO used instead of FIFO which appears
    > on the surface to make more sense.



    I think you're confused. A stack *is* LIFO by definition. That's
    what a stack is. If a data structure is not LIFO, it's not a stack.
    A queue, again by definition, is FIFO. Questioning why a stack has
    been implemented LIFO rather than FIFO is flatly nonsensical.

    There are many applications for both stacks and queues, but they're
    not usually interchangeable. A double ended queue is a generalization
    of both queues and stacks.
    , Feb 27, 2007
    #7
  8. DevNull

    kwikius Guest

    On 27 Feb, 04:57, "DevNull" <> wrote:

    > The analogies are getting a bit silly.


    Well.. since comp.lang.c++ isnt moderated, and comp.lang.c++.moderated
    takes itself way too serious, I like to try to raise the tone with
    some bawdy humour from time to time :)

    Obviously though... I failed this time :-(

    <...>

    > So I created a simple test problem, using a normal source file, and
    > general scoping rules I wrote a simple parser.


    <...>

    Looks fun :)

    > When it comes down to it though I wonder if there is/was any
    > performance gains to using stack vs a deque in a LIFO manner, or if
    > it's just syntactic sugar.


    Basically yes. Except you can theoretically replace the default
    container template param with e.g your own "model" of stack etc
    without changing the source code.

    In which case you would then only need to provide the operations
    defined for stack, without having to provide the whole interface for
    more versatile containers. Thats the theory, though I generally just
    stick with what I'm given...

    regards
    Andy Little
    kwikius, Feb 27, 2007
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ziliath
    Replies:
    87
    Views:
    2,250
    White Wolf
    Oct 4, 2004
  2. Dietmar Kuehl
    Replies:
    0
    Views:
    849
    Dietmar Kuehl
    Sep 16, 2004
  3. Russell Warren
    Replies:
    5
    Views:
    403
    Tim Peters
    May 2, 2006
  4. Stephen Horne
    Replies:
    3
    Views:
    567
    Stephen Horne
    Aug 5, 2009
  5. neverhoodboy
    Replies:
    2
    Views:
    311
    Juha Nieminen
    Mar 12, 2012
Loading...

Share This Page