Willem said:Keith Thompson wrote:
) Willem, you have a point. There is no One True Way to define the
) set of operations available for a stack.
Thank you, that was exactly the point I was trying to make.
) On the other hand, some operations make sense and some do not.
)
) I don't believe you've demonstrated that a push() operation that
) extends the stack without storing a value in the top element makes
) any sense.
I never tried to demonstrate it. I just got very annoyed by people
claiming that thier views on stacks are the One True Way, and using
bad logic to argue their points.
Nobody tried to argue *why* it maked sense to have the stack operations
work the way they say they should work. They just *asserted* it.
) Under what circumstances would you want to use such an operation?
) As far as I can see, extending the stack is *always* immediately
) followed by storing a value in the new top element. How would it
) be advantageous to separate those operations?
The most obvious one would be is your application needs a way to replace
or change the top value of a stack. Then a push() which sets the value
also would be redundant(*).
Another one would be if the 'value' on the stack is actually a large
entity, such as a struct, and passing the whole struct would be
a performance issue, especially if you're only using a part of it.
This is especially true if the stack is a way of being able to step
back to a previous saved state.
As a real-life example of that, look at a postscript interpreter, which
keeps a stack of graphics contexts. Or a chess playing program, which
needs to save the current state of the board to be able to try different
moves.
Another example would be when growing the stack would be a very costly
operation, and putting items in slots very cheap. In that case, it would
be very advantageous if you could grow the stack by a large step, and
then insert all the items one by one.
One could also imagine having a stack that stores char values, but using it
for different-sized objects/blobs.
Oh, and as a very real-life example, look at the way that a C compiler uses
stack frames: it allocates a whole frame in one go, and then uses the space
it created for different variables, objects, et cetera.
pop() not returning a value makes some sense if you think that
shrinking the stack and retrieving the top element should be
separate operations.
Ben said:This is an expression of void type but top() returns an item. That's
what my point was all about. Note that I do use the value of the
assignment so I must be remembering that it returns one!
Without the comma, you don't have an expression that behaves like top().
Just for drill I looked up what Knuth had to say in section 2.2.1 on
stacks, queues, and dequeues. He talks a good deal about push and pop
and various equivalent nomenclatures. Unless I missed it he doesn't
mention a top command at all until the last paragraph that reads:
When A is a nonempty stack, we MAY (emphasis mine) write
top(A)
to denote its top element.
I do not wish to appeal to authority, but in my experience Knuth's
depiction of stacks is the norm and Rui's formulation is
idiosyncratic. In short, push and pop are fundamental; top is a
convenience but it is not fundamental.
This is not to say that one can't come up with alternative commands.
For example one could have advance(), retreat(), write(item), and
read(), where write overwrites the top slot, read reads the top slot,
retreat moves the stack position back one slot, and advance moves it
forward one slot provided that the existing top slot isn't empty.
The suite of fanciful alternatives can be extended almost
indefinitely.
"Kleuskes & Moos" <[email protected]> ha scritto nel messaggio#io_x
Nitpick to an otherwise excellent expose:
That works fine if the content of your stack consists of simple values
(int, floats and such), you get into trouble when the stack consists
of structures. You can't just return a pointer, since the structure
will b ''destroyed'' with a pop operation.
---------------
#yes for stack of structures, not for stack of pointers to structs
#
#char *a;
#...
#a=pop(stack); if(a==0) error();
#// a point to the struct or 0
#free(a);
#
Stephen Sprunk said:In theory, I agree. However, are there implementations where returning
a value the function _already has available_ has a non-negligible
resource (I assume memory or CPU) impact?
Rui Maciel said:Willem wrote:
[...]
Again, do you even know what a stack is? If you don't know, I can tell you
that a stack is a LIFO data structure. A stack, by it's very definition,
doesn't offer a way to traverse the data structure. It offers a way for you
to access the top() element, it lets you push() elements and it letsyou
pop() elements. If you are thinking of a data structure which lets you
traverse the data it stores then you are thinking of some other data
structure, but you aren't thinking of a stack.
[I'm not quoting anything Willem wrote, but keeping the attribution line
to make it clear whom Rui is addressing.]
So if I showed you an interface that provides only the following
operations:
void push(item x); // pushes x onto stack
item pop(void); // removes top element from stack and
// returns its value
you'd tell me that it's not a stack, because it doesn't directly provide
a "top" operation?
Just for drill I looked up what Knuth had to say in section 2.2.1 on
stacks, queues, and dequeues. He talks a good deal about push and pop
and various equivalent nomenclatures. Unless I missed it he doesn't
mention a top command at all until the last paragraph that reads:
When A is a nonempty stack, we MAY (emphasis mine) write
top(A)
to denote its top element.
I do not wish to appeal to authority, but in my experience Knuth's
depiction of stacks is the norm and Rui's formulation is
idiosyncratic. In short, push and pop are fundamental; top is a
convenience but it is not fundamental.
This is not to say that one can't come up with alternative commands.
For example one could have advance(), retreat(), write(item), and
read(), where write overwrites the top slot, read reads the top slot,
retreat moves the stack position back one slot, and advance moves it
forward one slot provided that the existing top slot isn't empty.
The suite of fanciful alternatives can be extended almost
indefinitely.-
Kleuskes & Moos said:Rui Maciel said:Willem wrote:
[...]
Again, do you even know what a stack is? Â If you don't know, I can tell you
that a stack is a LIFO data structure. Â A stack, by it's very definition,
doesn't offer a way to traverse the data structure. Â It offers a way for you
to access the top() element, it lets  you push() elements and it lets you
pop() elements. Â If you are thinking of a data structure which lets you
traverse the data it stores then you are thinking of some other data
structure, but you aren't thinking of a stack.
[I'm not quoting anything Willem wrote, but keeping the attribution line
to make it clear whom Rui is addressing.]
So if I showed you an interface that provides only the following
operations:
  void push(item x); // pushes x onto stack
  item pop(void);   // removes top element from stack and
            // returns its value
