Queue Class Sample

public class Queue{

private int[] myQ;

private int front;

private int rear;

private int qLength;

public Queue(){

this.myQ = new int[10];

this.front = 0;

this.rear = 0;

this.qLength = 0;

}

public boolean isEmpty(){

//check if the length of the queue is 0

if(qLength==0){

return true;

}else{

return false;

}

}

public boolean isFull(){

//check if the length of the queue is the same as the length of the array

if(qLength==myQ.length){

return true;

}else{

return false;

}

}

}

See below for ideas on how to code the enqueue and dequeue methods.

pop out

queue review

Name 3 methods which operate on a queue.

Describe the behaviour of a queue.

The names of 10 students are input and enqueued onto a queue, NAMES. Write the algorithm in pseudocode.

A queue of names, NAMES, exists. Write an algorithm that will empty the queue and output how many names were in the queue.

queues

first in, first out

A Queue is an abstract data structure.

It stores data and...

... is has methods which can manipulate the data.

In this course, those methods are:

  • queue(item)
  • dequeue()
  • isEmpty()
  • isFull()

In this course we will look at the concept of a queue from a conceptual viewpoint and we will also consider how to process a queue using Java.

enqueue
dequeue

Queue

    0
    1
    2
    3
    4
front rear length
0 0 0

The simulation implements a queue using an array of fixed size - a static array.

The principals of a queue's operation are:

  • Data can be enqueued onto the rear of the queue.
  • Data can be dequeued from the front of the queue.
  • When dequeueing data off the queue, the first item of data in the queue is the first item off. This is known as first-in-first-out fifo
  • Note that we need a pointer to track the front of the queue when items are dequeued.
  • We also need to track the rear of the queue when we enqueue.

Queue behaviour is different from Stack behaviour, where we only need to track the top of the stack.

Pseudocode Example #1

Here is an example of enqueuing 5 integers into an empty queue, Q:

loop i from 0 to 4

input item //eg from keyboard

Q.enqueue(item)

end loop

In the simulation, notice that the rear pointer is used to place item at the correct index and is then updated, waiting for the next item.

Here is an idea for this method using Java:

public void enqueue(int item){

myQ[rear] = item;

qLength = qLength + 1; //update the length of the queue

//logic to update the rear pointer

if(rear==myQ.length-1){

rear = 0;

}else{

rear = rear + 1;

}

}

Note: we need to track the length of the queue (not the array!) to test if it is full or empty.

Pseudocode Example #2

Here is an example of dequeuing Q and displaying the items being dequeued:

loop while not Q.isEmpty()

item = Q.dequeue()

output item

end loop

In the simulation, notice that we we dequeue, we dequeue from the front (First In, First Out).

Here is an idea for the dequeue method using Java:

public int dequeue(){

firstItem = myQ[front]; //grab the item at the front

//logic to update the rear pointer

if(front == myQ.length-1){

front = 0;

}else{

front = front + 1;

}

qLength = qLength - 1; //update the length of the queue

return firstItem;

}

Note again that we are updating the length of the queue when necessary. This will allow us to determine of the queue is empty or full. When dequeuing, the front pointer is processed, the queue length is updated and the front item is returned.

Pseudocode Example #3

A collection NAMES exists.

Each item from the collection is enqueued into a queue, Q:

count = 0

NAMES.resetNext()

loop while NAME.hasNext()

name = NAMES.getNext()

Q.enqueue(name)

count = count+1

end loop

output count," items were enqueued!"

Study Option

As you can see, the Queue concept is pretty straightforward from a pseudocode persepctive.

In Paper 1, you should have a good opportuity to pick up points on a Queue question if you get the enqueue/dequeue concepts.

The tricky bit is understanding the Java sample. You will not be tested on this in Paper 1. However, as a programming exercise it would be valuable to attempt to design the Queue class and then create an instance of the class and enqueue/dequeue items.

This is especially recommended for students who are aiming for a high score, or are thinking of studying computer science after high school.

Exercises

Past Paper Questions

Tags

stack queue circular enqueue dequeue fifo empty full