Queue/Usage: Difference between revisions

Content added Content deleted

Inline

Revision as of 06:05, 15 August 2012

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

AppleScript

<lang AppleScript >on push(StackRef, value) set StackRef's contents to {value} & StackRef's contents return StackRef end push

on pop(StackRef) set R to missing value if StackRef's contents ≠ {} then set R to StackRef's contents's item 1 set StackRef's contents to {} & rest of StackRef's contents end if return R end pop

on isStackEmpty(StackRef) if StackRef's contents = {} then return true return false end isStackEmpty

set theStack to {} repeat with i from 1 to 5 push(a reference to theStack, i) log result end repeat repeat until isStackEmpty(theStack) = true pop(a reference to theStack) log result

end repeat</lang>Output (in Script Editor Event Log):

	(*1*)
	(*2, 1*)
	(*3, 2, 1*)
	(*4, 3, 2, 1*)
	(*5, 4, 3, 2, 1*)
	(*5*)
	(*4*)
	(*3*)
	(*2*)
	(*1*)

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>

CoffeeScript

We build a Queue on top of an ordinary JS array, which supports push
and shift. For simple queues, it might make sense to just use arrays
directly, but this code shows how to encapsulate the array behind a restricted
API. For very large queues, you might want a more specialized data
structure to implement the queue, in case arr.shift works in O(N) time, which
is common for array implementations. On my laptop I start noticing delay
after about 100,000 elements, using node.js.

Queue = ->

 arr = []
 enqueue: (elem) ->
   arr.push elem
 dequeue: (elem) ->
   throw Error("queue is empty") if arr.length == 0
   arr.shift elem
 is_empty: (elem) ->
   arr.length == 0

test

do ->

 q = Queue()
 for i in [1..100000]
   q.enqueue i

 console.log q.dequeue() # 1
 while !q.is_empty()
   v = q.dequeue()
 console.log v # 1000
 
 try
   q.dequeue() # throws Error
 catch e
   console.log "#{e}"

</lang> output <lang> > coffee queue.coffee 1 100000 Error: queue is empty </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>

Delphi

Generics were added in Delphi2009.

<lang Delphi>program QueueUsage;

{$APPTYPE CONSOLE}

uses Generics.Collections;

var

 lStringQueue: TQueue<string>;

begin

 lStringQueue := TQueue<string>.Create;
 try
   lStringQueue.Enqueue('First');
   lStringQueue.Enqueue('Second');
   lStringQueue.Enqueue('Third');

   Writeln(lStringQueue.Dequeue);
   Writeln(lStringQueue.Dequeue);
   Writeln(lStringQueue.Dequeue);

   if lStringQueue.Count = 0 then
     Writeln('Queue is empty.');
 finally
   lStringQueue.Free;
 end

end.</lang>

Output:

First
Second
Third
Queue is empty.

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.

Elisa

A generic component for Queues and its usage are described in Queue/Definition

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.

Fantom

Using definition of Queue in: Queue/Definition task.

<lang fantom> class Main {

 public static Void main ()
 {
   q := Queue()
   q.push (1)
   q.push ("a")
   echo ("Is empty? " + q.isEmpty)
   echo ("Element: " + q.pop)
   echo ("Element: " + q.pop)
   echo ("Is empty? " + q.isEmpty)
   try { q.pop } catch (Err e) { echo (e.msg) }
 }

} </lang>

Output:

Is empty? false
Element: 1
Element: a
Is empty? true
queue is empty

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>

Go

With Queue/Definition code

Solution using package from the Queue/Definition task: <lang go>package main

import (

   "fmt"
   "queue"

)

func main() {

   q := new(queue.Queue)
   fmt.Println("empty?", q.Empty())

   x := "black"
   fmt.Println("push", x)
   q.Push(x)

   fmt.Println("empty?", q.Empty())
   r, ok := q.Pop()
   if ok {
       fmt.Println(r, "popped")
   } else {
       fmt.Println("pop failed")
   }

   var n int
   for _, x := range []string{"blue", "red", "green"} {
       fmt.Println("pushing", x)
       q.Push(x)
       n++
   }

   for i := 0; i < n; i++ {
       r, ok := q.Pop()
       if ok {
           fmt.Println(r, "popped")
       } else {
           fmt.Println("pop failed")
       }
   }

}</lang> Output:

empty? true
push black
empty? false
black popped
pushing blue
pushing red
pushing green
blue popped
red popped
green popped

With channels

