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
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>
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>
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>
Logo
UCB Logo comes with a protocol for treating lists as queues.
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
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>
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>
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>