Queue/Usage: Difference between revisions
Line 824: | Line 824: | ||
uncons |
uncons |
||
= 1 [2 3 4 5 6] |
= 1 [2 3 4 5 6] |
||
[] empty? |
|||
=true |
|||
</lang> |
</lang> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
<lang PureBasic>NewList MyStack() |
<lang PureBasic>NewList MyStack() |
Revision as of 08:20, 27 March 2011
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
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>
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.
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
Container support in Go is weak yet. I used the package I wrote for 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
Groovy
<lang groovy>def queue = [] println queue.empty // empty queue << 1 << 2 << 3 println queue // [1,2,3] queue.pop() println queue // [1,2]</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>
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 http://rosettacode.org/wiki/Queue#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>
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>
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>
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>
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>
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>