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

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>

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() );

} </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

<java>

import java.util.LinkedList;
import java.util.Queue;
...
Queue<Integer> queue = new LinkedList<Integer>();
System.out.println(queue.peek() == null); // 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.peek() == null); // false

</java>

Java 1.4 compatible version: <java>

import java.util.LinkedList;
...
LinkedList queue = new LinkedList();
System.out.println(queue.size() == 0);    // 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.size() == 0);    // false

</java>

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