[erlang-questions] queues (previously: documentation of data structures)

Andras Georgy Bekes <>
Tue Dec 11 13:44:25 CET 2007


> The first step would be implementing a new data type: `cell' with operations such as
> - - cell:empty/0 (create an empty cell)
> - - cell:make/1 (create a cell with a given contents)
> - - cell:get/1 (non-destructively get the contents of a cell. Block (or throw an error or some
> predefined value if it is empty)
> - - cell:put/2 (destructively overwrite a cell with a given value)
> Basically, cell can be represented as a process that responds to proper messages. There can be
> wrapper procedures
> - - cell:/isEmpty/1 returns true if a given cell is empty
> 
> If you have cells, you can implement `queue item' as a triple composed from:
> - - a cell containing a reference to the previous `queue item'
> - - a cell containing a reference to the value of the current `queue item'
> - - a cell containing a reference to the next `queue item'.
> 
> If you have that, you can represent the whole queue as a couple composed from:
> - - a cell containing a reference to the head
> - - a cell containing a reference to the tail

Why having a process for each queue entry???
Ok, you can change a specific element once you've put on the
queue, but you probably don't want that.

Why not just use the message queue of Erlang?
(see attached module --- very simple)

Pros:
- one process for each queue
- same efficiency as the message queues of the VM
  (hope you're satisfied with that)
- works when several processes use a common queue

Cons:
- copies each queued element twice (just like your solution)
- ???

	Georgy
-------------- next part --------------
-module(myqueue).

-export([start/0,init/0,put/2,get/1,delete/1]).

start()->
    spawn(?MODULE,init,[]).

init()->
    loop().

loop()->
    receive
	{getnext,PID} ->
	    receive
		{element, Data} ->
		    PID ! {element,Data};
		stop ->
		    ok
	    end;
	stop->
	    ok
    end,
    loop().


put(Queue,Data)->
    Queue ! {element,Data},
    ok.

get(Queue)->
    Queue ! {getnext,self()},
    receive
	{element,Data}->
	    Data
    end.

delete(Queue)->
    Queue ! stop,
    ok.


More information about the erlang-questions mailing list