Array implementation of Stack

[Stephen Sprunk]

No, it is not. That's what top() is designed to do. Do you even know what
a stack is?

Dogma aside, it is common for implementations of pop() to return the
value being popped off the top of the stack. If callers don't need that
functionality, eg. because they've already retrieved it with top(), then
they can discard pop()'s return value. Therefore, it is of no harm to
provide that functionality in case callers do not wish to call top()
separately.

S

 

[Keith Thompson]

Rui Maciel wrote:
) in a scenario where "expanding the stack and setting the top element"
) are separate operations, the "expanding the stack" bit involves allocating
) memory and nothing more, without having the faintest guarantee that your
) program will ever use that memory or even initialize the memory it
) allocates.

Yes, and ?

) if you set your push() to do nothing more than allocate memory, then you
) only gain a way to needlessly allocate memory to your stack which you may or
) may not use.

You're contradicting yourself. It's only needless if you don't use it.
[...]

)> The point of pop() is to give you the top element of the stack.
)
) No, it is not. That's what top() is designed to do. Do you even know what
) a stack is?

BEGGING THE QUESTION AGAIN.
We're arguing about what the different stack operations should do.
So using "it's defined to do that" is begging the question.

There, I hope I spelled it out for you enough.

[...]

Willem, you have a point. There is no One True Way to define the
set of operations available for a stack.

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.

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?

 

[Willem]

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.



*) Note that I'm arguing that push()-takes-value and pop()-returns-value
are equivalent, not that it's better or worse than no-value.
In this case, the argument against pop() returning a value seems to
be that it's redundant, so therefore push() taking a value is also.


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

 

[Kleuskes & Moos]

I'm aware of that.


Ok, you don't *have* to, but there's no reason not to do so.



I never said that pop() shouldn't return the top value -- but it
doesn't really need to.

Extending the stack and storing a value in the new top element are
logically tied together.  I can't think of a scenario where it would
make sense to extend the stack *without* storing a value.  Because of
that, I don't think it makes sense to have a push() operation that
doesn't take an argument specifying the new value to be stored.

Accessing the top element and shrinking the stack by one element
are not tied together in the same way.  I might want to access the
same top element multiple times, or I might want to discard the
top element without caring what it was; either leaves the stack in
a well defined state.

If I want a conceptually pure stack implementation (perhaps in a
classroom setting), I might just provide a push() that takes an
element value and pop() that returns an element value.  If I want
something more convenient for real-world use, I might provide those
operations *plus* a top() function that returns the top element
value, an function that returns the Nth element from the top, and
a pop()-like function that discards the result.  (The latter isn't
necessary in C, since the caller can easily discard the result.)

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.

 

[Kenny McCormack]

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?

Could someone remind me again: Just how many angels do dance on the head of
a pin?

--
Windows 95 n. (Win-doze): A 32 bit extension to a 16 bit user interface for
an 8 bit operating system based on a 4 bit architecture from a 2 bit company
that can't stand 1 bit of competition.

Modern day upgrade --> Windows XP Professional x64: Windows is now a 64 bit
tweak of a 32 bit extension to a 16 bit user interface for an 8 bit
operating system based on a 4 bit architecture from a 2 bit company that
can't stand 1 bit of competition.

 

[Malcolm McLean]

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?

Let's say we've got a graphics context. We have a subroutine that
draws a bicycle.

What we want to do is this

push(gc);
drawbicycle();
pop(gc);
/* graphics context is now back to where it was before bicycle was
drawn */

drawbicycle() might not actually modify the graphics context. The
point is, it can do so, without breaking caller.

 

[Rui Maciel]

Dogma aside, it is common for implementations of pop() to return the
value being popped off the top of the stack. If callers don't need that
functionality, eg. because they've already retrieved it with top(), then
they can discard pop()'s return value. Therefore, it is of no harm to
provide that functionality in case callers do not wish to call top()
separately.

