Queue/Usage: Difference between revisions
Added PicoLisp |
|||
Line 509: | Line 509: | ||
(a b c) |
(a b c) |
||
NIL</pre> |
NIL</pre> |
||
=={{header|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 |
|||
</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 00:47, 25 February 2010
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
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>
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
</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>