Queue/Usage

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.

You may see other such structures in the Data Structures category.

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

See FIFO for the needed code. <lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <stdbool.h>

1. 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>

1. include <queue>
2. 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

Works with: Java version 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 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.

Works with: Java version 1.4

<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

Works with: UCB 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>

1. Queue.is_empty q;;

- : bool = true

1. Queue.add 1 q;;

- : unit = ()

1. Queue.is_empty q;;

- : bool = false

1. Queue.add 2 q;;

- : unit = ()

1. Queue.add 3 q;;

- : unit = ()

1. Queue.peek q;;

- : int = 1

1. Queue.length q;;

- : int = 3

1. Queue.iter (Printf.printf "%d, ") q; print_newline ();;

1, 2, 3, - : unit = ()

1. Queue.take q;;

- : int = 1

1. Queue.take q;;

- : int = 2

1. Queue.peek q;;

- : int = 3

1. Queue.length q;;

- : int = 1

1. Queue.add 4 q;;

- : unit = ()

1. Queue.take q;;

- : int = 3

1. Queue.peek q;;

- : int = 4

1. Queue.take q;;

- : int = 4

1. Queue.is_empty q;;

- : bool = true</lang>