you'd tell me that it's not a stack, because it doesn't directly provide
a "top" operation?
Depending on the usage, i might give you a hard time about that in a
code/design review and call the implementation "incomplete", unless
you can guarantee
a) the top-item is never inspected apart from after a 'pop'
b) the stack is never empty or you have a good definition for an error-
value of 'item'.
c) the stack is never 'full'.
In some cases, the above is all you need, but they are the exception,
rather than the rule.
Willem wrote:
[...]
Again, do you even know what a stack is? If you don't know, I cantell you
that a stack is a LIFO data structure. A stack, by it's very definition,
doesn't offer a way to traverse the data structure. It offers a way for you
to access the top() element, it lets you push() elements and it lets you
pop() elements. If you are thinking of a data structure which lets you
traverse the data it stores then you are thinking of some other data
structure, but you aren't thinking of a stack.
[I'm not quoting anything Willem wrote, but keeping the attribution line
to make it clear whom Rui is addressing.]
So if I showed you an interface that provides only the following
operations:
void push(item x); // pushes x onto stack
item pop(void); // removes top element from stack and
// returns its value
you'd tell me that it's not a stack, because it doesn't directly provide
a "top" operation?Depending on the usage, i might give you a hard time about that in a
code/design review and call the implementation "incomplete", unless
you can guaranteea) the top-item is never inspected apart from after a 'pop'
b) the stack is never empty or you have a good definition for an error-
value of 'item'.
c) the stack is never 'full'.In some cases, the above is all you need, but they are the exception,
rather than the rule.
Ok, but that wasn't my question. Rui's argument seems to imply that
it's not a stack at all, not merely that it's not a very good interface.
Michael Press wrote:
) A stack frame is best conceptualized as a single push. The
) details are not a stack operation at all. The details are
) memory allocation and initialization. _In_ the stack frame is
) data that tells the supervising process how to get the value of
) the stack pointer after this stack frame is released---how to
) pop the stack.
Thus illustrating my point nicely: It's a push without setting the value.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
The "Law of Least Surprize" is valid in these cases. Having some kind
of consensus of what you're talking about avoids much scratching of
ears, pointing at foreheads and general gnashing of teeth and loud
lamenting from the Upper Echelons.
On 06/24/2011 01:13 PM, Kleuskes & Moos wrote:
....
You may have noticed a distinct lack of consensus on this thread.
When different people are surprised by different things, the "Law of
Least Surprise" breaks down as a design principle.
// macro for function
#define P printf
// macro for keyWords
#define G goto
#define R return
#define W while
#define F for
#define T template
#define TN typename
The above macro's ought to be taken out and shot.
Nevertheless, introducing the designs as suggested in this thread (and
that includes the interfaces you brought up (and i do appreciate they
are not a sample of your usual design-style) need explanation, and
various people have expressed some surprise.
On 06/25/2011 02:00 AM, Kleuskes & Moos wrote:
...
Um ... - those were Keith's suggestions. I haven't made any.
Kleuskes & Moos said:The above macro's ought to be taken out and shot.
pop() gives you the top element, but it also has the side effect
of removing the top element from the stack.
Sometimes you want to look at the top element without modifying the stack..
If there isn't a separate top() operation, then of course
dosomethingwith(top());
can be emulated by
temp = pop(); push(temp); dosomethingwith(temp);
but the latter looks a bit awkward.
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.