Queues have the property that, the earlier an item enters a queue, the earlier it will leave the queue. A queue has the following properties

First in, first out (FIFO) data structure

A queue is a restricted form of a list.

Additions to the queue must occur at the rear (back).

Deletions from the queue must occur at the front

Example: Ethernet and printers

Ethernet is a set of protocols describing how devices on a network can communicate

Typical Ethernet configuration

Devices place messages onto the network preceded by an ‘id number’ of the device the message is intended for. If two devices try to send messages at the same time a collision occurs and none of the messages are sent.

Devices operate at differing speeds

PC may place document on network at 100,000 cps

Ethernet transmits document at >1,250,000 cps

Printer may only processes 10,000 cps

How does the printer handle the pileup of characters sent by the PC?

Answer - Print buffers

A buffer is a queue. Incoming data is stored at the rear

It normally processes data in a FIFO manner, except when using a priority queue

eg print all small documents before large documents

 // … read characters until '.' found, adding each char to Q and S.
   get input character;
   while input character not equal to '.‘
   begin
		q.add( character );
     		s.push( character );
		get input character;
   end while
   while ( ! q.isEmpty( ) ) begin
     		output "Q: " + q.remove( ) + '\t';
 		output "S: " + s.pop( ) + '\n';
   end while
   stop

Sample program output, given input sequence a b c:

Q: a      S: c

Q: b      S: b

Q: c      S: a

NB. Queues preserve order while stacks reverse it.

Worked Exercise:

What is the output resulting from the following sequence, where q is an initially empty queue of int:

   q.addQ( 1 );
   q.addQ( 2 ); 
   q.addQ( 3 );
   output q.front( );
   output q.removeQ( );
   output q.front( );
   if ( q.isEmpty( ) )
        output "empty\n";
   else
        output "not empty\n";
   end if

Program analysis – 📷 array implementation

📷 Program Output

x

x

Queue creator (constructor)

     // set up the queue front and back
     begin createQ( )
        set queueFront to 0;
        set queueRear to -1;
     end createQ;

add( ) algorithm

     // function to add an item onto the front of the queue
     begin add( queueElement qe ) 
        if ( queueFull ) begin
           output "Queue is full\n";
           set ok to false;
        end
        else begin
           inc queueRear;
           set queue[ queueRear ] = qe;
           set ok to true;
       end if
       return ok;
     end add;

remove( ) algorithm

     // function to remove the top item from the queue myQueue
     begin remove(queueElement qe)
        if ( queueEmpty )
           output "Queue is empty\n";
           set ok to false;
        end
        else begin
           qe = queue[ queueFront  ];
           inc queueFront;
           set ok to true;
        end if
        return ok;
     end remove;

queueEmpty( ) and queueFull( )

     // function checks to see if the queue is empty
     begin queueEmpty(  )
        return queueFront > queueRear;
     end queueEmpty;
     // function checks to see if the queue is full
     begin queueFull(  )
        // N.B. use -1 because array starts at zero for first array item
        return queueRear == ( maxQueueSize - 1 );
     end queueFull;

We cannot increase rear beyond the limits of the array. Therefore, this queue must be regarded as full, even though there are plenty of available memory cells. One way to solve this might be to Wait until the queue empties out and Then reset it and start again. In the computer processing job example however, this would be unacceptable since many jobs could arrive while the queue is emptying out.

Another difficulty

Our definition of empty is rear < front, so it is empty. But, rear has reached its limit. It cannot go beyond the array, Therefore, the queue is full!

The solution: 📷 wrapping around

📷 The Circular queue

Example:

Queue is an array of 4 elements. We wish to enqueue (Q.add) and dequeue (Q.remove) multiple items.

Enqueue and dequeue operations

With an array, it is easy to run out of space in the queue to enqueue (Q.add) items and yet still have unused memory cells that can store data! To get around this, we have to make it possible to ‘wrap around’. Both ‘rear’ and ‘front’ must be able to wrap around.

How to wrap around:

If rear + 1 > MAXQUEUESIZE -1 then set rear to 0

OR preferable to use modulo operator