Go buffered channels are FIFO, and better, are concurrency-safe (if you have an application for that.) Code below is same as code above only with Go channels rather than the home made queue implementation. Note that you don't have to start concurrent goroutines to use channels, they are useful all on their own. Other differences worth noting: Buffered channels are not dynamically resizable. This is a good thing, as queues that can grow without limit allow ugly bugs that consume memory and grind to a halt. Also blocking operations (as seen here with push) are probably a bad idea with a single goroutine. Much safer to use non-blocking operations that handle success and failure (the way pop is done here.) <lang go>package main

import "fmt"

func main() {

   q := make(chan string, 3)
   fmt.Println("empty?", len(q) == 0)

   x := "black"
   fmt.Println("push", x)
   q <- x

   fmt.Println("empty?", len(q) == 0)
   select {
   case r := <-q:
       fmt.Println(r, "popped")
   default:
       fmt.Println("pop failed")
   }

   var n int
   for _, x := range []string{"blue", "red", "green"} {
       fmt.Println("pushing", x)
       q <- x
       n++
   }

   for i := 0; i < n; i++ {
       select {
       case r := <-q:
           fmt.Println(r, "popped")
       default:
           fmt.Println("pop failed")
       }
   }

}</lang>

With linked lists

<lang go>package main

import (

   "fmt"
   "container/list"

)

func main() {

   q := list.New()
   fmt.Println("empty?", q.Len() == 0)

   x := "black"
   fmt.Println("push", x)
   q.PushBack(x)

   fmt.Println("empty?", q.Len() == 0)
   if e := q.Front(); e != nil {
       r := q.Remove(e)
       fmt.Println(r, "popped")
   } else {
       fmt.Println("pop failed")
   }

   var n int
   for _, x := range []string{"blue", "red", "green"} {
       fmt.Println("pushing", x)
       q.PushBack(x)
       n++
   }

   for i := 0; i < n; i++ {
       if e := q.Front(); e != nil {
           r := q.Remove(e)
           fmt.Println(r, "popped")
       } else {
           fmt.Println("pop failed")
       }
   }

}</lang>

Groovy

Solution: <lang groovy>def q = new LinkedList()</lang>

Test: <lang groovy>assert q.empty println q // "push" adds to end of "queue" list q.push('Stuart') println q assert !q.empty // "add" adds to end of "queue" list q.add('Pete') println q assert !q.empty // left shift operator ("<<") adds to end of "queue" list q << 'John' println q assert !q.empty // add assignment ("+=") adds the list elements // to the end of the "queue" list in list order q += ['Paul', 'George'] println q assert !q.empty // "poll" removes and returns the first element in the // "queue" list ("pop" exists for Groovy lists, but it // removes and returns the LAST element for "Stack" // semantics). "poll" only exists in objects that // implement java.util.Queue, like java.util.LinkedList assert q.poll() == 'Stuart' println q assert !q.empty assert q.poll() == 'Pete' println q assert !q.empty q << 'Ringo' println q assert !q.empty assert q.poll() == 'John' println q assert !q.empty assert q.poll() == 'Paul' println q assert !q.empty assert q.poll() == 'George' println q assert !q.empty assert q.poll() == 'Ringo' println q assert q.empty assert q.poll() == null</lang>

Output:

[]
[Stuart]
[Stuart, Pete]
[Stuart, Pete, John]
[Stuart, Pete, John, Paul, George]
[Pete, John, Paul, George]
[John, Paul, George]
[John, Paul, George, Ringo]
[Paul, George, Ringo]
[George, Ringo]
[Ringo]
[]

Haskell

Running the code from Queue/Definition#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>

Icon and Unicon

Icon and Unicon provide built-in queue and stack functions. <lang Icon>procedure main(arglist) queue := [] write("Usage:\nqueue x x x - x - - - - -\n\t- pops elements\n\teverything else pushes") write("Queue is:") every x := !arglist do {

  case x of {
     "-"     : pop(queue)  | write("pop(empty) failed.")    # pop if the next arglist[i] is a -
     default : put(queue,x)                                 # push arglist[i]
     }
  if empty(queue) then writes("empty")
  else every writes(!queue," ")
  write()
  }

end

procedure empty(X) #: fail if X is not empty if *X = 0 then return end</lang>

Sample output:

queue - 1 3 4 5 6 - - - - - - - -
Usage:
queue x x x - x - - - - -
        - pops elements
        everything else pushes
