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
<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; </ada> 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()
.
<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() );
} </cpp>
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
<cpp>
std::queue<int, std::list<int> >
</cpp>
(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. <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 </java>
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.
<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 </java>
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
<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</ocaml>