[Tutor] confused by linked queue

[Carroll, Barry]

Danny, et al:


> -----Original Message-----
> Date: Tue, 25 Jul 2006 15:43:34 -0700 (PDT)
> From: Danny Yoo <dyoo at hkn.eecs.berkeley.edu>
> Subject: Re: [Tutor] confused by linked queue
> To: Christopher Spears <cspears2002 at yahoo.com>
> Cc: Tutor <tutor at python.org>
> Message-ID: <Pine.LNX.4.64.0607251510020.22412 at hkn.eecs.berkeley.edu>
> Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
> 
> > One of my problems in conecptualizing this is that I thought a
linked
> > queue was just a linked list.  Is a linked queue a linked list?
There
> > seems to be a subtle difference...
> 
> Hi Chris,
> 
> I think you mean to ask:
> 
>      Is a "queue" a linked list?
> 
> 
> Here's another particular possible queue class that does something
> similar, but with Python's regular lists rather than a linked list:
> 
> ######################################
> class ArrayQueue:
>      def __init__(self):
>          self.elements = []
> 
>      def isEmpty(self):
>          return len(self.elements) == 0
> 
>      def insert(self, elt):
>          self.elements.append(elt)
> 
>      def remove(self):
>          return self.elements.pop(0)
> ######################################
> 
> This works on a different principle than the linked list queue, but it
> does the same stuff.  The main idea is that a "queue" can be anything,
as
> long as it supports three operations:
> 
>      * isEmpty
>      * insert
>      * remove
> 
<<snip>>

Isn't there a fourth operation needed?

	* isFull  

Even in Python (where the underlying data structure can grow on the fly,
there is a physical upper limit: the size of the heap or stack.  This
condition needs to be handled gracefully. 

Regards,

Barry
barry.carroll at psc.com
541-302-1107
________________________
We who cut mere stones must always be envisioning cathedrals.

-Quarry worker's creed