Queue/Definition

Queue/Definition
You are encouraged to solve this task according to the task description, using any language you may know.

Data Structure
This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.

Illustration of FIFO behavior

Implement a FIFO queue. Elements are added at one side and popped from the other in the order of insertion.

Operations:

• push (aka enqueue) - add element
• pop (aka dequeue) - pop first element
• empty - return truth value when empty

Errors:

• handle the error of trying to pop from an empty queue (behavior depends on the language and platform)

Ada

The first example below demonstrates a FIFO created for single-threaded computing. This version has the advantage of using a minimum of memory per FIFO element, and being very fast.

The interface specification for a FIFO is described in the package specification. <lang ada>generic

  type Element_Type is private;

package Fifo is

  type Fifo_Type is private;
  procedure Push(List : in out Fifo_Type; Item : in Element_Type);
  procedure Pop(List : in out Fifo_Type; Item : out Element_Type);
  function Is_Empty(List : Fifo_Type) return Boolean;
  Empty_Error : exception;

private

  type Fifo_Element;
  type Fifo_Ptr is access Fifo_Element;
  type Fifo_Type is record
     Head : Fifo_Ptr := null;
     Tail : Fifo_Ptr := null;
  end record;
  type Fifo_Element is record
     Value : Element_Type;
     Next  : Fifo_Ptr := null;
  end record;

end Fifo;</lang> The FIFO implementation is described in the package body: <lang ada>with Ada.Unchecked_Deallocation;

package body Fifo is

  ----------
  -- Push --
  ----------

  procedure Push (List : in out Fifo_Type; Item : in Element_Type) is
     Temp : Fifo_Ptr := new Fifo_Element'(Item, null);
  begin
     if List.Tail = null then
        List.Tail := Temp;
     end if;
     if List.Head /= null then
       List.Head.Next := Temp;
     end if;
     List.Head := Temp;
  end Push;

  ---------
  -- Pop --
  ---------

  procedure Pop (List : in out Fifo_Type; Item : out Element_Type) is
     procedure Free is new Ada.Unchecked_Deallocation(Fifo_Element, Fifo_Ptr);
     Temp : Fifo_Ptr := List.Tail;
  begin
     if List.Head = null then
        raise Empty_Error;
     end if;
     Item := List.Tail.Value;
     List.Tail := List.Tail.Next;
     if List.Tail = null then
        List.Head := null;
     end if;
     Free(Temp);
  end Pop;

  --------------
  -- Is_Empty --
  --------------

  function Is_Empty (List : Fifo_Type) return Boolean is
  begin
     return List.Head = null;
  end Is_Empty; 

end Fifo;</lang> A "main" procedure for this program is: <lang ada>with Fifo; with Ada.Text_Io; use Ada.Text_Io;

procedure Fifo_Test is

  package Int_Fifo is new Fifo(Integer);
  use Int_Fifo;
  My_Fifo : Fifo_Type;
  Val : Integer;