Queue is:
pop(empty) failed.
empty
1 
1 3 
1 3 4 
1 3 4 5 
1 3 4 5 6 
3 4 5 6 
4 5 6 
5 6 
6 
empty
pop(empty) failed.
empty
pop(empty) failed.
empty
pop(empty) failed.
empty

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>

Lua

Uses the queue-definition given at Queue/Definition#Lua <lang lua>q = Queue.new() Queue.push( q, 5 ) Queue.push( q, "abc" )

while not Queue.empty( q ) do

   print( Queue.pop( q ) )

end</lang>

Mathematica

<lang Mathematica>Empty[a_] := If[Length[a] == 0, True, False] SetAttributes[Push, HoldAll]; Push[a_, elem_] := AppendTo[a, elem] SetAttributes[Pop, HoldAllComplete]; Pop[a_] := If[EmptyQ[a], False, b = First[a]; Set[a, Most[a]]; b]

Queue = {} -> {} Empty[Queue] -> True Push[Queue, "1"] -> {"1"} EmptyQ[Queue] ->False Pop[Queue] ->1 Pop[Queue] ->False</lang>

NetRexx

This example demonstrates the push, pop and empty operations from an implementation of a queue as specified for the task.

The demonstration employs an in-line deployment of a queue object having as it's underlying implementation a java.util.Deque interface instanciated as a java.util.ArrayDeque. Typically this queue implementation would reside outside of the demonstration program and be imported at run-time rather than within the body of this source. <lang NetRexx>/* NetRexx */ options replace format comments java crossref savelog symbols nobinary

-- Queue Usage Demonstration Program ------------------------------------------- method main(args = String[]) public constant

 kew = RCQueueImpl()
 do
   say kew.pop()
 catch ex = IndexOutOfBoundsException
   say ex.getMessage
   say
 end

 melancholyDane = 
 melancholyDane[0] = 4
 melancholyDane[1] = 'To be'
 melancholyDane[2] = 'or'
 melancholyDane[3] = 'not to be?'
 melancholyDane[4] = 'That is the question.'

 loop p_ = melancholyDane[0] to 1 by -1
   kew.push(melancholyDane[p_])
   end p_

 loop while \kew.empty
   popped = kew.pop
   say popped '\-'
   end
 say; say

 -- demonstrate stowing something other than a text string in the queue
 kew.push(melancholyDane)
 md = kew.pop
 loop l_ = 1 to md[0]
   say md[l_] '\-'
   end l_
 say

 return

-- Queue implementation -------------------------------------------------------- class RCQueueImpl

 properties private
   qqq = Deque

method RCQueueImpl() public

 qqq = ArrayDeque()
 return

method push(stuff) public

 qqq.push(stuff)
 return

method pop() public returns Rexx signals IndexOutOfBoundsException

 if qqq.isEmpty then signal IndexOutOfBoundsException('The queue is empty')
 return Rexx qqq.pop()

method empty() public binary returns boolean

 return qqq.isEmpty

method isTrue public constant binary returns boolean

 return 1 == 1

method isFalse public constant binary returns boolean

 return \isTrue

</lang>

Output

The queue is empty

To be or not to be? That is the question. 

To be or not to be? That is the question.

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>

ooRexx

ooRexx includes a built-in queue class. <lang ooRexx> q = .queue~new -- create an instance q~queue(3) -- adds to the end, but this is at the front q~push(1) -- push on the front q~queue(2) -- add to the end say q~pull q~pull q~pull q~isempty -- should display all and be empty <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>

Perl 6

Perl 6 maintains the same list operators of Perl, for this task, the operations are: <lang>push (aka enqueue) -- @list.push pop (aka dequeue) -- @list.shift empty -- !@list.elems</lang> but there's also @list.pop which removes a item from the end, and @list.unshift which add a item on the start of the list.
Example: <lang perl6>my @queue = < a >;

@queue.push('b', 'c'); # [ a, b, c ]

say @queue.shift; # a say @queue.pop; # c

say @queue.perl; # [ b ] say @queue.elems; # 1

@queue.unshift('A'); # [ A, b ] @queue.push('C'); # [ A, b, C ]</lang>

PHP

Works with: PHP version 5.3+

<lang php><?php $queue = new SplQueue; echo $queue->isEmpty() ? 'true' : 'false', "\n"; // empty test - returns true // $queue->dequeue(); // would raise RuntimeException $queue->enqueue(1); $queue->enqueue(2); $queue->enqueue(3); echo $queue->dequeue(), "\n"; // returns 1 echo $queue->isEmpty() ? 'true' : 'false', "\n"; // returns false ?></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>

PostScript

