Simple stack implementation

Discussion in 'C++' started by Thomas Ibbotson, Sep 19, 2005.

  1. I've been going through a tutorial on C++ and I've come across what I
    regard as some strange behaviour. As part of the tutorial on classes a
    simple stack is implemented with functions push() and pop().

    I test this stack using:
    stack a_stack; // Create an instance of stack

    // Push some data onto the stack
    a_stack.push(1);
    a_stack.push(2);
    a_stack.push(3);

    // Now pop it off again and see what we get
    cout << a_stack.pop() << " " << a_stack.pop() << " " <<
    a_stack.pop() << endl;

    // Refill the stack
    a_stack.push(1);
    a_stack.push(2);
    a_stack.push(3);

    // Try it a different way
    cout << a_stack.pop() << endl;
    cout << a_stack.pop() << endl;
    cout << a_stack.pop() << endl;

    The resulting output is:
    1 2 3
    3
    2
    1

    Where I would have expected:
    3 2 1
    3
    2
    1

    Can someone tell me what is going on?

    Thanks,
    Tom
     
    Thomas Ibbotson, Sep 19, 2005
    #1
    1. Advertising

  2. Thomas Ibbotson wrote:
    > I've been going through a tutorial on C++ and I've come across what I
    > regard as some strange behaviour. As part of the tutorial on classes a
    > simple stack is implemented with functions push() and pop().
    >
    > I test this stack using:
    > stack a_stack; // Create an instance of stack
    >
    > // Push some data onto the stack
    > a_stack.push(1);
    > a_stack.push(2);
    > a_stack.push(3);
    >
    > // Now pop it off again and see what we get
    > cout << a_stack.pop() << " " << a_stack.pop() << " " <<
    > a_stack.pop() << endl;


    This is a single expression where arguments to the last 'operator <<' are
    evaluated in _unspecified_ order.

    > [...]


    V
     
    Victor Bazarov, Sep 19, 2005
    #2
    1. Advertising

  3. Thomas Ibbotson

    John Carson Guest

    "Thomas Ibbotson" <> wrote in message
    news:dgn2en$g27$
    > I've been going through a tutorial on C++ and I've come across what I
    > regard as some strange behaviour. As part of the tutorial on classes a
    > simple stack is implemented with functions push() and pop().
    >
    > I test this stack using:
    > stack a_stack; // Create an instance of stack
    >
    > // Push some data onto the stack
    > a_stack.push(1);
    > a_stack.push(2);
    > a_stack.push(3);
    >
    > // Now pop it off again and see what we get
    > cout << a_stack.pop() << " " << a_stack.pop() << " " <<
    > a_stack.pop() << endl;
    >
    > // Refill the stack
    > a_stack.push(1);
    > a_stack.push(2);
    > a_stack.push(3);
    >
    > // Try it a different way
    > cout << a_stack.pop() << endl;
    > cout << a_stack.pop() << endl;
    > cout << a_stack.pop() << endl;
    >
    > The resulting output is:
    > 1 2 3
    > 3
    > 2
    > 1
    >
    > Where I would have expected:
    > 3 2 1
    > 3
    > 2
    > 1
    >
    > Can someone tell me what is going on?
    >
    > Thanks,
    > Tom


    To better understand the output, run the following code:

    int main()
    {
    stack a_stack; // Create an instance of stack
    int a, b, c; // used for recording results of pop operations

    // Push some data onto the stack
    a_stack.push(1);
    a_stack.push(2);
    a_stack.push(3);

    // Now pop it off and see what we get
    cout << (a=a_stack.pop()) << " " << (b=a_stack.pop()) << " "
    << (c=a_stack.pop()) << endl;

    cout << "a is " << a << endl;
    cout << "b is " << b << endl;
    cout << "c is " << c << endl;

    // Refill
    a_stack.push(1);
    a_stack.push(2);
    a_stack.push(3);


    // Pop it off a different way
    cout << endl;
    cout << (a=a_stack.pop()) << endl;
    cout << (b=a_stack.pop()) << endl;
    cout << (c=a_stack.pop()) << endl;

    cout << "a is " << a << endl;
    cout << "b is " << b << endl;
    cout << "c is " << c << endl;
    return 0;
    }

    The output is:

    1 2 3
    a is 1
    b is 2
    c is 3

    3
    2
    1
    a is 3
    b is 2
    c is 1

    For the first (anomalous) result, what the output tells you is that the
    numbers are being output in left-to-right order, as you would expect.
    However, prior to doing the outputting, the program is making the pop()
    calls in the reverse order to what you expect. Specifically, it is doing
    them in the following order:

    c=a_stack.pop()
    b=a_stack.pop()
    a=a_stack.pop()

    The reason for this is that an implementation is free to make these
    evaluations in any order it wants since all pop() functions are part of the
    same expression.

    For the second version, the semi-colon at the end of each line creates a
    "sequence point" which forces the evaluation of the functions up to that
    point. This forces evaluation in the expected order:

    a=a_stack.pop()
    b=a_stack.pop()
    c=a_stack.pop()


    --
    John Carson
     
    John Carson, Sep 20, 2005
    #3
  4. Thanks for the explanations, I'll keep it in mind for future reference.
    Tom
     
    Thomas Ibbotson, Sep 20, 2005
    #4
    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. Surinder Singh
    Replies:
    1
    Views:
    1,249
    Richard Bos
    Dec 20, 2007
  2. Casey Hawthorne
    Replies:
    3
    Views:
    1,151
    Flash Gordon
    Nov 1, 2009
  3. Debajit Adhikary
    Replies:
    36
    Views:
    2,400
    Andre Kaufmann
    Feb 10, 2011
  4. Sam Roberts
    Replies:
    1
    Views:
    237
    Yukihiro Matsumoto
    Feb 11, 2005
  5. Kenneth McDonald

    Why stack overflow with such a small stack?

    Kenneth McDonald, Aug 30, 2007, in forum: Ruby
    Replies:
    7
    Views:
    290
    Kenneth McDonald
    Sep 1, 2007
Loading...

Share This Page