Yes, that is true. Nevertheless, when stating "the point" of a particular
operation, the description is focused on the operator's fundamental feature.
When considering a stack, the basic features which make it possible to use
it as a data structure are: storing data, retrieveing data and discarding
data. If we consider the classic stack operators, push(), top() and pop(),
it is easy to see what task is accomplished by which operator.

Some stack implementations may have been designed so that some fundamental
operators also perform a secondary task for the sake of convenience.
However, no matter how convenient a secondary task may be, the fundamental
task is still the main reason why that particular operator is needed.


Rui Maciel

 

[Rui Maciel]

Rui Maciel wrote:
) in a scenario where "expanding the stack and setting the top element"
) are separate operations, the "expanding the stack" bit involves
allocating ) memory and nothing more, without having the faintest
guarantee that your ) program will ever use that memory or even initialize
the memory it ) allocates.

Yes, and ?

) if you set your push() to do nothing more than allocate memory, then you
) only gain a way to needlessly allocate memory to your stack which you
may or ) may not use.

You're contradicting yourself. It's only needless if you don't use it.

Do you even take the time to read the stuff you post to this newsgroup? You
were the one who came up with the claim that "push() not taking a value
makes some sense", stating that it is a reasonable idea to reserve memory
for the stack without initializing it.

)> )> pop() without a return value would have to discard the value it
)> )> takes from the stack.
)> )
)> ) Well. that's the point of pop(). You store your data with push(),
you )> ) access the data with top() and you discard your data with pop().
)>
)> Do you know what "begging the question" means ?
)>
)> Here's an example for you:
^^^^^^^^^^^^^^^^^^^^^^^^^^

Are you really too stupid to read properly ?

So, you waste your time posting drivel to a discussion regarding basic data
structures such as a stack, while clearly demonstrating that you don't have
the faintest clue about what you were supposed to be discussing. Yet,
although your contribution to this discussion has been limited to noise and
pathetic assertions (i.e., "oh it makes so much sense to push uninitialized
values to a stack") you still believe you are in a position to accuse
someone else of being an idiot?

Here's a tip: if you your childishness makes it difficult for you to accept
that you may not be right about everything under the sun then try to limit
your claims to stuff you at least have any clue about. Beyond that, keep
your noise down to a minimum and your petty personal attacks to yourself.


Rui Maciel

 

[Willem]

Rui Maciel wrote:
) Yes, that is true. Nevertheless, when stating "the point" of a particular
) operation, the description is focused on the operator's fundamental feature.
) When considering a stack, the basic features which make it possible to use
) it as a data structure are: storing data, retrieveing data and discarding
) data.

That's your opinion. One could also claim that the basic features which
make it possible to use a stack as a data structure are: storing data and
retrieving data. These give the two classic stack operators push and pop.

This top() operator is an extra added convenience for when you want to
use the top value of a stack multiple times, but that is not one of
the basic features of a stack. Compare with being able to peek at the
first character of a stream without reading it.


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

 

[Willem]

Rui Maciel wrote:
) Willem wrote:
)> You're contradicting yourself. It's only needless if you don't use it.
)
) Do you even take the time to read the stuff you post to this newsgroup? You
) were the one who came up with the claim that "push() not taking a value
) makes some sense", stating that it is a reasonable idea to reserve memory
) for the stack without initializing it.

*IN THE SAME OPERATION*.

Now stop argumentam ad absurdum-ing.

) So, you waste your time posting drivel to a discussion regarding basic data
) structures such as a stack, while clearly demonstrating that you don't have
) the faintest clue about what you were supposed to be discussing. Yet,
) although your contribution to this discussion has been limited to noise and
) pathetic assertions (i.e., "oh it makes so much sense to push uninitialized
) values to a stack") you still believe you are in a position to accuse
) someone else of being an idiot?

Yes. You obviously didn't read anything I posted well enough to understand
it, instead just choosing to pick out some tidbits that you thought you
could attack in your counterarguments.

Other than that, anything you posted was one logical fallacy or another.
In this case, you seem to be resorting to throwing up a smokescreen by
posting personal insults, thereby completely ignoring what was actually
said.

) Here's a tip: if you your childishness makes it difficult for you to accept
) that you may not be right about everything under the sun then try to limit
) your claims to stuff you at least have any clue about. Beyond that, keep
) your noise down to a minimum and your petty personal attacks to yourself.

