From: Paul Brannan <pbrannan@...>
Date: 2002-11-30T04:20:24+09:00
Subject: Re: RCR: Stack, Queue alias methods in Array

On Sat, Nov 30, 2002 at 03:57:28AM +0900, Martin DeMello wrote:
> stack and queue are the more usual name, though. and the method names
> should be the usual names for *operations* on stacks and queues. the
> problem is, 'peek at the top element' is not (as far as i know, anyway)
> technically a valid stack operation - strictly, you should use
> 'stack.push(a = stack.pop)'.
>
> does any language with a Stack class define this method? the literature
> usually refers to the top of a stack, and the head and tail of a queue,
> hence my proposed method names.

The C++ standard explicity disallows retrieving an element using pop().
Instead, pop() takes an element of the stack (and returns void), while
top() returns the element last pushed onto the stack.

The reason is for exception safety.  We might implement pop() like this:

  template<class T>
  T Stack<T>::Pop()
  {
    T result; // if empty, return default-constructed T
    if( vused_ > 0)
    {
      result = v_[--vused_];
    }
    return result;
  }

but this would not be exception-safe, becase an exception could be
thrown in the last line (return result;) when the element being returned
is copy constructed.  If that happens, then it's too late; we've already
returned from pop(), so there's no chance for the function to roll back
the changes it made to the stack, and the element that was on the top of
the stack is now permanently lost.  I stole this example from Herb
Sutter; see http://www.gotw.ca/gotw/008.htm in case you want to read the
whole explanation.

Ruby doesn't have this problem, because all containers in Ruby hold
references to objects instead of objects.  If the stack mentioned above
were a stack of pointers (say T=Foo*), then there is no problem, because
the copy constructor cannot throw an exception.  In Ruby, we can safely
write:

  class Stack
    def pop
      @v = vused[-1]
      vused[-1].delete_at(-1)
      return @v
    end
  end

and there are no exception-safety problems to worry about.

Paul