Queue/Usage
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.
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
- See also
- Array
- Associative array: Creation, Iteration
- Collections
- Compound data type
- Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
- Linked list
- Queue: Definition, Usage
- Set
- Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
- Stack
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*)
AutoHotkey
<lang autohotkey>push("qu", 2), push("qu", 44), push("qu", "xyz") ; TEST
MsgBox % "Len = " len("qu") ; Number of entries While !empty("qu") ; Repeat until queue is not empty
MsgBox % pop("qu") ; Print popped values (2, 44, xyz)
MsgBox Error = %ErrorLevel% ; ErrorLevel = 0: OK MsgBox % pop("qu") ; Empty MsgBox Error = %ErrorLevel% ; ErrorLevel = -1: popped too much MsgBox % "Len = " len("qu") ; Number of entries
push(queue,_) { ; push _ onto queue named "queue" (!=_), _ string not containing |
Global %queue% .= %queue% = "" ? _ : "|" _
}
pop(queue) { ; pop value from queue named "queue" (!=_,_1,_2)
Global RegExMatch(%queue%, "([^\|]*)\|?(.*)", _) Return _1, ErrorLevel := -(%queue%=""), %queue% := _2
}
empty(queue) { ; check if queue named "queue" is empty
Global Return %queue% = ""
}
len(queue) { ; number of entries in "queue"
Global StringReplace %queue%, %queue%, |, |, UseErrorLevel Return %queue% = "" ? 0 : ErrorLevel+1
}</lang>
BBC BASIC
<lang bbcbasic> FIFOSIZE = 1000
FOR n = 3 TO 5 PRINT "Push ";n : PROCenqueue(n) NEXT PRINT "Pop " ; FNdequeue PRINT "Push 6" : PROCenqueue(6) REPEAT PRINT "Pop " ; FNdequeue UNTIL FNisempty PRINT "Pop " ; FNdequeue END DEF PROCenqueue(n) : LOCAL f% DEF FNdequeue : LOCAL f% : f% = 1 DEF FNisempty : LOCAL f% : f% = 2 PRIVATE fifo(), rptr%, wptr% DIM fifo(FIFOSIZE-1) CASE f% OF WHEN 0: wptr% = (wptr% + 1) MOD FIFOSIZE IF rptr% = wptr% ERROR 100, "Error: queue overflowed" fifo(wptr%) = n WHEN 1: IF rptr% = wptr% ERROR 101, "Error: queue empty" rptr% = (rptr% + 1) MOD FIFOSIZE = fifo(rptr%) WHEN 2: = (rptr% = wptr%) ENDCASE ENDPROC</lang>
Output:
Push 3 Push 4 Push 5 Pop 3 Push 6 Pop 4 Pop 5 Pop 6 Pop Error: queue empty
C
See FIFO for the needed code. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <stdbool.h>
- include <sys/queue.h>
/* #include "fifolist.h" */
int main() {
int i; FIFOList head;
TAILQ_INIT(&head);
/* insert 20 integer values */ for(i=0; i < 20; i++) { m_enqueue(i, &head); }
/* dequeue and print */ while( m_dequeue(&i, &head) ) printf("%d\n", i);
fprintf(stderr, "FIFO list %s\n",
( m_dequeue(&i, &head) ) ? "had still an element" : "is void!");
exit(0);
}</lang>
C++
Note that with C++'s standard queue, accessing the first element of the queue and removing it are two separate operations, front() and pop(). <lang cpp>#include <queue>
- include <cassert> // for run time assertions
int main() {
std::queue<int> q; assert( q.empty() ); // initially the queue is empty
q.push(1); // add an element assert( !q.empty() ); // now the queue isn't empty any more assert( q.front() == 1 ); // the first element is, of course, 1
q.push(2); // add another element assert( !q.empty() ); // it's of course not empty again assert( q.front() == 1 ); // the first element didn't change
q.push(3); // add yet an other element assert( !q.empty() ); // the queue is still not empty assert( q.front() == 1 ); // and the first element is still 1
q.pop(); // remove the first element assert( !q.empty() ); // the queue is not yet empty assert( q.front() == 2); // the first element is now 2 (the 1 is gone)
q.pop(); assert( !q.empty() ); assert( q.front() == 3);
q.push(4); assert( !q.empty() ); assert( q.front() == 3);
q.pop(); assert( !q.empty() ); assert( q.front() == 4);
q.pop(); assert( q.empty() );
q.push(5); assert( !q.empty() ); assert( q.front() == 5);
q.pop(); assert( q.empty() );
}</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>
CoffeeScript
<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>
Component Pascal
BlackBox Component Builder <lang oberon2> MODULE UseQueue; IMPORT StdLog,Queue,Boxes;
PROCEDURE Do*;
VAR
q: Queue.Queue;
o: Boxes.Object;
BEGIN
q := Queue.NewQueue(6);
q.Push(Boxes.NewInteger(1));
q.Push(Boxes.NewInteger(2));
q.Push(Boxes.NewInteger(3));
o := q.Pop();
o := q.Pop();
q.Push(Boxes.NewInteger(4));
o := q.Pop();
o := q.Pop();
q.Push(Boxes.NewInteger(5));
o := q.Pop();
StdLog.String("Is empty: ");StdLog.Bool(q.IsEmpty());StdLog.Ln
END Do;
END UseQueue.
</lang>
Execute: ^Q UseQueue.Do
Output:
Is empty: $TRUE
D
<lang d>class LinkedQueue(T) {
private static struct Node { T data; Node* next; }
private Node* head, tail;
bool empty() { return head is null; }
void push(T item) { if (empty()) head = tail = new Node(item); else { tail.next = new Node(item); tail = tail.next; } }
T pop() { if (empty()) throw new Exception("Empty LinkedQueue."); auto item = head.data; head = head.next; if (head is tail) // Is last one? // Release tail reference so that GC can collect. tail = null; return item; }
alias push enqueue; alias pop dequeue;
}
void main() {
auto q = new LinkedQueue!int(); q.push(10); q.push(20); q.push(30); assert(q.pop() == 10); assert(q.pop() == 20); assert(q.pop() == 30); assert(q.empty());
}</lang>
Faster Version
This versions creates a circular queue able to grow. Define "queue_usage2_main" to run the main and compile the unittests. <lang d>module queue_usage2;
struct GrowableCircularQueue(T) {
public size_t length; private size_t head, tail; private T[] A = [T.init];
bool empty() const pure nothrow { return length == 0; }
void push(immutable T item) pure nothrow { if (length >= A.length) { // Double the queue. const old = A; A = new T[A.length * 2]; A[0 .. (old.length - head)] = old[head .. $]; if (head) A[(old.length - head) .. old.length] = old[0 .. head]; head = 0; tail = length; } A[tail] = item; tail = (tail + 1) & (A.length - 1); length++; }
T pop() pure { import std.traits: hasIndirections;
if (length == 0) throw new Exception("GrowableCircularQueue is empty."); auto saved = A[head]; static if (hasIndirections!T) A[head] = T.init; // Help for the GC. head = (head + 1) & (A.length - 1); length--; return saved; }
}
version (queue_usage2_main) {
unittest { auto q = new GrowableCircularQueue!int(); q.push(10); q.push(20); q.push(30); assert(q.pop() == 10); assert(q.pop() == 20); assert(q.pop() == 30); assert(q.empty());
uint count = 0; foreach (immutable i; 1 .. 1_000) { foreach (immutable j; 0 .. i) q.push(count++); foreach (immutable j; 0 .. i) q.pop(); } }
void main() {}
}</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
<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
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.
<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
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>
Nemerle
The Nemerle.Collections namespace contains an implementation of a Queue. <lang Nemerle>mutable q = Queue(); // or use immutable version as per Haskell example def empty = q.IsEmpty(); // true at this point q.Push(empty); // or Enqueue(), or Add() def a = q.Pop(); // or Dequeue() or Take()</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.
Nimrod
<lang nimrod>import queues
var deq: TQueue[int] = initQueue[int]()
deq.enqueue(26) deq.add(99) # same as enqueue() deq.enqueue(2) echo("Dequeue size: ", deq.len()) echo("De-queue: ", deq.dequeue()) echo("De-queue: ", deq.dequeue()) echo("De-queue: ", deq.dequeue())
- echo("De-queue: ", deq.dequeue()) # dequeue an empty dequeue raises [EAssertionFailed]</lang>
- Output:
Dequeue size: 3 De-queue: 26 De-queue: 99 De-queue: 2
Objeck
<lang objeck> class Test {
function : Main(args : String[]) ~ Nil { q := Struct.IntQueue->New(); q->Add(1); q->Add(2); q->Add(3);
q->Remove()->PrintLine(); q->Remove()->PrintLine(); q->Remove()->PrintLine();
q->IsEmpty()->PrintLine(); }
} </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>
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> Output:
1 3 2 1
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
<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>
1 3 5 7 9 11 13 15 17 19
The queue has:
1 3 5 7 9 11 13 15 17 19
</lang>
PostScript
<lang postscript>
[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
3 1 4 1 5
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>
Racket
<lang Racket>#lang racket
(require data/queue)
(define queue (make-queue))
(enqueue! queue 'black) (queue-empty? queue) ; #f
(enqueue! queue 'red) (enqueue! queue 'green)
(dequeue! queue) ; 'black (dequeue! queue) ; 'red (dequeue! queue) ; 'green
(queue-empty? queue) ; #t</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
- 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>
- 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>
XPL0
<lang XPL0>include c:\cxpl\codes; def Size=8; int Fifo(Size); int In, Out; \fill and empty indexes into Fifo
proc Push(A); \Add integer A to queue int A; \(overflow not detected) [Fifo(In):= A; In:= In+1; if In >= Size then In:= 0; ];
func Pop; \Return first integer in queue int A; [if Out=In then \if popping empty queue
[Text(0, "Error"); exit 1]; \ then exit program with error code 1
A:= Fifo(Out); Out:= Out+1; if Out >= Size then Out:= 0; return A; ];
func Empty; \Return 'true' if queue is empty return In = Out;
[In:= 0; Out:= 0; Push(0); Text(0, if Empty then "true" else "false"); CrLf(0); IntOut(0, Pop); CrLf(0); Push(1); Push(2); Push(3); IntOut(0, Pop); CrLf(0); IntOut(0, Pop); CrLf(0); IntOut(0, Pop); CrLf(0); Text(0, if Empty then "true" else "false"); CrLf(0);
\A 256-byte queue is built in as device 8: OpenI(8); OpenO(8); ChOut(8, ^0); \push ChOut(0, ChIn(8)); CrLf(0); \pop ChOut(8, ^1); \push ChOut(8, ^2); \push ChOut(8, ^3); \push ChOut(0, ChIn(8)); CrLf(0); \pop ChOut(0, ChIn(8)); CrLf(0); \pop ChOut(0, ChIn(8)); CrLf(0); \pop ]</lang>
Output:
false 0 1 2 3 true 0 1 2 3
- Programming Tasks
- Data Structures
- Ada
- AppleScript
- AutoHotkey
- BBC BASIC
- C
- C++
- C sharp
- Clojure
- CoffeeScript
- Common Lisp
- Component Pascal
- D
- Delphi
- E
- Elisa
- Erlang
- Fantom
- Fortran
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Logo
- Lua
- Mathematica
- Nemerle
- NetRexx
- Nimrod
- Objeck
- OCaml
- OoRexx
- Oz
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PostScript
- Initlib
- Prolog
- PureBasic
- Python
- Racket
- REBOL
- REXX
- Ruby
- Scala
- Standard ML
- Tcl
- XPL0
- GUISS/Omit