Java LinkedListQueue辅导讲解、辅导java Queue 数据结构算法辅导、辅导java留学生

日期：2018-07-11 08:21

On a computer with a single processor, in order to simulate multi-tasking an

operating system rapidly switches between the various programs running on a

computer, called jobs, running each for fractions of a second a time. The result

is the appearance that all the applications are running at the same time.

There are many strategies used by operating systems to choose the next

application to run but, in general, they are implemented using queues. In this

assignment we will implement two different kinds of queues and, using them,

explore two different job scheduling strategies.

Several classes have been provided to help you:

Class Job This class stores all the information about Job. Your queues should

store objects of this class. This class is complete, you do not need to

modify it. There is no need to submit this class.

Class Simulation This is the actual operating system simulation class. It

includes the main method for this assignment. You will not need to modify

this class but you will need to make some minor adjustments to the main

method. There is no need to submit this class.

Class PriorityQueue This is a skeleton of the PriorityQueue class with some

of the method complete. You will need to fill in the missing methods.

Your final version of this class should be submitted along with the classes

you create.

1

ITI1121

Assignment # 3

1 Style

Conforming your code to proper Java conventions is important! The main ones

that we are looking for are:

Spacing All code “within” something should be indented one level deeper than

whatever they are in. Thus, all code within a class should be indented

deeper than the class declaration. All the code within a method should

be indented deeper than the method declaration. All code within an if,

while, for, switch statement should be indented deeper than the if, while,

for, switch statement.

Naming Every word in a class name should be capitalized (e.g. LinkedListQueue).

For methods and variables, every word after the first word should be capitalized

(e.g. reverseHeapify). For constants (variables declared final),

should be only capital letters, word separated by underscores (e.g. INTEREST

RATE). All names should be meaningful (exception: it is alright

to have loop variables i and j).

Comments At a minimum, all classes, public methods and public variables

should have a JavaDoc comment next to them. It is good practice to

comment sections of your code as well (if you get the code wrong but the

comment is right you may lose fewer marks).

Marks: 3 marks for proper spacing, 3 marks for proper naming

and 4 marks for proper comments. [Total 10 marks]

It is IMPORTANT that all classes compile and run! It is -50%

(to the marks of that class) for every class that does not compile and

-25% for every class that does not run!

2 Queue

We will be implementing two different types of queues and running them on

the same simulator. Since both are queues they must have many methods in

common. It is important that we inform Java of this fact as otherwise we would

have to write a separate simulator for each queue. To do this we need to create

an interface for queues.

Interface Queue Queues are “line ups”, e.g. a line up to get a ticket. They

have the property that elements are removed from the queue in the same

order that they were put into the queue, e.g. the first person in a line is

the first person to be served.

All queues have four common methods: isEmpty, enqueue, dequeue and

clear. The implementations of each of these methods is dependant on

the type of queue which is why we must use an interface. However, below

is a description of what each method is supposed to do.

2

isEmpty checks to see if the queue contains an elements. It returns true

is the queue is empty and false otherwise.

enqueue adds an element to the back queue, e.g. when a person enters a

line they start go to the back and wait their turn. Since our queues store

objects of class Job, enqueue should take in (as a parameter) an object of

class Job and add it to the back of the queue.

dequeue removes an element from the front of the queue, e.g. the person

at the front of the line gets served. Since our queues store objects of class

Job, dequeue removes the front Job from the queue and returns it.

clear removes all the elements from queue, emptying it.

Marks: 2 marks for creating the interface, 2 marks for each method

[Total 10 marks]

3

3 Linked-List Queue

As you know from class, a linked list is a like an array but it is implement by a

series of nodes, containing data, which point to each other. It is very efficient

to add and remove items from a linked list but it is difficult to find items in the

list. This is the opposite of an array where it is very efficient to find items but it

is inefficient to add and remove items. However, for linked lists it is extremely

efficient to add, remove and find items at the start or end of the list which

makes them perfect for queues. Thus, the linked list is the most common way

to implement a queue.

