Re: Array implementation of Stack

From	Willem <willem@toad.stack.nl>
Newsgroups	comp.lang.c
Subject	Re: Array implementation of Stack
Date	2011-06-22 16:30 +0000
Organization	Stack Usenet News Service
Message-ID	<slrnj04648.1gpo.willem@toad.stack.nl> (permalink)
References	(8 earlier) <4dfc01c7$0$21771$a729d347@news.telepac.pt> <slrnivostk.2vnc.willem@toad.stack.nl> <4e015801$0$1785$a729d347@news.telepac.pt> <slrnj03al5.29pm.willem@toad.stack.nl> <lnaad9j25k.fsf@nuthaus.mib.org>

Show all headers | View raw

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

Thread

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

csiph-web