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.
Illustration of FIFO behavior
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>