Queue/Usage: Difference between revisions
(Ada solution added) |
No edit summary |
||
Line 9: | Line 9: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<ada> |
<lang ada> |
||
with FIFO; |
with FIFO; |
||
with Ada.Text_Io; use Ada.Text_Io; |
with Ada.Text_Io; use Ada.Text_Io; |
||
Line 31: | Line 31: | ||
Put_Line ("Is_Empty " & Boolean'Image (Is_Empty (Queue))); |
Put_Line ("Is_Empty " & Boolean'Image (Is_Empty (Queue))); |
||
end Queue_Test; |
end Queue_Test; |
||
</ |
</lang> |
||
Sample output: |
Sample output: |
||
<pre> |
<pre> |
||
Line 37: | Line 37: | ||
</pre> |
</pre> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
Note that with C++'s standard queue, accessing the first element of the queue and removing it are two separate operations, < |
Note that with C++'s standard queue, accessing the first element of the queue and removing it are two separate operations, <tt>front()</tt> and <tt>pop()</tt>. |
||
<cpp> |
<lang cpp> |
||
#include <queue> |
#include <queue> |
||
#include <cassert> // for run time assertions |
#include <cassert> // for run time assertions |
||
Line 85: | Line 85: | ||
assert( q.empty() ); |
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 < |
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 <tt>q</tt> to |
||
<cpp> |
<lang cpp> |
||
std::queue<int, std::list<int> > |
std::queue<int, std::list<int> > |
||
</ |
</lang> |
||
(and add < |
(and add <tt>#include <list></tt>, of course). Also note that the containers can be used directly; in that case <tt>push</tt> and <tt>pop</tt> have to be replaced by <tt>push_back</tt> and <tt>pop_front</tt>. |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
In Java 1.6 and above, LinkedList uses a double-ended queue (deque) implementation under the hood. 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 <tt>push</tt> and <tt>pop</tt> methods. |
In Java 1.6 and above, LinkedList uses a double-ended queue (deque) implementation under the hood. 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 <tt>push</tt> and <tt>pop</tt> methods. |
||
<java> |
<lang java> |
||
import java.util.LinkedList; |
import java.util.LinkedList; |
||
import java.util.Queue; |
import java.util.Queue; |
||
Line 110: | Line 110: | ||
System.out.println(queue); // [2, 3] |
System.out.println(queue); // [2, 3] |
||
System.out.println(queue.isEmpty()); // false |
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. |
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. |
||
{{works with|Java|1.4}} |
{{works with|Java|1.4}} |
||
<java> |
<lang java> |
||
import java.util.LinkedList; |
import java.util.LinkedList; |
||
... |
... |
||
Line 127: | Line 127: | ||
System.out.println(queue); // [2, 3] |
System.out.println(queue); // [2, 3] |
||
System.out.println(queue.isEmpty()); // false |
System.out.println(queue.isEmpty()); // false |
||
</ |
</lang> |
||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
Line 144: | Line 144: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
<ocaml># let q = Queue.create ();; |
<lang ocaml># let q = Queue.create ();; |
||
val q : '_a Queue.t = <abstr> |
val q : '_a Queue.t = <abstr> |
||
# Queue.is_empty q;; |
# Queue.is_empty q;; |
||
Line 180: | Line 180: | ||
- : int = 4 |
- : int = 4 |
||
# Queue.is_empty q;; |
# Queue.is_empty q;; |
||
- : bool = true</ |
- : bool = true</lang> |
Revision as of 15:31, 3 February 2009
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
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.
Java
In Java 1.6 and above, LinkedList uses a double-ended queue (deque) implementation under the hood. 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. <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>