s c h e m a t i c s : c o o k b o o k

/ Cookbook.ImperativeQueues

This Web


WebHome 
WebChanges 
TOC (with recipes)
NewRecipe 
WebTopicList 
WebStatistics 

Other Webs


Chicken
Cookbook
Erlang
Know
Main
Plugins
Sandbox
Scm
TWiki  

Schematics


Schematics Home
Sourceforge Page
SchemeWiki.org
Original Cookbook
RSS

Scheme Links


Schemers.org
Scheme FAQ
R5RS
SRFIs
Scheme Cross Reference
PLT Scheme SISC
Scheme48 SCM
MIT Scheme scsh
JScheme Kawa
Chicken Guile
Bigloo Tiny
Gambit LispMe
GaucheChez

Lambda the Ultimate
TWiki.org

Imperative Queues

Problem

A queue is a first-in first-out memory. Objects can be stored one by one and can be extracted (or removed) one by one. Objects are extracted (or removed) in the same time order as they are stored. How to implement a queue with constant access time, i.e. independent of the length of the queue? (Compare this problem with that of recipe FunctionalQueue).

Solution

The solution shown in this recipe is in essence the same as described in section 3.3.2 of SICP. However, in this recipe the word 'pointer' is avoided. Each queue will have its own set of six procedures, say queue-empty?, queue-enter!, queue-extract!, queue-peek, queue-remove! and queue->list.

These six procedures share access to a freshly allocated queue. The queue can be accessed by means of these six procedures only. Every distinct queue has its own distinct set of six procedures. Initially the queue is empty. When the queue is empty, the procedures queue-extract!, queue-peek or queue-remove! return whatever is returned by the thunk or signal an error if no thunk is supplied. The procedures are prepared by means of procedure make-queue:

(make-queue [string]) → multiple value of six procedures

The optional string is used in error messages in order to identify the queue. It has no other use. The default string is "no name".

The internal representation for the queue is a mutable list containing the entered objects in the reversed order, i.e. the most recent one at the end and the oldest one at the start. Procedure queue-enter! appends an object at the end of the queue. This is done in situ (i.e. destructively) Procedures queue-extract!, queue-peek and queue-remove! apply to the first element of the queue. Procedures queue-extract! and queue-remove! replace the queue by its cdr, thus removing the oldest element. A simple, but inefficient implementation (without names, thunks or error-detection) is

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

In this implementation, procedure queue-enter! is inefficient, because it calls procedure last-pair, which does a full traversal of the queue. In order to avoid this traversal, the last pair must be memorized:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

Example of use:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

Now it is a matter of routine in order to prepare the full implemention, name, thunk arguments and error detection included:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

A good alternative is to implement the queues as a class of objects with two private variables queue and last-pair and methods empty?, enter!, extract!, peek, remove!, queue->list and name:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)


Comments about this recipe

Very welcome. Code adapted to MzScheme version 3.99.0.9. All code requires: (require scheme/mpair) JosKoot 09-01-2008

Contributors

-- JosKoot - 11 October 2006

CookbookForm
TopicType: Recipe
ParentTopic: DataStructureRecipes
TopicOrder: 999

 
 
Copyright © 2004 by the contributing authors. All material on the Schematics Cookbook web site is the property of the contributing authors.
The copyright for certain compilations of material taken from this website is held by the SchematicsEditorsGroup - see ContributorAgreement & LGPL.
Other than such compilations, this material can be redistributed and/or modified under the terms of the GNU Lesser General Public License (LGPL), version 2.1, as published by the Free Software Foundation.
Ideas, requests, problems regarding Schematics Cookbook? Send feedback.
/ You are Main.guest