Queue/Usage

Create a queue data structure and demonstrate its operations. (For implementations of queues, see the FIFO task.)

Operations:

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

Ada

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

procedure Queue_Test is

  package Int_FIFO is new FIFO (Integer);
  use Int_FIFO;
  Queue : FIFO_Type;
  Value : Integer;

begin

  Push (Queue, 1);
  Push (Queue, 2);   
  Push (Queue, 3);
  Pop (Queue, Value);
  Pop (Queue, Value);
  Push (Queue, 4);
  Pop (Queue, Value);
  Pop (Queue, Value);
  Push (Queue, 5);
  Pop (Queue, Value);
  Put_Line ("Is_Empty " & Boolean'Image (Is_Empty (Queue)));

end Queue_Test;</lang> Sample output:

Is_Empty TRUE

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

Include fifo.ahk</lang>

Note that the container used to store the queue elements can be specified explicitly; to use a linked linst instead of a deque (the latter is the default), just replace the definition of q to <lang cpp> std::queue<int, std::list<int> ></lang>

(and add #include <list>, of course). Also note that the containers can be used directly; in that case push and pop have to be replaced by push_back and pop_front.

C#

In C# we can use the Queue<T> class in the .NET 2.0 framework. <lang csharp>using System; using System.Collections.Generic;

namespace RosettaCode {

   class Program
   {
       static void Main()
       {
           // Create a queue and "push" items into it
           Queue<int> queue  = new Queue<int>();
           queue.Enqueue(1);
           queue.Enqueue(3);
           queue.Enqueue(5);

           // "Pop" items from the queue in FIFO order
           Console.WriteLine(queue.Dequeue()); // 1
           Console.WriteLine(queue.Dequeue()); // 3
           Console.WriteLine(queue.Dequeue()); // 5

           // To tell if the queue is empty, we check the count
           bool empty = queue.Count == 0;
           Console.WriteLine(empty); // "True"

           // If we try to pop from an empty queue, an exception
           // is thrown.
           try
           {
               queue.Dequeue();
           }
           catch (InvalidOperationException exception)
           {
               Console.WriteLine(exception.Message); // "Queue empty."
           }
       }
   }

}</lang>

Clojure

Using the implementation from FIFO: <lang lisp>(def q (make-queue))

(enqueue q 1) (enqueue q 2) (enqueue q 3)

(dequeue q) ; 1 (dequeue q) ; 2 (dequeue q) ; 3

(queue-empty? q) ; true</lang> Or use a java implementation: <lang lisp>(def q (java.util.LinkedList.))

(.add q 1) (.add q 2) (.add q 3)

(.remove q) ; 1 (.remove q) ; 2 (.remove q) ; 3

(.isEmpty q) ; true</lang>

Common Lisp

Using the implementation from FIFO.

<lang lisp>(let ((queue (make-queue)))

 (enqueue 38 queue)
 (assert (not (queue-empty-p queue)))
 (enqueue 23 queue)
 (assert (eql 38 (dequeue queue)))
 (assert (eql 23 (dequeue queue)))
 (assert (queue-empty-p queue)))</lang>

E

Using the implementation from FIFO.

<lang e>def [reader, writer] := makeQueue() require(escape empty { reader.dequeue(empty); false } catch _ { true }) writer.enqueue(1) writer.enqueue(2) require(reader.dequeue(throw) == 1) writer.enqueue(3) require(reader.dequeue(throw) == 2) require(reader.dequeue(throw) == 3) require(escape empty { reader.dequeue(empty); false } catch _ { true })</lang>

E also has queues in the standard library such as <import:org.erights.e.examples.concurrency.makeQueue>, but they are designed for concurrency purposes and do not report emptiness but rather return a promise for the next element.

Erlang

All functions, from the shell: <lang Erlang>1> Q = fifo:new(). {fifo,[],[]} 2> fifo:empty(Q). true 3> Q2 = fifo:push(Q,1). {fifo,[1],[]} 4> Q3 = fifo:push(Q2,2). {fifo,[2,1],[]} 5> fifo:empty(Q3). false 6> fifo:pop(Q3). {1,{fifo,[],[2]}} 7> {Popped, Q} = fifo:pop(Q2). {1,{fifo,[],[]}} 8> fifo:pop(fifo:new()).

- exception error: 'empty fifo'

    in function  fifo:pop/1</lang>

Crashing is the normal expected behavior in Erlang: let it crash, a supervisor will take responsibility of restarting processes, or the caller will take care of it. Only program for the successful cases.

Fortran

Works with: Fortran version 90 and later

<lang fortran>module fifo_nodes

 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

end module fifo_nodes

program FIFOTest

 use fifo
 implicit none

 type(fifo_head) :: thehead
 type(fifo_node), dimension(5) :: ex, xe
 integer :: i
 
 call new_fifo(thehead)

 do i = 1, 5
    ex(i)%datum = i
    call fifo_enqueue(thehead, ex(i))
 end do

 i = 1
 do
    call fifo_dequeue(thehead, xe(i))
    print *, xe(i)%datum
    i = i + 1
    if ( fifo_isempty(thehead) ) exit
 end do

end program FIFOTest</lang>

Haskell

Running the code from http://rosettacode.org/wiki/FIFO#Haskell through GHC's interpreter.

<lang Haskell> 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 </lang>

J

Using object-oriented FIFO queue implementation from FIFO

This is an interactive J session:

<lang j> queue=: conew 'fifo'

  isEmpty__queue

1

  push__queue 9

9

  push__queue 8

8

  push__queue 7

7

  isEmpty__queue

0

  pop__queue

9

  pop__queue

8

  pop__queue

7

  isEmpty__queue

1</lang>

Using function-level FIFO queue implementation from FIFO

This is an interactive J session: <lang j> is_empty make_empty _ 1

  first_named_state =: push 9 onto make_empty _
  newer_state =: push 8 onto first_named_state
  this_state =: push 7 onto newer_state
  is_empty this_state

0

  tell_queue this_state

9 8 7

  tell_atom pop this_state

9

  tell_atom pop pop this_state

8

  tell_atom pop pop pop this_state

7

  is_empty pop pop pop this_state

1</lang>

Java

Works with: Java version 1.5+

LinkedList can always be used as a queue or stack, but not in conjunction with the Stack object provided by Java. To use a LinkedList as a stack, use the push and pop methods. A LinkedList can also be used as a double-ended queue (deque); LinkedList has implemented the Deque interface since Java 1.6+. <lang java>import java.util.LinkedList; import java.util.Queue; ... Queue<Integer> queue = new LinkedList<Integer>(); System.out.println(queue.isEmpty()); // empty test - true // queue.remove(); // would throw NoSuchElementException queue.add(1); queue.add(2); queue.add(3); System.out.println(queue); // [1, 2, 3] System.out.println(queue.remove()); // 1 System.out.println(queue); // [2, 3] System.out.println(queue.isEmpty()); // false</lang>

You can also use "offer" and "poll" methods instead of "add" and "remove", respectively. They indicate errors with the return value instead of throwing an exception.

Works with: Java version 1.4

<lang java>import java.util.LinkedList; ... LinkedList queue = new LinkedList(); System.out.println(queue.isEmpty()); // empty test - true queue.add(new Integer(1)); queue.add(new Integer(2)); queue.add(new Integer(3)); System.out.println(queue); // [1, 2, 3] System.out.println(queue.removeFirst()); // 1 System.out.println(queue); // [2, 3] System.out.println(queue.isEmpty()); // false</lang>

JavaScript

JavaScript arrays can be used as FIFOs. <lang javascript>var f = new Array(); print(f.length); f.push(1,2); // can take multiple arguments f.push(3); f.shift(); f.shift(); print(f.length); print(f.shift()) print(f.length == 0); print(f.shift());</lang>

outputs:

0
1
3
true
undefined

Logo

Works with: UCB Logo

UCB Logo comes with a protocol for treating lists as queues.

<lang logo>make "fifo [] print empty? :fifo ; true queue "fifo 1 queue "fifo 2 queue "fifo 3 show :fifo ; [1 2 3] print dequeue "fifo ; 1 show :fifo ; [2 3] print empty? :fifo ; false</lang>

OCaml

<lang ocaml># let q = Queue.create ();; val q : '_a Queue.t = <abstr>

Queue.is_empty q;;

- : bool = true

Queue.add 1 q;;

- : unit = ()

Queue.is_empty q;;

- : bool = false

Queue.add 2 q;;

- : unit = ()

Queue.add 3 q;;

- : unit = ()

Queue.peek q;;

- : int = 1

Queue.length q;;

- : int = 3

Queue.iter (Printf.printf "%d, ") q; print_newline ();;

1, 2, 3, - : unit = ()

Queue.take q;;

- : int = 1

Queue.take q;;

- : int = 2

Queue.peek q;;

- : int = 3

Queue.length q;;

- : int = 1

Queue.add 4 q;;

- : unit = ()

Queue.take q;;

- : int = 3

Queue.peek q;;

- : int = 4

Queue.take q;;

- : int = 4

Queue.is_empty q;;

- : bool = true</lang>

Oz

<lang oz>declare

 [Queue] = {Link ['x-oz://system/adt/Queue.ozf']}
 MyQueue = {Queue.new}

in

 {MyQueue.isEmpty} = true
 {MyQueue.put foo}
 {MyQueue.put bar}
 {MyQueue.put baz}
 {MyQueue.isEmpty} = false
 {Show {MyQueue.get}}  %% foo
 {Show {MyQueue.get}}  %% bar
 {Show {MyQueue.get}}  %% baz</lang>

Perl

Perl has built-in support to these operations: <lang perl>@queue = (); # we will simulate a queue in a array

push @queue, (1..5); # enqueue numbers from 1 to 5

print shift @queue,"\n"; # dequeue

print "array is empty\n" unless @queue; # is empty ?

print $n while($n = shift @queue); # dequeue all print "\n"; print "array is empty\n" unless @queue; # is empty ?</lang> Output: <lang>1 2345 array is empty</lang>

PicoLisp

Using the implementation from FIFO: <lang PicoLisp>(println (fifo 'Queue)) # Retrieve the number '1' (println (fifo 'Queue)) # Retrieve an internal symbol 'abc' (println (fifo 'Queue)) # Retrieve a transient symbol "abc" (println (fifo 'Queue)) # and a list (abc) (println (fifo 'Queue)) # Queue is empty -> NIL</lang> Output:

1
abc
"abc"
(a b c)
NIL

PL/I

<lang PL/I> test: proc options (main);

  /* To implement a queue. */
  define structure
     1 node,
        2 value fixed,
        2 link handle(node);
  declare (head, tail, t) handle (node);
  declare null builtin;
  declare i fixed binary;

  head, tail = bind(:node, null:);

  do i = 1 to 10; /* Add ten items to the tail of the queue. */
     if head = bind(:node, null:) then
        do;
           head,tail = new(:node:);
           get list (head => value);
           put skip list (head => value);
           head => link = bind(:node, null:); /* A NULL link */
        end;
     else
        do;
           t = new(:node:);
           tail => link = t; /* Point the tail to the new node. */
           tail = t;
           tail => link = bind(:node, null:); /* Set the tail link to NULL */
           get list (tail => value) copy;
           put skip list (tail => value);
        end;
  end;

  /* Pop all the items in the queue. */
  put skip list ('The queue has:');
  do while (head ^= bind(:node, null:));
     put skip list (head => value);
     head = head => link;
  end;

end test; </lang> The output: <lang>

The queue has:

</lang>

Python

<lang python>import Queue my_queue = Queue.Queue() my_queue.put("foo") my_queue.put("bar") my_queue.put("baz") print my_queue.get() # foo print my_queue.get() # bar print my_queue.get() # baz</lang>

REBOL

See FIFO#REBOL for implementation. Example repeated here for completeness.

<lang REBOL>; Create and populate a FIFO:

q: make fifo [] q/push 'a q/push 2 q/push USD$12.34 ; Did I mention that REBOL has 'money!' datatype? q/push [Athos Porthos Aramis] ; List elements pushed on one by one. q/push Huey Dewey Lewey ; This list is preserved as a list.

Dump it out, with narrative

print rejoin ["Queue is " either q/empty [""]["not "] "empty."] while [not q/empty][print [" " q/pop]] print rejoin ["Queue is " either q/empty [""]["not "] "empty."] print ["Trying to pop an empty queue yields:" q/pop]</lang>

Output:

Queue is not empty.
   a
   2
   USD$12.34
   Athos
   Porthos
   Aramis
   Huey Dewey Lewey
Queue is empty.
Trying to pop an empty queue yields: none

Ruby

Sample usage at FIFO#Ruby

Tcl

See FIFO for operation implementations: <lang tcl>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>