Admin: 1 версия

2010-06-01T05:04:50Z

1 версия

в 17:44, 31 мая 2010

2010-05-31T17:44:27Z

Новая страница

== A Queue Implemented by a Linked List ==



<source lang="java">
class Link {
public int iData;
public Link next;
public Link(int id) {
iData = id;
}
public String toString() {
return "{" + iData + "} ";
}
}
class LinkList {
private Link first;
public LinkList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(int dd) {
Link newLink = new Link(dd);
newLink.next = first;
first = newLink;
}
public int deleteFirst() {
Link temp = first;
first = first.next;
return temp.iData;
}
public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}
class FirstLastList {
private Link first;
private Link last;
public FirstLastList() {
first = null;
last = null;
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(int dd) {
Link newLink = new Link(dd);
if (isEmpty())
last = newLink;
newLink.next = first;
first = newLink;
}
public void insertLast(int dd) {
Link newLink = new Link(dd);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}
public int deleteFirst() {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}
public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}
class LinkQueue {
private FirstLastList theList;
public LinkQueue() {
theList = new FirstLastList();
}
public boolean isEmpty() {
return theList.isEmpty();
}
public void insert(int j) {
theList.insertLast(j);
}
public double remove() {
return theList.deleteFirst();
}
public String toString() {
return theList.toString();
}
}
public class MainClass {
public static void main(String[] args) {
LinkQueue theQueue = new LinkQueue();
theQueue.insert(20);
theQueue.insert(40);
System.out.println(theQueue);
theQueue.insert(60);
theQueue.insert(80);
System.out.println(theQueue);
theQueue.remove();
theQueue.remove();
System.out.println(theQueue);
}
}</source>



<pre class=codeResult>{20} {40}
{20} {40} {60} {80}
{60} {80}</pre>

== Priority Queues ==

<p>In a priority queue, items are ordered by key value, so that the item with the lowest
key (or in some implementations the highest key) is always at the front.
Items are inserted in the proper position to maintain the order.</p>



<source lang="java">
class PriorityQueue {
private int maxSize;
private double[] queArray;
private int nItems;
public PriorityQueue(int s) {
maxSize = s;
queArray = new double[maxSize];
nItems = 0;
}
public void insert(double item) {
int j;
if (nItems == 0) {
queArray[nItems++] = item;
} else {
for (j = nItems - 1; j >= 0; j--)
{
if (item > queArray[j])
queArray[j + 1] = queArray[j];
else
break;
}
queArray[j + 1] = item;
nItems++;
}
}
public double remove() {
return queArray[--nItems];
}
public double peekMin() {
return queArray[nItems - 1];
}
public boolean isEmpty() {
return (nItems == 0);
}
public boolean isFull() {
return (nItems == maxSize);
}
}
public class MainClass {
public static void main(String[] args) {
PriorityQueue thePQ = new PriorityQueue(5);
thePQ.insert(30);
thePQ.insert(50);
thePQ.insert(10);
thePQ.insert(40);
thePQ.insert(20);
while (!thePQ.isEmpty()) {
double item = thePQ.remove();
System.out.print(item + " ");
}
}
}</source>



<pre class=codeResult>10.0 20.0 30.0 40.0 50.0</pre>

== Queue: The first item inserted is the first to be removed (FIFO) ==



<source lang="java">
class Queue {
private int maxSize;
private int[] queArray;
private int front;
private int rear;
private int nItems;
public Queue(int s) {
maxSize = s;
queArray = new int[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
public void insert(int j) {
if (rear == maxSize - 1)
rear = -1;
queArray[++rear] = j;
nItems++;
}

public int remove() {
int temp = queArray[front++];
if (front == maxSize)
front = 0;
nItems--;
return temp;
}
public int peekFront() {
return queArray[front];
}
public boolean isEmpty() {
return (nItems == 0);
}
public boolean isFull() {
return (nItems == maxSize);
}
public int size() {
return nItems;
}
}
public class MainClass {
public static void main(String[] args) {
Queue theQueue = new Queue(5); // queue holds 5 items
theQueue.insert(10); // insert 4 items
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // remove 3 items
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // insert 4 more items
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while (!theQueue.isEmpty()) { // all items
int n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
}
}</source>



<pre class=codeResult>40 50 60 70 80</pre>

← Предыдущая	Версия 05:04, 1 июня 2010
(нет различий)

Java Tutorial/Collections/Your Queue - История изменений

Admin: 1 версия

в 17:44, 31 мая 2010