Re: Meaning of Pop() in a Queue
- From: Michael Ekstrand <michael@xxxxxxxxxxx>
- Date: Sat, 16 May 2009 11:14:48 -0500
arnuld <sunrise@xxxxxxxxxxxxxxx> writes:
I have implemented a Queue as Singly Linked List, down here is the code
and it works fine. My friend argued with me that the operation I have
named list_remove_element() is actually a pop() and list_add_element() is
actually should be named push(). He even argues that my
list_remove_element() should not free() any element but instead it should
only remove the link of that element from the queue and the 2rd party
programs/software who is going to use that element should free it. I think
if I am allocating some memory for some element then its the
responsibility of my program to free it, not of 3rd party's.
2nd, I really don't get it, Aho, Hopcraft and Ullman's "Data Structures
and Algorithms" says the operations pop() and push() belong to Stack, not
queue (Section 2.3). Queue has operations like front(), enqueue() and
dequeue() (Section 2.4) and even then authors advise against using pop()
in a Stack.
1) Am I right in removing the element and freeing it allocated
memory ?
That's a design decision, different philosophies and libraries will
probably choose differently. I tend to prefer having the list free the
element as it keeps the abstraction tighter.
2) Am I right in not implementing pop() but call_remove_element() or
deqeue() ?
I definitely prefer to see remove_element or dequeue. I find pop
confusing. Given the prior art using push/pop for queues, you would be
keeping with some tradition by naming it "pop", but I find that
confusing. And in either case, the advice that you "should" call it
"pop" is just flat wrong. You may call it pop, but saying you "should"
use confusing terminology is highly dubious advice indeed. The
algorithms and data structures textbooks I have looked at tend to call
it add/remove or enqueue/dequeue (or enq/deq).
- Michael
--
mouse, n: A device for pointing at the xterm in which you want to type.
Confused by the strange files? I cryptographically sign my messages.
For more information see <http://www.elehack.net/resources/gpg>.
.
- References:
- Meaning of Pop() in a Queue
- From: arnuld
- Meaning of Pop() in a Queue
- Prev by Date: Re: binary tree question
- Next by Date: Re: binary tree question
- Previous by thread: Re: Meaning of Pop() in a Queue
- Next by thread: binary tree question
- Index(es):
Relevant Pages
|
