Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #6156 > unrolled thread

Re: Array implementation of Stack

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Array implementation of Stack Mark Bluemel <mark_bluemel@pobox.com> - 2011-06-16 15:05 +0100
    Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-16 20:12 +0100
      Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-16 19:35 +0000
        Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-16 22:44 +0100
          Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-16 15:26 -0700
          Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-17 14:10 +0000
            Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-17 08:12 -0700
              Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-17 15:16 +0000
                Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-17 10:46 -0700
                Re: Array implementation of Stack Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-06-17 12:22 -0600
                Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-18 02:35 +0100
                  Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-17 19:38 -0700
                  Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-18 09:45 +0000
                    Re: Array implementation of Stack Ike Naar <ike@sverige.freeshell.org> - 2011-06-18 10:18 +0000
                      Re: Array implementation of Stack Chad <cdalten@gmail.com> - 2011-06-28 21:43 -0700
                    Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-18 11:40 -0700
                    Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-22 03:46 +0100
                      Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-22 08:41 +0000
                        Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-22 08:50 -0700
                          Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-22 16:30 +0000
                            Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-23 16:37 +0100
                              Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-23 16:27 +0000
                              Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-23 10:08 -0700
                                Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-24 04:13 -0700
                                  Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-24 07:47 -0700
                                    Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-24 10:13 -0700
                                      Re: Array implementation of Stack James Kuyper <jameskuyper@verizon.net> - 2011-06-24 21:56 -0400
                                        Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-24 23:00 -0700
                                          Re: Array implementation of Stack James Kuyper <jameskuyper@verizon.net> - 2011-06-25 07:03 -0400
                                            Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-25 08:49 -0700
                            Re: Array implementation of Stack Michael Press <rubrum@pacbell.net> - 2011-06-23 20:49 -0700
                              Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-24 13:26 +0000
                                Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-24 10:25 -0700
                          Re: Array implementation of Stack gazelle@shell.xmission.com (Kenny McCormack) - 2011-06-22 20:40 +0000
                          Re: Array implementation of Stack Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-06-23 01:31 -0700
                        Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-23 15:53 +0100
                          Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-23 15:02 +0000
                      Re: Array implementation of Stack Stephen Sprunk <stephen@sprunk.org> - 2011-06-22 09:06 -0500
                        Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-23 15:39 +0100
                          Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-23 14:57 +0000
                            Re: Array implementation of Stack cri@tiac.net (Richard Harter) - 2011-06-23 19:19 +0000
                              Re: Array implementation of Stack luser- -droog <mijoryx@yahoo.com> - 2011-06-24 01:44 -0700
                                Re: Array implementation of Stack cri@tiac.net (Richard Harter) - 2011-06-24 21:55 +0000
                              Re: Array implementation of Stack Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-06-24 05:21 -0700
                          Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-23 08:25 -0700
                            Re: Array implementation of Stack Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-06-23 16:57 +0100
                              Re: Array implementation of Stack luser- -droog <mijoryx@yahoo.com> - 2011-06-23 12:49 -0700
                                Re: Array implementation of Stack Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-06-23 22:19 +0100
                                  Re: Array implementation of Stack luser- -droog <mijoryx@yahoo.com> - 2011-06-24 01:35 -0700
                              Re: Array implementation of Stack Stephen Sprunk <stephen@sprunk.org> - 2011-06-23 22:03 -0500
                                Re: Array implementation of Stack Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-06-24 11:47 +0100
                            Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-23 16:52 +0100
                              Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-23 10:11 -0700
              Re: Array implementation of Stack Mark Storkamp <mstorkamp@yahoo.com> - 2011-06-17 10:55 -0500
                Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-17 13:00 -0700
                  Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-17 20:24 +0000
                    Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-17 14:24 -0700
                      Re: Array implementation of Stack Ralf Damaschke <rwspam@gmx.de> - 2011-06-17 21:57 +0000
                        Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-17 16:07 -0700
                          Re: Array implementation of Stack Ralf Damaschke <rwspam@gmx.de> - 2011-06-18 16:59 +0000
                        Re: Array implementation of Stack Dr Nick <3-nospam@temporary-address.org.uk> - 2011-06-18 11:05 +0100
                      Re: Array implementation of Stack Willem <willem@toad.stack.nl> - 2011-06-18 09:55 +0000
                        Re: Array implementation of Stack Keith Thompson <kst-u@mib.org> - 2011-06-18 11:49 -0700
                          Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-22 10:22 -0700
                            Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-06-23 09:02 +0200
                              Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-06-23 09:57 +0200
                              Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-24 03:00 -0700
              Re: Array implementation of Stack Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-06-24 00:16 -0700
      Re: Array implementation of Stack "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 13:35 -0700
        Re: Array implementation of Stack Ian Collins <ian-news@hotmail.com> - 2011-06-17 08:50 +1200
          Re: Array implementation of Stack "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 14:15 -0700
            Re: Array implementation of Stack "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 14:19 -0700
            Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-16 22:51 +0100
              Re: Array implementation of Stack "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 15:27 -0700
        Re: Array implementation of Stack Rui Maciel <rui.maciel@gmail.com> - 2011-06-16 22:43 +0100

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#6752

