Re: [OT] Stack Operation
On Sat, 23 Nov 2002, Jonathan M. Hollin wrote: Can anyone offer me some pointers (pun intended) on how to implement a stack in Perl with an array? The description you give does not describe an 'academic' stack... You would probably need to read some good Perl books. I suggest the classical Programming Perl - Ed. O'Reilly I need to have an array of elements as follows: 0 - e1 1 - e2 2 - e3 ... @stack = (e1, e2, e3, ...) And I need to be able to insert items: e4 needs to go into $array[1]. 1 and 2 need to move down (or up or left or right - depending on how you visualise arrays) yet retain their contents: 0 - e1 1 - e4 2 - e2 3 - e3 splice @stack, 1, 0, e4; ... And, you guessed it, I need to be able to remove elements, and have the others move down... remove e2, leaving: 0 - e1 1 - e4 3 - e3 ... splice @stack, 2, 1; Franck. ESSENTIAL SOFTWARE - Ingénierie Informatique Solutions Linux Open Source en Polynésie française http://www.esoft.pf/ Tél: (689) 562 395 / 541 295 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Fiabilisez vos systèmes informatiques. Osez Linux, le choix moderne des gouvernements et des entreprises Fortune 500
Re: [OT] Stack Operation
Jonathan M. Hollin wrote to [EMAIL PROTECTED]: Can anyone offer me some pointers (pun intended) on how to implement a stack in Perl with an array? Perl has two simple builtin functions for treating an array like a stack. See push() and pop(). Basically: my @stack; push @stack, e3; push @stack, e2; push @stack, e1; print pop(@stack); print pop(@stack); print pop(@stack); Output is: e1e2e3 I need to have an array of elements as follows: 0 - e1 1 - e2 2 - e3 ... And I need to be able to insert items: e4 needs to go into $array[1]. Does it *have* to? That would be expensive. push() and pop() keep the head element at the end of the array, so push() and pop() are each O(1) operations. By rearranging the array for every push() and pop() to keep the head at [1] (or [0]), your operations are now O(n). 1 and 2 need to move down (or up or left or right - depending on how you visualise arrays) yet retain their contents: Again, expensive. I can't think of a reason you'd need to do this for a traditional stack. Even if you're extending the idea of a stack to include other functions, you probably just need to reverse your logic to start from the last element of the array. And, you guessed it, I need to be able to remove elements, and have the others move down... pop() How do I implement this in code anyone? See above. push() and pop() are very simple functions you could write yourself in about 1 line apiece. Fortunately, you don't have to. :-) - Ryan -- Ryan Thompson [EMAIL PROTECTED] SaskNow Technologies - http://www.sasknow.com 901 1st Avenue North - Saskatoon, SK - S7K 1Y4 Tel: 306-664-3600 Fax: 306-244-7037 Saskatoon Toll-Free: 877-727-5669 (877-SASKNOW) North America
RE: [OT] Stack Operation
Tim Tompkins wrote to Ben Mathews: Honestly, I didn't see where any of those libs would assist what the poster wanted to accomplish. What's wrong with splice? For implementing a traditional stack, the splice operation (or any operation which has to rearrange the list every time an element is pushed or popped) will be much more expensive than the constant-time push() and pop(). That, and push()/pop() have the benefit of abstracting the underlying data representation. :-) The idea in any memory stack implementation is to not have to move the elements. You can abstract away from that to make more sense for a given application, but, in memory, you still want the growth end of the stack to be variable. If you don't buy any of that, unshift() and shift() instead, for the O(n) versions of push() and pop(). :-) - Ryan -- Ryan Thompson [EMAIL PROTECTED] SaskNow Technologies - http://www.sasknow.com 901 1st Avenue North - Saskatoon, SK - S7K 1Y4 Tel: 306-664-3600 Fax: 306-244-7037 Saskatoon Toll-Free: 877-727-5669 (877-SASKNOW) North America
Re: [OT] Stack Operation
But push()ing and pop()ing is not what the original poster wants to do. He wants to splice(). It doesn't matter if he's talking about treating a stack in the traditional sense, and it doesn't matter that splice is not as efficient as push or pop. What matters is that he knows how to accomplish what he requested. -- Tim Tompkins
Re: [OT] Stack Operation
Tim Tompkins wrote: But push()ing and pop()ing is not what the original poster wants to do. He wants to splice(). It doesn't matter if he's talking about treating a stack in the traditional sense, and it doesn't matter that splice is not as efficient as push or pop. What matters is that he knows how to accomplish what he requested. Any chance you can find a more appropriate forum for discussing perl basic things? Thank you! __ Stas BekmanJAm_pH -- Just Another mod_perl Hacker http://stason.org/ mod_perl Guide --- http://perl.apache.org mailto:[EMAIL PROTECTED] http://use.perl.org http://apacheweek.com http://modperlbook.org http://apache.org http://ticketmaster.com
RE: [OT] Stack Operation
Don't reinvent the wheel. http://search.cpan.org/search?query=stackmode=module Ben -Original Message- From: Jonathan M. Hollin [mailto:[EMAIL PROTECTED]] Sent: Saturday, November 23, 2002 6:59 AM To: [EMAIL PROTECTED] Subject: [OT] Stack Operation Can anyone offer me some pointers (pun intended) on how to implement a stack in Perl with an array? I need to have an array of elements as follows: 0 - e1 1 - e2 2 - e3 ... And I need to be able to insert items: e4 needs to go into $array[1]. 1 and 2 need to move down (or up or left or right - depending on how you visualise arrays) yet retain their contents: 0 - e1 1 - e4 2 - e2 3 - e3 ... And, you guessed it, I need to be able to remove elements, and have the others move down... remove e2, leaving: 0 - e1 1 - e4 3 - e3 ... How do I implement this in code anyone? -- Jonathan M. Hollin Technical Director: Digital-Word Co. (http://digital-word.com/) Co-ordinator: WYPUG (http://wypug.pm.org/)
RE: [OT] Stack Operation
Honestly, I didn't see where any of those libs would assist what the poster wanted to accomplish. What's wrong with splice? -- Tim On Sat, 2002-11-23 at 09:03, Ben Mathews wrote: Don't reinvent the wheel. http://search.cpan.org/search?query=stackmode=module Ben -Original Message- From: Jonathan M. Hollin [mailto:[EMAIL PROTECTED]] Sent: Saturday, November 23, 2002 6:59 AM To: [EMAIL PROTECTED] Subject: [OT] Stack Operation Can anyone offer me some pointers (pun intended) on how to implement a stack in Perl with an array? I need to have an array of elements as follows: 0 - e1 1 - e2 2 - e3 ... And I need to be able to insert items: e4 needs to go into $array[1]. 1 and 2 need to move down (or up or left or right - depending on how you visualise arrays) yet retain their contents: 0 - e1 1 - e4 2 - e2 3 - e3 ... And, you guessed it, I need to be able to remove elements, and have the others move down... remove e2, leaving: 0 - e1 1 - e4 3 - e3 ... How do I implement this in code anyone? -- Jonathan M. Hollin Technical Director: Digital-Word Co. (http://digital-word.com/) Co-ordinator: WYPUG (http://wypug.pm.org/) -- Tim Tompkins [EMAIL PROTECTED]