Library: initlib

[1 2 3 4 5] 6 exch tadd
= [1 2 3 4 5 6]
uncons
= 1 [2 3 4 5 6]
[] empty?
=true

</lang>

Prolog

Works with SWI-Prolog.

<lang Prolog>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% definitions of queue empty(U-V) :- unify_with_occurs_check(U, V).

push(Queue, Value, NewQueue) :- append_dl(Queue, [Value|X]-X, NewQueue).

pop([X|V]-U, X, V-U) :- \+empty([X|V]-U).

append_dl(X-Y, Y-Z, X-Z).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% use of queue queue :- % create an empty queue empty(Q), format('Create queue ~w~n~n', [Q]),

% add numbers 1 and 2 write('Add numbers 1 and 2 : '), push(Q, 1, Q1), push(Q1, 2, Q2),

% display queue format('~w~n~n', [Q2]),

% pop element pop(Q2, V, Q3),

% display results format('Pop : Value ~w Queue : ~w~n~n', [V, Q3]),

% test the queue write('Test of the queue : '), ( empty(Q3) -> writeln('Queue empy'); writeln('Queue not empty')), nl,

% pop the elements write('Pop the queue : '), pop(Q3, V1, Q4), format('Value ~w Queue : ~w~n~n', [V1, Q4]),

write('Pop the queue : '), pop(Q4, _V, _Q5). </lang> Output :

?- queue.
Create queue _G132-_G132

Add numbers 1 and 2 : [1,2|_G148]-_G148

Pop : Value 1 Queue : [2|_G148]-_G148

Test of the queue : Queue not empty

Pop the queue : Value 2 Queue : _G148-_G148

Pop the queue : 
false.

PureBasic

<lang PureBasic>NewList MyStack()

Procedure Push(n)

 Shared MyStack()
 LastElement(MyStack())
 AddElement(MyStack())
 MyStack()=n

EndProcedure

Procedure Pop()

 Shared MyStack()
 Protected n
 If FirstElement(MyStack())  ; e.g. Stack not empty
   n=MyStack()
   DeleteElement(MyStack(),1)
 EndIf
 ProcedureReturn n

EndProcedure

Procedure Empty()

 Shared MyStack()
 If  ListSize(MyStack())=0
   ProcedureReturn #True
 EndIf
 ProcedureReturn #False

EndProcedure

---- Example of implementation ----

Push(3) Push(1) Push(4) Push(1) Push(5) While Not Empty()

 Debug Pop()

Wend </lang>

Outputs

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

REXX

The REXX language was developed under IBM VM/CMS operating system, and CMS had a stack mechanism built-into the
operating system, so REXX utilized that resource.
The queue instruction adds an entry to the bottom of the stack (FIFO),
the push instruction adds an entry to the top of the stack (LIFO).
The queued function returns the number of entries in the stack.
The pull or parse pull removes an entry from the top of the stack.
There are other instructions to manipulate the stack by "creating" mulitiple (named) stacks.
The entries in the stack may be anything, including "nulls". <lang rexx>/*REXX program demonstrates three queue operations: push, pop, queued. */ say '══════════════════════════════════Pushing five values to the stack.'

       do j=1 for 4                   /*loop to PUSH four values.      */
       call push j*10                 /*PUSH  (aka enqueue to stack).  */
       say 'pushed value:' j*10       /*echo the pushed value.         */
       if j\==3 then iterate          /*also, insert a "null" entry.   */
       call push                      /*PUSH  (aka enqueue to stack).  */
       say 'pushed a "null" value.'   /*echo what was pushed.          */
       end   /*j*/

say '══════════════════════════════════Popping all values from the stack.'

       do m=1 while \empty()          /*EMPTY (returns TRUE if empty). */
       call pop                       /*POP   (aka dequeue from stack).*/
       say m': popped value=' result  /*echo the popped value.         */
       end   /*m*/

say '══════════════════════════════════The stack is now empty.' exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────subroutines/functions/operators. */ push: queue arg(1); return /*REXX QUEUE is FIFO. */ pop: procedure; pull x; return x /*REXX PULL removes a stack item*/ empty: return queued()==0 /*returns the status of the stack*/</lang> output

══════════════════════════════════Pushing five values to the stack.
pushed value: 10
pushed value: 20
pushed value: 30
pushed a "null" value.
pushed value: 40
══════════════════════════════════Popping all values from the stack.
1: popped value= 10
2: popped value= 20
3: popped value= 30
4: popped value=
5: popped value= 40
══════════════════════════════════The stack is now empty.