On Thu, 23 Jun 2011 14:57:55 +0000 (UTC), Willem
<willem@toad.stack.nl> wrote:

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

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.

    

[toc] | [prev] | [next] | [standalone]

#6810

On Jun 23, 2:19 pm, c...@tiac.net (Richard Harter) wrote:
> On Thu, 23 Jun 2011 14:57:55 +0000 (UTC), Willem
>
> <wil...@toad.stack.nl> wrote:
> >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.
>
> 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.  

The 'nonempty' part seems tricky. If push() and pop() are used in
pairs,
one could avoid underflow checking entirely. But top() appears to need
an error mechanism, that might otherwise be omitted.

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

That might do well for a lower-level interface to the same object.
Then the stack interface could use these APIs to implement push(),
pop(), and top().

[toc] | [prev] | [next] | [standalone]

#6896

On Fri, 24 Jun 2011 01:44:23 -0700 (PDT), luser- -droog
<mijoryx@yahoo.com> wrote:

>On Jun 23, 2:19=A0pm, c...@tiac.net (Richard Harter) wrote:


>The 'nonempty' part seems tricky. If push() and pop() are used in
>pairs,
>one could avoid underflow checking entirely. But top() appears to need
>an error mechanism, that might otherwise be omitted.
>
>> 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.
>
>That might do well for a lower-level interface to the same object.
>Then the stack interface could use these APIs to implement push(),
>pop(), and top().

It occurs to me that there are some unexpressed issues in this
discussion.  The term, stack, precedes its use in computer science.  A
standard example is the push-down stack of plates.  (Do they still
make those things - I haven't seen one in ages.)  The important thing
about a physical stack is that the things in the stack are discrete
physical objects that can be in one place or another but not in two
places at once.   

Now it turns out that the notion of an object being in a unique place
is hard to express in many programming languages, C in particular.  C
does have the notion of an object as being a piece of addressable
memory.  However you cannot put that object anywhere; you can bind
variables to it and create pointers to it, but you cannot move it from
place to place.

In essence C data structures consist of locations holding values
(numbers, structs, pointers,etc).  Hence the physical model for stacks
is misleading .  That is, you don't put things on the stack; rather
you copy values into and from stack locations.

Thus push and pop "really" are:
   push:  advance the stack top and copy into the new location
   pop:   copy out the stack top contents and retreat the stack top
          (making provision for an empty stack)

So far, so good.  But what then is top(stack)?  It could be any of
several things.  Thus it could be a copy of the contents of the top
location; on the other hand it could a pointer to the top location.  A
bit of tricky declaration can even ensure that the top location is not
alterable.  (I think:-))  In short, top(stack) is ambiguous until its
definition is pinned down.

  


  

[toc] | [prev] | [next] | [standalone]

#6826

On Jun 23, 8:19 pm, c...@tiac.net (Richard Harter) wrote:
> On Thu, 23 Jun 2011 14:57:55 +0000 (UTC), Willem
>
>
>
>
>
> <wil...@toad.stack.nl> wrote:
> >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.
>
> 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.-

http://en.wikipedia.org/wiki/Stack_(data_structure)

they include a top operation. As does C++s STL





<spoiler>


ok I admit it, I wrote part of the wiki page

[toc] | [prev] | [next] | [standalone]

#6736

Rui Maciel <rui.maciel@gmail.com> writes:
> Stephen Sprunk wrote:
>> 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.

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.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#6739

Keith Thompson <kst-u@mib.org> writes:
<snip>
> 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>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#6754