Here's a tip: Stop projecting your own shortcomings on others.


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

 

[Keith Thompson]

Yes, that is true. Nevertheless, when stating "the point" of a
particular operation, the description is focused on the operator's
fundamental feature. When considering a stack, the basic features
which make it possible to use it as a data structure are: storing
data, retrieveing data and discarding data. If we consider the
classic stack operators, push(), top() and pop(), it is easy to see
what task is accomplished by which operator.

Some stack implementations may have been designed so that some
fundamental operators also perform a secondary task for the sake of
convenience. However, no matter how convenient a secondary task may
be, the fundamental task is still the main reason why that particular
operator is needed.

Certainly one way to implement a stack interface is:

void push(item x);
item top();
void pop();

Another way is:

void push(item x);
item pop();

Another is

void push(item x);
item top();
void pop();
item pop();

where the latter two might be distinguished by different names,
by overloading, or just by having the caller ignore the result.

Anything that can be done with any of these interfaces, can also be
done with the others, perhaps at the expense of some extra calls.
For example, top() is equivalent to push(pop()).

You seem to be asserting that the three functions I listed as the
first interface are the fundamental operations, and everything else
is secondary. I see no basis for this assertion. I would say that
the second interface is more "academically pure" (it's the simplest,
and the others can be built from it), and the third is probably
more convenient.

 

[Rui Maciel]

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.

It appears that at least two different persons have been posting under the
name Willem, because this whole discussion has been based on how Willem
believes a stack should be implemented, instead of how it can be
implemented.

) 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.

Please do take the time to point out who has been making assertions on how
stack operations should work, and quote them exactly where they made those
assertions. Here's a hint: you won't find posts from anyone but yourself.

Therefore, if you believe that presenting that sort of behaviour is the sign
that someone is an idiot, and that it gives you the right to launch a set of
personal attacks based on your petty views, then I expect you to start
posting about how you believe Willem is stupid and an idiot.

) 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(*).

It appears that, still at this point, you are still unaware of top()'s
existence and purpose.

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.

Irrelevant and absurd. You either store an object in your stack or you
store a reference to an object in your stack. Even if you intend to store
"a part of" a structure in a stack you are still forced to store either
objects or references to those objects.

Either way, there is absolutely no justification for pushing uninitialized
values into a stack and postponing it's initialization, which isn't even
guaranteed to happen due to the design you've came up with.

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.

....which are always represented through objects and therefore are stacked
either as objects or references to those objects. Either way, this does not
provide any justification to push uninitialized values into a stack.

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.

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.

One could also imagine having a stack that stores char values, but using
it for different-sized objects/blobs.

Irrelevant. You store the object (or reference to the object), not the data
it represents.

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.

Stack frames are elements of a call stack. That is, they are the objects
(or references to an object) which are pushed into the stack. A call stack
doesn't push a new stack frame (that is, a new object isn't push()ed into
the stack) unless it needs to store information on that stack (that is,
unless there is a need to push() a value into the stack, and therefore
initialize the value). Therefore, this does not provide any justification
to push uninitialized values into a stack.



Rui Maciel

 

[Rui Maciel]

Certainly one way to implement a stack interface is:

void push(item x);
item top();
void pop();

Another way is:

void push(item x);
item pop();

Another is

void push(item x);
item top();
void pop();
item pop();

where the latter two might be distinguished by different names,
by overloading, or just by having the caller ignore the result.

Anything that can be done with any of these interfaces, can also be
done with the others, perhaps at the expense of some extra calls.
For example, top() is equivalent to push(pop()).

You seem to be asserting that the three functions I listed as the
first interface are the fundamental operations, and everything else
is secondary. I see no basis for this assertion. I would say that
the second interface is more "academically pure" (it's the simplest,
and the others can be built from it), and the third is probably
more convenient.

