Queue/Usage
Create a queue data structure and demonstrate its operations. (For implementations of queues, see the FIFO task.)
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.
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>
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>
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
<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
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>
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>
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>