On Jun 23, 10:57 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> Keith Thompson <ks...@mib.org> writes:
>
> <snip>
>
>
>
> > 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.

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.

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

[toc] | [prev] | [next] | [standalone]

#6762

luser- -droog <mijoryx@yahoo.com> writes:

> On Jun 23, 10:57 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> Keith Thompson <ks...@mib.org> writes:
>>
>> <snip>
>>
>> > 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.
>
> 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>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#6814

Ben Bacarisse wrote:
> luser- -droog <mijoryx@yahoo.com> writes:
>
> > On Jun 23, 10:57 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> >> Keith Thompson <ks...@mib.org> writes:
> >>
> >> <snip>
> >> > 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.
> >
> > 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().

Oh. I get it now. You're squeezing it into an expression. It appears
my
inclination is to break this into multiple statements.

So, the awkwardness *is* necessary for the expressivity you describe.

--
ldroog

[toc] | [prev] | [next] | [standalone]

#6776

On 23-Jun-11 10:57, Ben Bacarisse wrote:
> 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

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#6822

Stephen Sprunk <stephen@sprunk.org> writes:

> On 23-Jun-11 10:57, Ben Bacarisse wrote:
>> 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?

I don't know.  It must have some impact, but I have no idea if it can
ever be counted as significant.  I can say that I've never changed a
function's return type to void in order to gain some performance
advantage, but that's not a "fair" observation -- functions with return
values end up having that value used, so changing the interface so that
the function does not return a value is usually far from trivial, so it
is rarely going to be an appealing target for micro-optimisation.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#6740

Keith Thompson wrote:

> 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

[toc] | [prev] | [next] | [standalone]

#6747

Rui Maciel <rui.maciel@gmail.com> writes:
[...]
> 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.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#6251

In article <lnmxhg1ohk.fsf@nuthaus.mib.org>,
 Keith Thompson <kst-u@mib.org> wrote:

> Willem <willem@toad.stack.nl> writes:
> > Rui Maciel wrote:
> > ) Willem wrote:
> > )
> > )> ) Why should pop return a value?
> > )> 
> > )> For the same reason as push() takes two arguments.
> > )> 
> > )
> > ) And what reason is that?
> >
> > I don't know.  Ask the person who proposed the API upthread.
> >
> > If you insist that pop() shouldn't return a value, then push()
> > should not take a value either, just a stack.  Otherwise it
> > is plainly inconsistent.
> 
> pop() not returning a value makes some sense if you think that
> shrinking the stack and retrieving the top element should be
> separate operations.
> 
> push() without an argument would have to push an indeterminate or
> default value onto the stack.

Maybe the names are just poorly chosen. I always think of pop() 
returning the top value and shrinking the stack. I would use drop() to 
just shrink the stack. A push() without arguments could just duplicate 
the top of the stack, but then you'd be better off calling that dup().

[toc] | [prev] | [next] | [standalone]

#6295

On Jun 17, 5:55 pm, Mark Storkamp <mstork...@yahoo.com> wrote:
> In article <lnmxhg1ohk....@nuthaus.mib.org>,
>  Keith Thompson <ks...@mib.org> wrote:
>
>
>
>
>
>
>
>
>
> > Willem <wil...@toad.stack.nl> writes:
> > > Rui Maciel wrote:
> > > ) Willem wrote:
> > > )
> > > )> ) Why should pop return a value?
> > > )>
> > > )> For the same reason as push() takes two arguments.
> > > )>
> > > )
> > > ) And what reason is that?
>
> > > I don't know.  Ask the person who proposed the API upthread.
>
> > > If you insist that pop() shouldn't return a value, then push()
> > > should not take a value either, just a stack.  Otherwise it
> > > is plainly inconsistent.
>
> > pop() not returning a value makes some sense if you think that
> > shrinking the stack and retrieving the top element should be
> > separate operations.
>
> > push() without an argument would have to push an indeterminate or
> > default value onto the stack.
>
> Maybe the names are just poorly chosen. I always think of pop()
> returning the top value and shrinking the stack. I would use drop() to
> just shrink the stack. A push() without arguments could just duplicate
> the top of the stack, but then you'd be better off calling that dup().