The second interface fails to address the case where an item at the top of
the stack needs to be accessed without being forced to be removed from the
data structure, and it fails to address this case because it clumps two
atomic operations on a single operation.

When referring to the interface itself, and therefore acknowledging that the
stack can only be handled exclusively through those interfaces, then the
absence of a top() would represent a hindrance which, in practice, would
also represent a efficiency problem. Therefore, in terms of "academic
purity", it is better to represent the interface through a list of atomic
operations, which in this case would be the first example you provided.


Rui Maciel

 

[Ben Bacarisse]

Certainly one way to implement a stack interface is:

void push(item x);
item top();
void pop();

Another way is:

void push(item x);
item pop();

Another is

void push(item x);
item top();
void pop();
item pop();

where the latter two might be distinguished by different names,
by overloading, or just by having the caller ignore the result.

Anything that can be done with any of these interfaces, can also be
done with the others, perhaps at the expense of some extra calls.
For example, top() is equivalent to push(pop()).

Since push does not return anything and top does, that's not quite true.
You can do it with a temporary, of course (push(i = pop()), i) but
that's awkward in C because you can't introduce a new identifier into an
expression.

If push returned its argument, push(pop()) would do on its own so this
raises the question: should push return what it pushes? Form a purely
practical point of view, I always prefer a function to return something
rather than nothing. Not returning anything always seems like a wasted
opportunity. However unless the compiler can optimise it away it away
it may be the other way round: a waste of resources to return a value
that is so often ignored.

<snip>

 

[Willem]

Rui Maciel wrote:
) Willem wrote:
)
)> 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.
)
) It appears that at least two different persons have been posting under the
) name Willem, because this whole discussion has been based on how Willem
) believes a stack should be implemented, instead of how it can be
) implemented.

I believe I said before that you should learn to read. You have misread
what I wrote on several occasions, and here you make that abundantly clear.

I don't see how discussing with you any further could be fruitful in any
way; all you do is preach your One True Way of how a stack should work.


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

 

[Keith Thompson]

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?

Can you cite a definition of the word "stack" that says it *must*
provide an explicit top() operation?

I'm not arguing that this is a *good* interface for a stack. I agree
completely that having a top() operation is a good thing. My point is
merely that this qualifies as a "stack" by any reasonable definition.

 

[Keith Thompson]

The second interface fails to address the case where an item at the top of
the stack needs to be accessed without being forced to be removed from the
data structure, and it fails to address this case because it clumps two
atomic operations on a single operation.

Yes, it does. Does that mean it's not a stack? (See my other followup.)

When referring to the interface itself, and therefore acknowledging that the
stack can only be handled exclusively through those interfaces, then the
absence of a top() would represent a hindrance which, in practice, would
also represent a efficiency problem. Therefore, in terms of "academic
purity", it is better to represent the interface through a list of atomic
operations, which in this case would be the first example you provided.

Yes, the absence of top() would be a hindrance. I'm not aware of any
forma definition of "stack" that excludes hindrances.

The question of which interface has more "academic purity" is not a
particularly important one; if you disagree with my selection on that
score, I won't necessarily argue the point.

 

[luser- -droog]

<snip>











Since push does not return anything and top does, that's not quite true.
You can do it with a temporary, of course (push(i = pop()), i) but
that's awkward in C because you can't introduce a new identifier into an
expression.

That's more awkward than it needs to be. Remember the assignment
operator
yields a value.

item i;
push(i = pop());

You don't need the comma. I suppose i is a temporary if it's only
needed
for one expression.

 

[Ben Bacarisse]

That's more awkward than it needs to be. Remember the assignment
operator
yields a value.

item i;
push(i = pop());

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!

You don't need the comma.

Without the comma, you don't have an expression that behaves like top().

<snip>

 

[Stephen Sprunk]

If push returned its argument, push(pop()) would do on its own so this
raises the question: should push return what it pushes? Form a purely
practical point of view, I always prefer a function to return something
rather than nothing. Not returning anything always seems like a wasted
opportunity. However unless the compiler can optimise it away it away
it may be the other way round: a waste of resources to return a value
that is so often ignored.

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?

S