Before we can build a linked-list queue we must first build a linked list. For

a queue all we need is a singly linked list meaning that each node is linked to

the next node.

Node

data

next ?

Node

data

next ?

Node

data

next ?

Node

data

next ?

Node

data

next

Figure 1: A diagram of a singly linked list.

Class Node A linked list is merely a group of nodes that are linked to each

other. Thus, to implement a linked list we need only implement a Node

class. Each Node must store some data, in our case the data should be

of type Job. Because we are building a singly linked list, a Node must also

store a linked to the next Node, if there is one. It there is no next Node

then it should be null.

The Node class merely stores data. Thus, for methods it should provide

getters and setters for the variables. It should also have two constructors:

one which gets the values for both variables from the user and one

which only gets the Job from the user and assumes that the next Node is

null.

Class LinkedListQueue Since a queue is a “line” two important pieces of

information are needed: the start of the line and the end of the line, called

the head and tail respectively. These are obviously of type Node. The

linked list, if properly implemented, will take care of storying everybody

in between the head and tail.

enqueue works just like in a “line” in real life: a new person arrives and

goes to the end of the line, becoming the new end of the line. In our case

we simply add a new Node end to the linked list (the tail Node). This Node

becomes the new tail.

dequeue is different than a “line” in real life. In real life, the whole line

moves forward when a person at the front is served, but this is inefficient in

4

Java. Instead, we can imagine the service counter moving forward towards

the next person in line. Thus, the head Node is removed from the linked

list (and its Job returned) and the next person in the line becomes the

new head of the line.

It is up to you to figure out how isEmpty and clear work.

Marks: For class Node, 1 mark for creating each instance variable,

1 mark for each getter/setter method, 2 marks for each constructor

[Total 10 marks]

For class LinkedListQueue, 5 marks for enqueue, 5 marks for dequeue,

4 marks for clear, 3 marks for isEmpty and 3 marks for the constructor

[Total 20 marks]

5

4 Priority Queue

A priority queue operates differently than a regular queue as it allows some

elements to move through the queue more quickly than others. The classic

example of a priority queue is a hospital emergency room where the sickest

patients are the first to see the doctor even if a less sick patient has been waiting

longer.

Since a queue’s primary responsibility is determining the next element to be

dequeued it must do so very efficiently. In a priority queue this can be tricky

as we want to avoid examining every element in the queue when an element is

enqueued or dequeued (this is considered inefficient). Thus, one common way

to store a priority queue that does this efficiently is a heap.

A heap is an array representation of a binary tree (a tree where every node has

at most two children) such that each subtree of the tree has the heap property.

The heap property is that the root of a tree is greater (has a higher priority)

than any of the other elements in the subtree. Even though it is a binary tree,

a heap is always stored as an array. The children of an element at index i in

array are stored at indices 2i and 2i + 1. The parent of i can be found at index

bi/2c.

9

6 7

4 2 5

9 6 7 4 2 5

Figure 2: A diagram of a heap.

For example, in the heap in Figure 2 the root is node containing 9, which

is also the largest element in the array. It is stored as position 0 in the array

representation of the heap. It has two children6 and 7 stored at positions 1 and

2 in the array which are bigger than all their children (they are the largest in

their respective subtrees). It leaves are 4, 2 and 5.

The trick to a heap is adding and removing elements while preserving the

heap property. There are two methods that do this: heapify and reverseHeapify.

Whenever an element is altered a call to one of these methods will restore the

heap property. If the element altered is an internal node of the tree (a node

with one or more children) then heapify should be called. If it is a leaf of the

6

tree (a node with no children) then reverseHeapify should be called.

heapify works by comparing the current internal node with its children to

see which is the largest. If the root is not the largest then it is swapped with

the largest of its children. Since the child has now been altered it needs to check

to make sure it still satisfies the heap property. heapify works its way down

the tree in this manner and, when it is complete, the tree should again be a

heap. The details of how heapify works are a little complex but the method

is provided for you, you just need to understand when to use it, which we will

discuss a bit more below.