Hmmm... Usually i like pop to just pop things off the stack, no more,
no less. I developed a strong dislike for 'two-for-one' operations. I
developed an even stronger dislike for all kinds of renaming schemes
which only obfuscate basically very simple operations. And 'dup' is a
commonly used stack primitive in it's own right, which exists neatly
alongside push, pop and top.

[toc] | [prev] | [next] | [standalone]

#6296

Kleuskes & Moos wrote:
) Hmmm... Usually i like pop to just pop things off the stack, no more,
) no less. I developed a strong dislike for 'two-for-one' operations. I
) developed an even stronger dislike for all kinds of renaming schemes
) which only obfuscate basically very simple operations. And 'dup' is a
) commonly used stack primitive in it's own right, which exists neatly
) alongside push, pop and top.

Then why should push() do two things at once ?
It extends the stack, and then places something in the top slot.
I have a strong dislike for inconsistent operations.


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

[toc] | [prev] | [next] | [standalone]

#6302

Willem <willem@toad.stack.nl> writes:
> Kleuskes & Moos wrote:
> ) Hmmm... Usually i like pop to just pop things off the stack, no more,
> ) no less. I developed a strong dislike for 'two-for-one' operations. I
> ) developed an even stronger dislike for all kinds of renaming schemes
> ) which only obfuscate basically very simple operations. And 'dup' is a
> ) commonly used stack primitive in it's own right, which exists neatly
> ) alongside push, pop and top.
>
> Then why should push() do two things at once ?
> It extends the stack, and then places something in the top slot.
> I have a strong dislike for inconsistent operations.

Because after you extend the stack, you have to put *something* in the
top slot.  Requiring the user to provide a value means you don't have to
complicate the semantics by inventing something to put there.

push() and pop() are two different operations.  They don't have to
be consistent if that consistency comes at the cost of convenience.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#6305

Keith Thompson <kst-u@mib.org> wrote:

> Because after you extend the stack, you have to put *something*
> in the top slot.  Requiring the user to provide a value means
> you don't have to complicate the semantics by inventing
> something to put there.

That's thought too short. You could also first supply a value to
be placed on the stack with the next push operation.

> push() and pop() are two different operations.  They don't have
> to be consistent if that consistency comes at the cost of
> convenience. 

So you find it convinient to be tied to a hosted implementation
where you can redirect the output to a file and then analyse
this file for getting the value of "top of stack", as you are
required with the OP's implementation?

-- Ralf

[toc] | [prev] | [next] | [standalone]

#6313

Ralf Damaschke <rwspam@gmx.de> writes:
> Keith Thompson <kst-u@mib.org> wrote:
>> Because after you extend the stack, you have to put *something*
>> in the top slot.  Requiring the user to provide a value means
>> you don't have to complicate the semantics by inventing
>> something to put there.
>
> That's thought too short. You could also first supply a value to
> be placed on the stack with the next push operation.

Seriously?

How is that supplied value associated with a particular stack?  Would
it ever make sense to do something with it other than immediately
pushing it?  What happens if you push without specifying a value?

>> push() and pop() are two different operations.  They don't have
>> to be consistent if that consistency comes at the cost of
>> convenience. 
>
> So you find it convinient to be tied to a hosted implementation
> where you can redirect the output to a file and then analyse
> this file for getting the value of "top of stack", as you are
> required with the OP's implementation?

Um, no.  I was commenting only on the question of whether push()
should take a value and whether pop() should return a value.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#6364

Keith Thompson <kst-u@mib.org> wrote:

> Ralf Damaschke <rwspam@gmx.de> writes:
>> Keith Thompson <kst-u@mib.org> wrote:
>>> Because after you extend the stack, you have to put
>>> *something* in the top slot.  Requiring the user to provide a
>>> value means you don't have to complicate the semantics by
>>> inventing something to put there.
>>
>> That's thought too short. You could also first supply a value
>> to be placed on the stack with the next push operation.
> 
> Seriously?

Not too much.

> How is that supplied value associated with a particular stack?

As usual: with a parameter specifying the stack and some storage.
 
> Would it ever make sense to do something with it other than
> immediately pushing it?

Who knows...

> What happens if you push without specifying a value?

Some error recovery, as would be also necessary when there are
more pop() than push(), or top() applied to an empty stack.

I find it strange that the question "Why would pop() not return
a value?" was answered with that's what the top() operation is for
but there was no top() either.

-- Ralf

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web