Ruby

Sample usage at FIFO#Ruby

Scala

<lang scala>val q=scala.collection.mutable.Queue[Int]() println("isEmpty = " + q.isEmpty) try{q dequeue} catch{case _:java.util.NoSuchElementException => println("dequeue(empty) failed.")} q enqueue 1 q enqueue 2 q enqueue 3 println("queue = " + q) println("front = " + q.front) println("dequeue = " + q.dequeue) println("dequeue = " + q.dequeue) println("isEmpty = " + q.isEmpty)</lang> Output:

isEmpty = true
dequeue(empty) failed.
queue   = Queue(1, 2, 3)
front   = 1
dequeue = 1
dequeue = 2
isEmpty = false

Standard ML

Works with: SML/NJ

Functional interface

<lang sml>- open Fifo; opening Fifo

 datatype 'a fifo = ...
 exception Dequeue
 val empty : 'a fifo
 val isEmpty : 'a fifo -> bool
 val enqueue : 'a fifo * 'a -> 'a fifo
 val dequeue : 'a fifo -> 'a fifo * 'a
 val next : 'a fifo -> ('a * 'a fifo) option
 val delete : 'a fifo * ('a -> bool) -> 'a fifo
 val head : 'a fifo -> 'a
 val peek : 'a fifo -> 'a option
 val length : 'a fifo -> int
 val contents : 'a fifo -> 'a list
 val app : ('a -> unit) -> 'a fifo -> unit
 val map : ('a -> 'b) -> 'a fifo -> 'b fifo
 val foldl : ('a * 'b -> 'b) -> 'b -> 'a fifo -> 'b
 val foldr : ('a * 'b -> 'b) -> 'b -> 'a fifo -> 'b

- val q = empty; val q = Q {front=[],rear=[]} : 'a fifo - isEmpty q; val it = true : bool - val q' = enqueue (q, 1); val q' = Q {front=[],rear=[1]} : int fifo - isEmpty q'; val it = false : bool - val q = List.foldl (fn (x, q) => enqueue (q, x)) q' [2, 3, 4]; val q = Q {front=[],rear=[4,3,2,1]} : int fifo - peek q; val it = SOME 1 : int option - length q; val it = 4 : int - contents q; val it = [1,2,3,4] : int list - val (q', v) = dequeue q; val q = Q {front=[2,3,4],rear=[]} : int fifo val v = 1 : int - val (q', v') = dequeue q; val q' = Q {front=[3,4],rear=[]} : int fifo val v' = 2 : int - val (q, v) = dequeue q'; val q = Q {front=[4],rear=[]} : int fifo val v = 3 : int - val (q', v) = dequeue q; val q' = Q {front=[],rear=[]} : int fifo val v = 4 : int - isEmpty q'; val it = true : bool</lang>

Works with: SML/NJ

Imperative interface

<lang sml>- open Queue; opening Queue

 type 'a queue
 exception Dequeue
 val mkQueue : unit -> 'a queue
 val clear : 'a queue -> unit
 val isEmpty : 'a queue -> bool
 val enqueue : 'a queue * 'a -> unit
 val dequeue : 'a queue -> 'a
 val next : 'a queue -> 'a option
 val delete : 'a queue * ('a -> bool) -> unit
 val head : 'a queue -> 'a
 val peek : 'a queue -> 'a option
 val length : 'a queue -> int
 val contents : 'a queue -> 'a list
 val app : ('a -> unit) -> 'a queue -> unit
 val map : ('a -> 'b) -> 'a queue -> 'b queue
 val foldl : ('a * 'b -> 'b) -> 'b -> 'a queue -> 'b
 val foldr : ('a * 'b -> 'b) -> 'b -> 'a queue -> 'b

- val q : int queue = mkQueue (); val q = - : int queue - isEmpty q; val it = true : bool - enqueue (q, 1); val it = () : unit - isEmpty q; val it = false : bool - enqueue (q, 2); val it = () : unit - enqueue (q, 3); val it = () : unit - peek q; val it = SOME 1 : int option - length q; val it = 3 : int - contents q; val it = [1,2,3] : int list - dequeue q; val it = 1 : int - dequeue q; val it = 2 : int - peek q; val it = SOME 3 : int option - length q; val it = 1 : int - enqueue (q, 4); val it = () : unit - dequeue q; val it = 3 : int - peek q; val it = SOME 4 : int option - dequeue q; val it = 4 : int - isEmpty q; val it = true : bool</lang>

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>