begin

  for I in 1..10 loop
     Push(My_Fifo, I);
  end loop;
  while not Is_Empty(My_Fifo) loop
     Pop(My_Fifo, Val);
     Put_Line(Integer'Image(Val));
  end loop;

end Fifo_Test;</lang> 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. <lang ada> with Ada.Containers.Doubly_Linked_Lists;

generic
   type Element_Type is private;
package Generic_Fifo is
   type Fifo_Type is tagged private;
   procedure Push(The_Fifo : in out Fifo_Type; Item : in Element_Type);
   procedure Pop(The_Fifo : in out Fifo_Type; Item : out Element_Type);
   Empty_Error : Exception;
private
   package List_Pkg is new Ada.Containers.Doubly_Linked_Lists(Element_Type);
   use List_Pkg;
   Type Fifo_Type is new List with null record;
end Generic_Fifo;

</lang ada> <lang ada>

package body Generic_Fifo is

   ----------
   -- Push --
   ---------- 

   procedure Push (The_Fifo : in out Fifo_Type; Item : in Element_Type) is
   begin
      The_Fifo.Prepend(Item);
   end Push;

   ---------
   -- Pop --
   ---------

   procedure Pop (The_Fifo : in out Fifo_Type; Item : out Element_Type) is
   begin
      if Is_Empty(The_Fifo) then
         raise Empty_Error;
      end if;
      Item := The_Fifo.Last_Element;
      The_Fifo.Delete_Last;
   end Pop;

end Generic_Fifo;</lang>

<lang ada>with Generic_Fifo; with Ada.Text_Io; use Ada.Text_Io;

procedure Generic_Fifo_Test is

  package Int_Fifo is new Generic_Fifo(Integer);
  use Int_Fifo;
  My_Fifo : Fifo_Type;
  Val : Integer;

begin

  for I in 1..10 loop
     My_Fifo.Push(I);
  end loop;
  while not My_Fifo.Is_Empty loop
     My_Fifo.Pop(Val);
     Put_Line(Integer'Image(Val));
  end loop;

end Generic_Fifo_Test;</lang> The function Is_Empty is inherited from the Lists type.

The next two examples provide simple FIFO functionality for concurrent tasks. The buffer in each example holds a single value. When running concurrent tasks, one writing to the buffer, and one reading from the buffer, either the writer will be faster than the reader, or the reader will be faster than the writer. If the writer is faster a dynamic FIFO will grow to consume all available memory on the computer. If the reader is faster the FIFO will either contain a single value or it will be empty. In either case, no implementation is more efficient than a single element buffer.

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. <lang ada>generic

  type Element_Type is private;

package Synchronous_Fifo is

  protected type Fifo is
     entry Push(Item : Element_Type);
     entry Pop(Item : out Element_Type);
  private
     Value : Element_Type;
     Is_New : Boolean := False;
  end Fifo;

end Synchronous_Fifo;</lang> <lang ada>package body Synchronous_Fifo is

  ----------
  -- Fifo --
  ----------

  protected body Fifo is 

     ---------
     -- Push --
     ---------

     entry Push (Item : Element_Type) when not Is_New is
     begin
        Value := Item;
        Is_New := True;
     end Push; 

     ---------
     -- Pop --
     ---------

     entry Pop (Item : out Element_Type) when Is_New is
     begin
        Item := Value;
        Is_New := False;
     end Pop; 

  end Fifo;

end Synchronous_Fifo;</lang> <lang ada>with Synchronous_Fifo; with Ada.Text_Io; use Ada.Text_Io;

procedure Synchronous_Fifo_Test is
   package Int_Fifo is new Synchronous_Fifo(Integer);
   use Int_Fifo;
   Buffer : Fifo;
   
   task Writer is
      entry Stop;
   end Writer;
   
   task body Writer is
      Val : Positive := 1;
   begin
      loop
         select
            accept Stop;
            exit;
         else
            select
               Buffer.Push(Val);
               Val := Val + 1;
            or
               delay 1.0;
            end select;
         end select;
      end loop;
   end Writer;
   
   task Reader is
      entry Stop;
   end Reader;
   
   task body Reader is
      Val : Positive;
   begin
      loop
         select
            accept Stop;
            exit;
         else
            select
               Buffer.Pop(Val);
               Put_Line(Integer'Image(Val));
            or
                delay 1.0;
           end select;
         end select;
      end loop;
   end Reader;
begin
   delay 0.1;
   Writer.Stop;
   Reader.Stop;
end Synchronous_Fifo_Test;</lang>

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 this example the writer writes several values before the reader reads a value. The reader will then read that same value several times before the writer is scheduled to write more values.

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. <lang ada>generic

  type Element_Type is private;

package Asynchronous_Fifo is

  protected type Fifo is
     procedure Push(Item : Element_Type);
     entry Pop(Item : out Element_Type);
  private
     Value : Element_Type;
     Valid : Boolean := False;
  end Fifo;

end Asynchronous_Fifo;</lang> 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. <lang ada>package body Asynchronous_Fifo is

  ----------
  -- Fifo --
  ----------

  protected body Fifo is 

     ----------
     -- Push --
     ----------

     procedure Push (Item : Element_Type) is
     begin
         Value := Item;
        Valid := True;
     end Push;

     ---------
     -- Pop --
     ---------

     entry Pop (Item : out Element_Type) when Valid is
     begin
        Item := Value;
     end Pop;

  end Fifo; 

end Asynchronous_Fifo;</lang> <lang ada>with Asynchronous_Fifo; with Ada.Text_Io; use Ada.Text_Io;

procedure Asynchronous_Fifo_Test is
   package Int_Fifo is new Asynchronous_Fifo(Integer);
   use Int_Fifo;
   Buffer : Fifo;
   
   task Writer is
      entry Stop;
   end Writer;
   
   task body Writer is
      Val : Positive := 1;
   begin
      loop
         select
            accept Stop;
            exit;
         else
            Buffer.Push(Val);
            Val := Val + 1;
         end select;
      end loop;
   end Writer;
   
   task Reader is
      entry Stop;
   end Reader;
   
   task body Reader is
      Val : Positive;
   begin
      loop
         select 
            accept Stop;
            exit;
         else
            Buffer.Pop(Val);
            Put_Line(Integer'Image(Val));
         end select;
      end loop;
   end Reader;
begin
   delay 0.1;
   Writer.Stop;
   Reader.Stop;
end Asynchronous_Fifo_Test;</lang>

AutoHotkey

ahk forum: discussion <lang AutoHotkey>push("st",2),push("st",4)  ; TEST: push 2 and 4 onto stack named "st" While !empty("st")  ; Repeat until stack is not empty

  MsgBox % pop("st")       ; Print popped values (4, 2)

MsgBox % pop("st")  ; Empty MsgBox %ErrorLevel%  ; ErrorLevel = 1: popped too much

push(stack,x) {  ; push x onto stack named "stack"

  Local _ ;
  _ :=  %stack%0 := %stack%0="" ? 1 : %stack%0+1
  %stack%%_% := x

} pop(stack) {  ; pop value from stack named "stack"

  Local _ ;
  _ := %stack%0
  If (_ < 1)
     Return "", ErrorLevel := 1
  Return %stack%%_%,  %stack%0 := _-1

} empty(stack) {  ; check if stack named "stack" is empty

  Global
  Return %stack%0<1

}</lang>

C

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

<lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <stdbool.h>

1. include <sys/queue.h>

struct entry {

 int value;
 TAILQ_ENTRY(entry) entries;

};

typedef struct entry entry_t;

TAILQ_HEAD(FIFOList_s, entry);

typedef struct FIFOList_s FIFOList;

bool m_enqueue(int v, FIFOList *l) {

 entry_t *val;
 val = malloc(sizeof(entry_t));
 if ( val != NULL ) {
   val->value = v;
   TAILQ_INSERT_TAIL(l, val, entries);
   return true;
 }
 return false;

}

bool m_dequeue(int *v, FIFOList *l) {

 entry_t *e = l->tqh_first;
 if ( e != NULL ) {
   *v = e->value;
   TAILQ_REMOVE(l, e, entries);
   free(e);
   return true;
 }
 return false;

}

bool isQueueEmpty(FIFOList *l) {

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

}</lang>

C++

Works with: g++ version 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)

C++ already has a class queue 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 head == 0, therefore it doesn't matter that the tail value is invalid in that case. <lang cpp>namespace rosettacode {

 template<typename T> class queue
 {
 public:
   queue();
   ~queue();
   void push(T const& t);
   T pop();
   bool empty();
 private:
   void drop();
   struct node;
   node* head;
   node* tail;
 };

 template<typename T> struct queue<T>::node
 {
   T data;
   node* next;
   node(T const& t): data(t), next(0) {}
 };

 template<typename T>
  queue<T>::queue():
   head(0)
 {
 }

 template<typename T>
  inline void queue<T>::drop()
 {
   node* n = head;
   head = head->next;
   delete n;
 }

 template<typename T>
  queue<T>::~queue()
 {
   while (!empty())
     drop();
 }

 template<typename T>
  void queue<T>::push(T const& t)
 {
   node*& next = head? tail->next : head;
   next = new node(t);
   tail = next;
 }

 template<typename T>
  T queue<T>::pop()
 {
   T tmp = head->data;
   drop();
   return tmp;
 }

 template<typename T>
  bool queue<T>::empty()
 {
   return head == 0;
 }

}</lang>

C#

Compatible with C# 3.0 specification, requires System library for exceptions (from either .Net or Mono). A FIFO class in C# using generics and nodes. <lang csharp>public class FIFO<T> {

 class Node
 {
   public T Item { get; set; }
   public Node Next { get; set; }
 }
 Node first = null;
 Node last = null;
 public void push(T item)
 {
   if (empty())
   {
     //Uses object initializers to set fields of new node
     first = new Node() { Item = item, Next = null };
     last = first;
   }
   else
   {
     last.Next = new Node() { Item = item, Next = null };
     last = last.Next;
   }
 }
 public T pop()
 {
   if (first == null)
     throw new System.Exception("No elements"); 
   if (last == first)
     last = null;
   T temp = first.Item;
   first = first.Next;
   return temp;
 }
 public bool empty()
 {
   return first == null;
 }

}</lang>

Clojure

The "pop" function implies mutating the input, but since Clojure data structures are immutable we use a mutable reference to an immutable data structure; in this case an atom holding a vector:

<lang lisp>(defn make-queue []

 (atom []))

(defn enqueue [q x]

 (swap! q conj x))

(defn dequeue [q]

 (if (seq @q)
   (let [x (first @q)] 
     (swap! q subvec 1)
     x)
   (throw (IllegalStateException. "Can't pop an empty queue."))))

(defn queue-empty? [q]

 (empty? @q))</lang>

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.

<lang lisp>(defstruct (queue (:constructor %make-queue))

 (items '() :type list)
 (tail '() :type list))

(defun make-queue ()

 "Returns an empty queue."
 (%make-queue))

(defun queue-empty-p (queue)

 "Returns true if the queue is empty."
 (endp (queue-items queue)))

(defun enqueue (item queue)

 "Enqueue item in queue. Returns the queue."
 (prog1 queue
   (if (queue-empty-p queue)
     (setf (queue-items queue) (list item)
           (queue-tail queue) (queue-items queue))
     (setf (cdr (queue-tail queue)) (list item)
           (queue-tail queue) (cdr (queue-tail queue))))))

(defun dequeue (queue)

 "Dequeues an item from queue. Signals an error if queue is empty."
 (if (queue-empty-p queue)
   (error "Cannot dequeue from empty queue.")
   (pop (queue-items queue))))</lang>

D

Implemented a queue class, by reusing previous stack class definition. See Stack#D. <lang d>module stack ; class Stack(T){ ...

 void push(T top) { ... }
 T pop() { ... }
 bool empty() { ... } 

}</lang> <lang d>module fifo ; import stack ; class FIFO(T) : Stack!(T){

 override T pop() {
   if (empty)
     throw new Exception("FIFO Empty") ;
   T top = content[0] ;
   content = content[1..$] ;
   return top ;
 }
 alias push enqueue ;
 alias pop dequeue ;

}</lang> Statement content = content[1..$] is efficient enough, because no array content is moved/copyed, but pointer modified.

Using the Singly-Linked List (element): <lang d>module fifolink ; class FIFOLinked(T) {

 alias Node!(T) Node;
 private Node head = null;
 private Node tail = null;
 void push(T last) {
   head = new Node(last, head);
   if (tail is null)
     tail = head;
 }
 T pop() {
   if(empty)
     throw new Exception("FIFO Empty") ;
   T first = head.data;
   if (head is tail) // is last one?
     tail = null;   // release tail reference so that GC can collect afterward
   head = head.next;
   return first;
 }
 bool empty() { return head is null; }
 alias push enqueue ;
 alias pop dequeue ;

}</lang>

E

This uses a linked list representation of queues, hanging onto both ends of the list, except that the next-link reference is an E promise rather than a mutable slot.

Also, according to E design principles, the read and write ends of the queue are separate objects. This has two advantages; first, it implements 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).

<lang e>def makeQueue() {

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

 def writer {
   to enqueue(value) {
     def [nh, nt] := Ref.promise()
     tail.resolve([value, nh])
     tail := nt
   }
 }

 def reader {
   to empty() { return !Ref.isResolved(head) }

   to dequeue(whenEmpty) {
     if (Ref.isResolved(head)) {
       def [value, next] := head
       head := next
       return value
     } else {
       throw.eject(whenEmpty, "pop() of empty queue")
     }
   }
 }
 
 return [reader, writer]

}</lang>

Erlang

The standard way to manage fifo in functional programming is to use a pair of list for the fifo queue, one is the input, the other is the output. When the output is empty just take the input list and reverse it. <lang Erlang>-module(fifo). -export([new/0, push/2, pop/1, empty/1]).

new() -> {fifo, [], []}.

push({fifo, In, Out}, X) -> {fifo, [X|In], Out}.

pop({fifo, [], []}) -> erlang:error('empty fifo'); pop({fifo, In, []}) -> pop({fifo, [], lists:reverse(In)}); pop({fifo, In, [H|T]}) -> {H, {fifo, In, T}}.

empty({fifo, [], []}) -> true; empty({fifo, _, _}) -> false.</lang>

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.

<lang forth>1024 constant size create buffer size cells allot here constant end variable head buffer head ! variable tail buffer tail ! variable used 0 used !

empty? used @ 0= ;

full? used @ size = ;

next ( ptr -- ptr )

 cell+  dup end = if drop buffer then ;

put ( n -- )

 full? abort" buffer full"
 \ begin full? while pause repeat
 tail @ !  tail @ next tail !   1 used +! ;

get ( -- n )

 empty? abort" buffer empty"
 \ begin empty? while pause repeat
 head @ @  head @ next head !  -1 used +! ;</lang>

Fortran

Works with: Fortran version 90 and later

See FIFO (usage) for an example of fifo_nodes

<lang fortran>module FIFO

 use fifo_nodes

! fifo_nodes must define the type fifo_node, with the two field ! next and valid, for queue handling, while the field datum depends ! on the usage (see FIFO (usage) for an example) ! type fifo_node ! integer :: datum !  ! the next part is not variable and must be present ! type(fifo_node), pointer :: next ! logical :: valid ! end type fifo_node

 type fifo_head
    type(fifo_node), pointer :: head, tail
 end type fifo_head

contains

 subroutine new_fifo(h)
   type(fifo_head), intent(out) :: h
   nullify(h%head)
   nullify(h%tail)
 end subroutine new_fifo

 subroutine fifo_enqueue(h, n)
   type(fifo_head), intent(inout) :: h
   type(fifo_node), intent(inout), target :: n

   if ( associated(h%tail) ) then
      h%tail%next => n
      h%tail => n
   else
      h%tail => n
      h%head => n
   end if

   nullify(n%next)
 end subroutine fifo_enqueue

 subroutine fifo_dequeue(h, n)
   type(fifo_head), intent(inout) :: h
   type(fifo_node), intent(out), target :: n

   if ( associated(h%head) ) then
      n = h%head
      if ( associated(n%next) ) then
         h%head => n%next
      else
         nullify(h%head)
         nullify(h%tail)
      end if
      n%valid = .true.
   else
      n%valid = .false.
   end if
   nullify(n%next)
 end subroutine fifo_dequeue

 function fifo_isempty(h) result(r)
   logical :: r
   type(fifo_head), intent(in) :: h
   if ( associated(h%head) ) then
      r = .false.
   else
      r = .true.
   end if
 end function fifo_isempty

end module FIFO</lang>

Haskell

The standard way to manage fifo in functional programming is to use a pair of list for the fifo queue, one is the input, the other is the output. When the output is empty just take the input list and reverse it.

<lang haskell>data Fifo a = F [a] [a]

emptyFifo :: Fifo a emptyFifo = F [] []

push :: Fifo a -> a -> Fifo a push (F input output) item = F (item:input) output

pop :: Fifo a -> (Maybe a, Fifo a) pop (F input (item:output)) = (Just item, F input output) pop (F [] [] ) = (Nothing, F [] []) pop (F input [] ) = pop (F [] (reverse input))

isEmpty :: Fifo a -> Bool isEmpty (F [] []) = True isEmpty _ = False</lang>

and a session in the interactive interpreter:

Prelude> :l fifo.hs
[1 of 1] Compiling Main             ( fifo.hs, interpreted )
Ok, modules loaded: Main.
*Main> let q = emptyFifo
*Main> isEmpty q
True
*Main> let q' = push q 1
*Main> isEmpty q'
False
*Main> let q'' = foldl push q' [2..4]
*Main> let (v,q''') = pop q''
*Main> v
Just 1
*Main> let (v',q'''') = pop q'''
*Main> v'
Just 2
*Main> let (v'',q''''') = pop q''''
*Main> v''
Just 3
*Main> let (v''',q'''''') = pop q'''''
*Main> v'''
Just 4
*Main> let (v'''',q''''''') = pop q''''''
*Main> v''''
Nothing

J

<lang J>queue_fifo_=:

pop_fifo_=: verb define

 r=. {. ::] queue
 queue=: }.queue
 r

)

push_fifo_=: verb define

 queue=: queue,y
 y

)

isEmpty_fifo_=: verb define

 0=#queue

)</lang>

See also FIFO (usage)#J

Java

Works with: Java version 1.5+

This task could be done using a LinkedList from java.util, but here is a user-defined version with generics: <lang java>public class Queue<E>{ Node<E> head, tail;

static class Node<E>{ E value; Node<E> next;

public Node(){ this(0, null); }

public Node(E value, Node<E> next){ this.value= value; this.next= next; }

public Node<E> getNext(){ return next; }

public void setNext(Node<E> next){ this.next= next; }

}

public Queue(){ head= tail= null; }

public void enqueue(E value){ //standard queue name for "push" Node<E> newNode= new Node<E>(value, null); if(empty()){ head= newNode; }else{ tail.setNext(newNode); } tail= newNode; }

public E dequeue() throws java.util.NoSuchElementException{//standard queue name for "pop" if(empty()){ throw new java.util.NoSuchElementException("No more elements."); } E retVal= head.value; head= head.getNext(); return retVal; }

public boolean empty(){ return head == null; } }</lang>

JavaScript

<lang javascript>function FIFO() {

   this.data = new Array();

   this.push  = function(element) {this.data.push(element)}
   this.pop   = function() {return this.data.shift()}
   this.empty = function() {return this.data.length == 0}

   this.enqueue = this.push;
   this.dequeue = this.pop;

}</lang>

OCaml

The standard way to manage fifo in functional programming is to use a pair of list for the fifo queue, one is the input, the other is the output. When the output is empty just take the input list and reverse it.

<lang ocaml>module FIFO : sig

 type 'a fifo
 val empty: 'a fifo
 val push: fifo:'a fifo -> item:'a -> 'a fifo
 val pop: fifo:'a fifo -> 'a * 'a fifo
 val is_empty: fifo:'a fifo -> bool

end = struct

 type 'a fifo = 'a list * 'a list
 let empty = [], []
 let push ~fifo:(input,output) ~item = (item::input,output)
 let is_empty ~fifo =
   match fifo with
   | [], [] -> true
   | _ -> false
 let rec pop ~fifo =
   match fifo with
   | input, item :: output -> item, (input,output)
   | [], [] -> failwith "empty fifo"
   | input, [] -> pop ([], List.rev input)

end</lang>

and a session in the top-level:

<lang ocaml># open FIFO;;

1. let q = empty ;;

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

1. is_empty q ;;

- : bool = true

1. let q = push q 1 ;;

val q : int FIFO.fifo = <abstr>

1. is_empty q ;;

- : bool = false

1. let q =

   List.fold_left push q [2;3;4] ;;

val q : int FIFO.fifo = <abstr>

1. let v, q = pop q ;;

val v : int = 1 val q : int FIFO.fifo = <abstr>

1. let v, q = pop q ;;

val v : int = 2 val q : int FIFO.fifo = <abstr>

1. let v, q = pop q ;;

val v : int = 3 val q : int FIFO.fifo = <abstr>

1. let v, q = pop q ;;

val v : int = 4 val q : int FIFO.fifo = <abstr>

1. let v, q = pop q ;;

Exception: Failure "empty fifo".</lang>

The standard ocaml library also provides a FIFO module, but it is imperative, unlike the implementation above which is functional.

Pascal

Works with: Free Pascal version 2.2.0

Works with: GNU Pascal version 20060325, based on gcc-3.4.4

This program should be Standard Pascal compliant (i.e. it doesn't make use of the advanced/non-standard features of FreePascal or GNU Pascal).

<lang pascal>program fifo(input, output);

type

pNode = ^tNode;
tNode = record
         value: integer;
         next:  pNode;
        end;

tFifo = record
         first, last: pNode;
        end;           

procedure initFifo(var fifo: tFifo);

begin
 fifo.first := nil;
 fifo.last := nil
end;

procedure pushFifo(var fifo: tFifo; value: integer);

var
 node: pNode;
begin
 new(node);
 node^.value := value;
 node^.next := nil;
 if fifo.first = nil
  then
   fifo.first := node
  else
   fifo.last^.next := node;
 fifo.last := node
end;

function popFifo(var fifo: tFifo; var value: integer): boolean;

var
 node: pNode;
begin
 if fifo.first = nil
  then
   popFifo := false
  else
   begin
    node := fifo.first;
    fifo.first := fifo.first^.next;
    value := node^.value;
    dispose(node);
    popFifo := true
   end
end;

procedure testFifo;

var
 fifo: tFifo;
procedure testpop(expectEmpty: boolean; expectedValue: integer);
 var
  i: integer;
 begin
  if popFifo(fifo, i)
   then
    if expectEmpty
     then
      writeln('Error! Expected empty, got ', i, '.')
     else
      if i = expectedValue
       then
        writeln('Ok, got ', i, '.')
       else
        writeln('Error! Expected ', expectedValue, ', got ', i, '.')
   else
    if expectEmpty
      then
       writeln('Ok, fifo is empty.')
      else
       writeln('Error! Expected ', expectedValue, ', found fifo empty.')
 end;
begin
 initFifo(fifo);
 pushFifo(fifo, 2);
 pushFifo(fifo, 3);
 pushFifo(fifo, 5);
 testpop(false, 2);
 pushFifo(fifo, 7);
 testpop(false, 3);
 testpop(false, 5);
 pushFifo(fifo, 11);
 testpop(false, 7);
 testpop(false, 11);
 pushFifo(fifo, 13);
 testpop(false, 13);
 testpop(true, 0);
 pushFifo(fifo, 17);
 testpop(false, 17);
 testpop(true, 0)
end;

begin

writeln('Testing fifo implementation ...');
testFifo;
writeln('Testing finished.')

end.</lang>

Perl

Lists are a central part of Perl. To implement a FIFO using OO will to many Perl programmers seem a bit awkward.

<lang perl>use Carp; sub mypush (\@@) {my($list,@things)=@_; push @$list, @things} sub mypop (\@) {my($list)=@_; @$list or croak "Empty"; shift @$list } sub empty (@) {@_}</lang>

Example:

<lang perl>my @fifo=qw(1 2 3 a b c);

mypush @fifo, 44, 55, 66; mypop @fifo for 1 .. 6+3; mypop @fifo; #empty now</lang>

Python

A python list can be used as a simple FIFO by simply using only it's .append() and .pop() methods and only using .pop(0) to consistently pull the head off the list. (The default .pop() pulls off the tail, and using that would treat the list as a stack.

To encapsulate this behavior into a class and provide the task's specific API we can simply use:

<lang python> class FIFO(object):

      def __init__(self, *args):
          self.contents = list()
          if len(args):
              self.contents.extend(*args)
      def __call__(self):
          return self.pop()
      def __len__(self):
          return len(self.contents)
      def pop(self):
          return self.contents.pop(0)
      def push(self, item):
          self.contents.append(item)
      def extend(self,*itemlist):
          self.contents.extend(*itemlist)
      def empty(self):
          if len(self.contents):
              return True
          else:
              return False
      def __iter__(self):
          return self
      def next(self):
          if self.empty():
              raise StopIteration
          return self.pop()

if __name__ == "__main__":

   # Sample usage:
   f = FIFO()
   f.push(3)
   f.push(2)
   f.push(1)
   while not f.empty():
       print f.pop(),
   # >>> 3 2 1
   # Another simple example gives the same results:
   f = FIFO(3,2,1)
   while not f.empty():
       print f(),
   # Another using the default "truth" value of the object
   # (implicitly calls on the length() of the object after
   # checking for a __nonzero__ method
   f = FIFO(3,2,1)
   while f:
       print f(),
   # Yet another, using more Pythonic iteration:
   f = FIFO(3,2,1)
   for i in f:
       print i,</lang>

This example does add to a couple of features which are easy in Python and allow this FIFO class to be used in ways that Python programmers might find more natural. Our __init__ accepts and optional list of initial values, we add __len__ and extend methods which simply wrap the corresponding list methods; we define a __call__ method to show how one can make objects "callable" as functions, and we define __iter__ and next() methods to facilitate using these FIFO objects with Python's prevalent iteration syntax (the for loop). The empty method could be implemented as simply an alias for __len__ --- but we've chosen to have it more strictly conform to the task specification. Implementing the __len__ method allows code using this object to test of emptiness using normal Python idioms for "truth" (any non-empty container is considered to be "true" and any empty container evaluates as "false").

These additional methods could be omitted and some could have been dispatched to the "contents" object by defining a __getattr__ method. (All methods that are note defined could be relayed to the contained list). This would allow us to skip our definitions of extend, __iter__, and __len__, and would allow contents of these objects to be access by indexes and slices as well as supporting all other list methods.

That sort of wrapper looks like:

<lang python>class FIFO: ## NOT a new-style class, must not derive from "object"

  def __init__(self,*args):
      self.contents = list()
      if len(args):
          for i in args:
              self.contents.append(i)
  def __call__(self):
      return self.pop()
  def empty(self):
      if self.contents:
          return True
      else:
          return False
  def pop(self):
          return self.contents.pop(0)
  def __getattr__(self, attr):
      return getattr(self.contents,attr)
  def next(self):
      if not self:
          raise StopIteration
      return self.pop()</lang>

As noted in the contents this must NOT be a new-style class, it must NOT but sub-classed from object nor any of its descendents. (A new-style implementation using __getattribute__ would be possible)

Works with: Python version 2.4+

Python 2.4 and later includes a deque class, supporting thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction. For other options see Python Cookbook.

from collections import deque
fifo = deque()
fifo. appendleft(value) # push
value = fifo.pop()
not fifo # empty
fifo.pop() -> raises IndexError when empty

R

Simple functional implementation

This simple implementation provides three functions that act on a variable in the global environment (user workspace) named l. the push and pop functions display the new status of l, but return NULL silently. <lang R>empty <- function() length(l) == 0 push <- function(x) {

  l <<- c(l, list(x))
  print(l)
  invisible()

} pop <- function() {

  if(empty()) stop("can't pop from an empty list")
  l1 <<- NULL
  print(l)
  invisible()

} l <- list() empty()

1. [1] TRUE

push(3)

1. 1
2. [1] 3

push("abc")

1. 1
2. [1] 3
3. 2
4. [1] "abc"

push(matrix(1:6, nrow=2))

1. 1
2. [1] 3
3. 2
4. [1] "abc"
5. 3
6. [,1] [,2] [,3]
7. [1,] 1 3 5
8. [2,] 2 4 6

empty()

1. [1] FALSE

pop()

1. 1
2. [1] 3
3. 2
4. [1] "abc"

pop()

1. 1
2. [1] 3

pop()

1. list()

pop()

1. Error in pop() : can't pop from an empty list</lang>

The problem with this is that the functions aren't related to the FIFO object (the list l), and they require the list to exist in the global environment. (This second problem is possible to get round by passing l into the function and then returning it, but that is extra work.)

Object oriented implementation

Library: proto

A better solution is to use the object oriented facility in the proto package. (R does have it's own native object oriented code, though the proto package is often nicer to use.)

<lang R>library(proto)

fifo <- proto(expr = {

  l <- list()
  empty <- function(.) length(.$l) == 0
  push <- function(., x) 
  {
     .$l <- c(.$l, list(x))
     print(.$l)
     invisible()
  }
  pop <- function(.) 
  {
     if(.$empty()) stop("can't pop from an empty list")
     .$l1 <- NULL
     print(.$l)
     invisible()
  }

})

1. The following code provides output that is the same as the previous example.

fifo$empty() fifo$push(3) fifo$push("abc") fifo$push(matrix(1:6, nrow=2)) fifo$empty() fifo$pop() fifo$pop() fifo$pop() fifo$pop()</lang>

Ruby

<lang ruby>class FIFO

 def initialize
   @fifo = []
 end
 
 def push(*args)
   @fifo.push(*args)
   self
 end
 alias << push
 alias enqueue push

 # popping an empty FIFO returns nil, or [] if a number is specified
 def pop(*args)
   @fifo.shift(*args)
 end
 alias dequeue pop
 
 def empty?
   @fifo.empty?
 end

 def size
   @fifo.length
 end

end

f = FIFO.new f.empty? # => true f.pop # => nil f.pop(2) # => [] f.push(14) # => #<FIFO:...> f << "foo" << [1,2,3] # => #<FIFO:...> f.enqueue("bar", Hash.new, "baz") # => #<FIFO:...> f.size # => 6 f.pop(3) # => [14, "foo", [1, 2, 3]] f.dequeue # => "bar" f.empty? # => false</lang>

Slate

Toy code based on Slate's Queue standard library (which is optimized for FIFO access): <lang slate>collections define: #Queue &parents: {ExtensibleArray}.

q@(Queue traits) isEmpty [resend]. q@(Queue traits) push: obj [q addLast: obj]. q@(Queue traits) pop [q removeFirst]. q@(Queue traits) pushAll: c [q addAllLast: c]. q@(Queue traits) pop: n [q removeFirst: n].</lang>

Smalltalk

Works with: GNU Smalltalk

An OrderedCollection can be easily used as a FIFO queue.

<lang smalltalk>OrderedCollection extend [

  push: obj [ ^(self add: obj) ]
  pop [
      (self isEmpty) ifTrue: [
         SystemExceptions.NotFound signalOn: self
               reason: 'queue empty'
      ] ifFalse: [
         ^(self removeFirst)
      ]
  ]

]

|f| f := OrderedCollection new. f push: 'example'; push: 'another'; push: 'last'. f pop printNl. f pop printNl. f pop printNl. f isEmpty printNl. f pop. "queue empty error"</lang>

Tcl

Here's a simple implementation using a list: <lang tcl>proc push {stackvar value} {

   upvar 1 $stackvar stack
   lappend stack $value

} proc pop {stackvar} {

   upvar 1 $stackvar stack
   set value [lindex $stack 0]
   set stack [lrange $stack 1 end]
   return $value

} proc size {stackvar} {

   upvar 1 $stackvar stack
   llength $stack

} proc empty {stackvar} {

   upvar 1 $stackvar stack
   expr {[size stack] == 0}

} proc peek {stackvar} {

   upvar 1 $stackvar stack
   lindex $stack 0

}

set Q [list] empty Q ;# ==> 1 (true) push Q foo empty Q ;# ==> 0 (false) push Q bar peek Q ;# ==> foo pop Q ;# ==> foo peek Q ;# ==> bar</lang>

There is a package in

Library: tcllib

called struct::queue that presents an object interface:

<lang tcl>package require struct::queue struct::queue Q Q size ;# ==> 0 Q put a b c d e Q size ;# ==> 5 Q peek ;# ==> a Q get ;# ==> a Q peek ;# ==> b Q pop 4 ;# ==> b c d e Q size ;# ==> 0</lang>

UnixPipes

Uses moreutils <lang bash>init() {echo > fifo} push() {echo $1 >> fifo } pop() {head -1 fifo ; (cat fifo | tail -n +2)|sponge fifo} empty() {cat fifo | wc -l}</lang> Usage: <lang bash>push me; push you; push us; push them |pop;pop;pop;pop me you us them</lang>

V

V doesn't have mutable data. Below is an function interface for a fifo.

<lang v>[fifo_create []]. [fifo_push swap cons]. [fifo_pop [[*rest a] : [*rest] a] view]. [fifo_empty? dup empty?].</lang>

Using it <lang v>|fifo_create 3 fifo_push 4 fifo_push 5 fifo_push ?? =[5 4 3] |fifo_empty? puts =false |fifo_pop put fifo_pop put fifo_pop put =3 4 5 |fifo_empty? puts</lang>

=true