reverseHeapify works by comparing the current node with its parent. It

the current node is larger than its parent then it swaps itself with its parent.

The parent still might not be correct, it now needs to compare its parent with its

grand parent, and so on, until it reaches the top of the tree. reverseHeapify is

easy to implement using a while loop which keeps going until parent is larger

than the child. While the parent is smaller than the child it swaps the parent

with the child and makes then moves up to the parent (so that the parent will

become the child during the next iteration of the loop). We will discuss when

to use reverseHeapify a bit more below.

Class PriorityQueue The priority of a Job is determined by the owner of

the Job. Job has a method getOwner that returns a number 0, 1 or 2

indicating the owner. The higher the number of the owner the higher the

priority of the Job. There will likely be many Jobs with the same priority.

Since we are using a heap (a type of array) we don’t need to keep track of

the head like in a linked-list queue. This is because it is always position

0 in the array. However, we do need to keep track of atail. The tail is

the position after the last used position in the array. Thus, the tail of an

empty queue will be at position 0.

Included with the assignment is a skeleton the the class. Some of the

methods needed by the heap have been implemented for you. Methods

left, right and parent give the index of the left child, right child and

parent respectively of an index i. The method swap swaps two elements

of the array. heapify is also implemented for you. Also, the constructor

has been implemented for you already, there is no need to modify it.

You will need to implement the queue methods: isEmpty, enqueue, dequeue

and clear. You will also need to implement reverseHeapify. Since a

heap is an array, you will also need to implement resize, which doubles

the size of the array just like in Assignment #1.

enqueue adds an element to the end of the heap (the tail). Since the

heap is stored as an array, this simply means adding an element at the

tail and incrementing the tail. However, we must ensure that the heap

property is maintained. Since the last element in the heap cannot have

any children it must be a leaf so we can call reverseHeapify to enforce

the heap property. Also, if the heap is too small to add a new element,

we must call resize before adding the element.

7

dequeue removes the first element in the heap and returns it. The challenge

is that we cannot leave the beginning of the array empty. We cannot

shift the other elements forward either, not only is this inefficient but it

will also destroy the heap property. The trick is to realize that we can

replace the first element with absolutely any element in the heap so long

as heapify is called. There is only one element that can be moved without

destroying the heap property: the last element. Thus, we swap the first

element and the last element of heap, remove and return the last element

and then call heapify on the first element.

reverseHeapify is described above. resize is the same as Assignment

#1. It is up to you to figure out how to implement isEmpty and clear.

Marks: For class PriorityQueue, 6 marks for reverseHeapify, 5

marks for enqueue, 5 marks for dequeue, 4 marks for resize, 4 marks

for clear, 3 marks for isEmpty and 3 marks for the constructor [Total

30 marks]

8

5 Operating System Scheduler

Two scheduling strategies for an operating system scheduler are first come first

serve (FCFS) and fixed priority pre-emptive scheduling (FPPS). Since queues

operate on a first come first serve basis, FCFS is implemented using a queue.

Similarly, FPPS is implemented using a priority queue.

The operating system scheduler simulation is already provided for you. To

use it you simply need to modify the main method to run the simulator using

either the LinkedListQueue or the PriorityQueue.

Run the simulator a few times with each type of queue. Answer the following

four questions about your experiments in a plain text file called scheduler.txt.

1. What are differences in how the jobs are managed between FCFS and

FPPS?

2. What is are the advantages of FCFS over FPPS and vice versa?

3. What potential problems do you see happening if you were using an operating

system with an FCFS scheduler?

4. What potential problems do you see happening if you were using an operating

system with an FPPS scheduler?

Marks: THIS QUESTION WILL NOT BE MARKED IF YOU

PROGRAM DOES NOT COMPILE AND RUN!

3 marks for question 1, 3 marks for question 2, 2 marks for question

3, 2 marks for question 4 [Total 10 marks]

6 Submit

Please submit the following files:

? Queue.java

? Node.java

? LinkedListQueue.java

? PriorityQueue.java

? scheduler.txt