Queue/Definition: Difference between revisions

[[File:Fifo.gif|frame|right|Illustration of FIFO behavior]]

 

Operations:

 

Errors:

 

 

=={{header|Ada}}==

 

The interface specification for a FIFO is described in the package specification.

type Element_Type is private;

package Fifo is

Next : Fifo_Ptr := null;

end record;

The FIFO implementation is described in the package body:

 

package body Fifo is

end Is_Empty;

 

A "main" procedure for this program is:

with Ada.Text_Io; use Ada.Text_Io;

 

Put_Line(Integer'Image(Val));

end loop;

The following implementation produces equivalent functionality by deriving from the standard Ada Container type Doubly_Linked_Lists.

 

This example needs fewer lines of code on the part of the application programmer, but the implementation is less efficient than the previous example. Each element has all the data members needed for a doubly linked list. It also links in all the functionality of a doubly linked list. Most of that functionality is unneeded in a FIFO.

with Ada.Containers.Doubly_Linked_Lists;

generic

Type Fifo_Type is new List with null record;

end Generic_Fifo;

package body Generic_Fifo is

end Pop;

with Ada.Text_Io; use Ada.Text_Io;

 

Put_Line(Integer'Image(Val));

end loop;

The function Is_Empty is inherited from the Lists type.

 

 

If we wish for the reader to read every value written by the writer we must synchronize the tasks. The writer can only write a new value when the buffer contains a stale value. The reader can only read a value when the value is fresh. This synchronization forces the two tasks to run at the same speed.

type Element_Type is private;

package Synchronous_Fifo is

Is_New : Boolean := False;

end Fifo;

 

----------

end Fifo;

 

with Ada.Text_Io; use Ada.Text_Io;

 

Writer.Stop;

Reader.Stop;

Another choice is to cause the two tasks to run independently. The writer can write whenever it is scheduled. The reader reads whenever it is scheduled, after the writer writes the first valid value.

 

 

In a fully asynchronous system the reader only samples the values written by the writer. There is no control over the number of values not sampled by the reader, or over the number of times the reader reads the same value.

type Element_Type is private;

package Asynchronous_Fifo is

Valid : Boolean := False;

end Fifo;

You may notice that the protected type specification is remarkably similar to the synchronous example above. The only important difference is that Push is declared to be an Entry in the synchronous example while it is a procedure in the asynchronous example. Entries only execute when their boundary condition evaluates to TRUE. Procedures execute unconditionally.

 

----------

end Fifo;

 

with Ada.Text_Io; use Ada.Text_Io;

 

Put_Line(Integer'Image(Val));

end select;

end Reader;

begin

Writer.Stop;

Reader.Stop;

 

=={{header|AutoHotkey}}==

 

MsgBox % "Len = " len("qu") ; Number of entries

StringReplace %queue%, %queue%, |, |, UseErrorLevel

Return %queue% = "" ? 0 : ErrorLevel+1

 

=={{header|C}}==

Using the <tt>sys/queue.h</tt>, which is not POSIX.1-2001 (but it is BSD). The example allows to push/pop int values, but instead of <tt>int</tt> one can use <tt>void *</tt> and push/pop any kind of "object" (of course changes to the commodity functions <tt>m_queue</tt> and <tt>m_dequeue</tt> are needed)

 

#include <stdlib.h>

#include <stdbool.h>

if ( l->tqh_first == NULL ) return true;

return false;

 

=={{header|C++}}==

{{works with|g++|4.1.2 20061115 (prerelease) (Debian 4.1.1-21)}}

C++ already has a class <code>queue</code> in the standard library, however the following is a simple implementation based on a singly linkes list. Note that an empty queue is internally represented by <code>head == 0</code>, therefore it doesn't matter that the <code>tail</code> value is invalid in that case.

{

template<typename T> class queue

return head == 0;

}

 

 

 

 

 

 

 

 

=={{header|Common Lisp}}==

This defines a queue structure that stores its items in a list, and maintains a tail pointer (i.e., a pointer to the last cons in the list). Note that dequeuing the last item in the queue does not clear the tail pointer—enqueuing into the resulting empty queue will correctly reset the tail pointer.

 

(items '() :type list)

(tail '() :type list))

(if (queue-empty-p queue)

(error "Cannot dequeue from empty queue.")

 

=={{header|D}}==

 

 

=={{header|E}}==

 

Also, according to E design principles, the read and write ends of the queue are separate objects. This has two advantages; first, it implements [http://wiki.erights.org/wiki/POLA POLA] by allowing only the needed end of the queue to be handed out to its users; second, if the reader end is garbage collected the contents of the queue automatically will be as well (rather than accumulating if the writer continues writing).

 

def [var head, var tail] := Ref.promise()

 

return [reader, writer]

 

=={{header|Erlang}}==

-export([new/0, push/2, pop/1, empty/1]).

 

 

empty({fifo, [], []}) -> true;

 

Note that there exists a 'queue' module in the standard library handling this for you in the first place

 

=={{header|Fantom}}==

 

class Queue

{

}

}

 

=={{header|Forth}}==

This is a FIFO implemented as a circular buffer, as is often found between communicating processes such the interrupt and user parts of a device driver. In practice, the get/put actions would block instead of aborting if the queue is empty/full.

 

create buffer size cells allot

here constant end

empty? abort" buffer empty"

\ begin empty? while pause repeat

 

=={{header|Fortran}}==

See [[FIFO (usage)]] for an example of <code>fifo_nodes</code>

 

use fifo_nodes

! fifo_nodes must define the type fifo_node, with the two field

end function fifo_isempty

 

=={{header|Go}}==

Hard coded to be a queue of strings. Implementation is a circular buffer which grows as needed.

package queue

 

return q.head == q.tail

}

 

=={{header|Haskell}}==

 

 

 

emptyFifo :: Fifo a

isEmpty (F [] []) = True

isEmpty _ = False

 

=={{header|J}}==

Object oriented technique, using mutable state:

 

 

pop_fifo_=: verb define

isEmpty_fifo_=: verb define

0=#queue

 

Function-level technique, with no reliance on mutable state:

 

push =: ( '' ; ,~ )& > /

tell_atom =: >& {.

onto =: [ ; }.@]

 

 

See also [[FIFO (usage)#J]]

{{works with|Java|1.5+}}

This task could be done using a LinkedList from java.util, but here is a user-defined version with generics:

 

 

 

 

 

 

 

 

=={{header|JavaScript}}==

 

=== Using built-in Array ===

fifo.push(42); // Enqueue.

fifo.push(43);

var x = fifo.shift(); // Dequeue.

 

=== Custom constructor function ===

this.data = new Array();

 

this.enqueue = this.push;

this.dequeue = this.pop;

=={{header|Lua}}==

 

function Queue.new()

function Queue.empty( queue )

return queue.first > queue.last

 

 

classdef FIFOQueue

end %methods

 

Sample usage:

myQueue =

 

>> push(myQueue,'jello')

>> pop(myQueue)

??? Error using ==> FIFOQueue.FIFOQueue>FIFOQueue.pop at 61

 

=={{header|OCaml}}==

 

 

type 'a fifo

val empty: 'a fifo

| [], [] -> failwith "empty fifo"

| input, [] -> pop ([], List.rev input)

 

and a session in the top-level:

 

# let q = empty ;;

val q : '_a FIFO.fifo = <abstr>

val q : int FIFO.fifo = <abstr>

# let v, q = pop q ;;

 

The standard ocaml library also provides a

[http://caml.inria.fr/pub/docs/manual-ocaml/libref/Queue.html FIFO module],

but it is ''imperative'', unlike the implementation above which is ''functional''.