rear = (rear+1) % MAXQUEUESIZE

NB same goes for front

front = (front) % MAXQUEUESIZE

Main issues (full and empty)

Wrapping around allows us to avoid an erroneous ‘full’, but, it means that we cannot use ‘rear < front’ as a test of whether the queue is empty because rear will become < front as soon as it wraps around

If there is one element in the queue then rear should be the same as front, therefore, rear must start < front.

You could check for an empty queue with something like: nextPos(rear) == front, but, when the queue is full it is also true that nextPos(rear) == front!

Solution

To solve this dilemma we let the definition of empty use the length() method

Then the test for empty is length() == 0, and the test for full is length == MAXQUEUESIZE

Solution

Queues are often used for sending and receiving asynchronous messages. Asynchronous means that the sender does not wait for a response from the receiver, but assumes that the receiver will get the message at some later time. For example, when you use a mobile phone you can communicate either synchronously or asynchronously:

Synchronous: Talk – callers communicate in real time conversation, content is “processed” immediately, not stored

Asynchronous: Text/email – messages are sent and stored until read. In asynchronous communication the messages are usually stored in some intermediate location, e.g. a queue or mailbox.

Asynchronous messages can obviously be used for communication between people. They can also be used in some situations for communication between components of a software system.

Message queue example

The following Java code shows four classes, Message, MessageSender and MessageReceiver, that make up a very simple text message system. MessageSender and MessageReceiver both need to use an instance of SimpleQueue to send/get messages. MessageTester is a simple test programme that creates a queue, and makes a MessageSender send messages to be received by a MessageReceiver. The messages are received in the order that they were sent, and the receiver can get one message at a time, or get all the messages from the queue at once.

import java.util.*;
import java.text.*;

public class Message
{
    public StringBuffer sender;
    public StringBuffer recipient;
    public StringBuffer content;
    public Date date;

    public Message()
    {
        String sender = "unknown sender";
        this.sender = new StringBuffer(sender);
        String recipient = "unknown recipient";
        this.recipient = new StringBuffer(recipient);
        String content = "none";
        this.content = new StringBuffer(content);
        this.date = new Date();
    }

    public Message(String sender, String recipient, String content)
    {
        this.sender = new StringBuffer(sender);
        this.recipient = new StringBuffer(recipient);
        this.content = new StringBuffer(content);
        this.date = new Date();
    }

    public String getDate()
    {
        return DateFormat.getDateTimeInstance().format(this.date);
    }
    
    @Override
    public String toString(){
        StringBuffer s = new StringBuffer();
        s.append("From:");
        s.append(sender);
        s.append(",To:");
        s.append(recipient);
        s.append(",Content: ");
        s.append(content);
        s.append(",Date: ");
        s.append(getDate());
        
        return s.toString();
    }
}

public class MessageSender
{

    public void sendMessage(Message m, SimpleQueue q)
    {
        if(!q.isFull())
            q.enqueue(m.toString());
        else
            System.out.println("Cannot send - queue is full");
    }
}

public class MessageReceiver
{
    
    public void receiveMessage(SimpleQueue q)
    {
        String s = q.dequeue();
        if (s != null)
        {
            System.out.println(s);
        }
        else
            System.out.println("No messages to receive");
    }
}

public class MessageTester {

    public static void main(String[] args) {
        SimpleQueue q = new SimpleQueue();
        q.createQueue();

        MessageSender ms = new MessageSender();
        MessageReceiver mr = new MessageReceiver();

        Message m1 = new Message("Bob", "Alice", "Hello");
        Message m2 = new Message("Jane", "Joe", "Good morning");
        Message m3 = new Message("Jack ", "Jill", "See you later");
        Message m4 = new Message("George", "Mildred", "Good evening");
        Message m5 = new Message("Diane", "Sam", "Bye for now");

  ms.sendMessage(m1, q);
        ms.sendMessage(m2, q);
        ms.sendMessage(m3, q);

        mr.receiveMessage(q);

        ms.sendMessage(m4, q);
        ms.sendMessage(m5, q);

        while (!q.isEmpty()) {
        mr.receiveMessage(q);
        }
    }
}