1 2007 6 26 26 (sakai.keiichi@kochi sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2007/index.html tech.ac.jp/k1sakai/lecture/alg/2007/index.html
FIFO
(46 ) head, front tail, rear nn 0 n n+1
2 AND
public class Queue private Queue() public Queue(int amaxsize) int realsize = amaxsize + 1; this.maxsize = realsize; this.queuearray = new Object[realSize]; this.front = 0; this.rear = 0; private int front; private int maxsize; private Object[] queuearray; private int rear; front, rear maxsize
public Object dequeue() if(this.isempty()) System.err.println(" "); return null; Object dequedobject = this.queuearray[this.front]; this.queuearray[this.front] = null; ++this.front; if(this.maxsize == this.front) this.front = 0; return dequedobject; public boolean isempty() return (this.rear == this.front); front
public boolean enqueue(object atarget) if(this.isfull()) System.err.println(" "); return false; this.queuearray[this.rear] = atarget; ++this.rear; if(this.maxsize == this.rear) this.rear = 0; return true; public boolean isfull() return ((this.rear + 1) == this.front); rear
public void printall() System.out.println(" "); if(this.isempty()) System.out.println(); return; front rear int count = 1; int position = this.front; int limit = (this.front > this.rear)? this.maxsize: this.rear; while(position < limit) System.out.println(count +" t" + this.queuearray[position]); ++count; ++position; position = 0; limit = (this.front > this.rear)? this.rear: 0; while(position < limit) System.out.println(count +" t" + this.queuearray[position]); ++count; ++position; System.out.println();
// // Java public class Element1 public Element1(Object adata) this.data = adata; public Object getdata() return this.data; public Element1 getnextelement() return this.; public void setnextelement(element1 annextelement) this. = annextelement; private Object data; // private Element1 ; /* */ /* C */ union Object int Integer; double Double; ; struct Element1 union Object data; struct Element1 *; ; // // Java public class Element2 public Element2() public Object data; public Element2 ; /* */ /* C */ struct Element2 void *data; struct Element2 *; ;
// // Java // Element1 _element1; // Element1 new_element1; new_element1 = new Element1(new Integer(100)); new_element1. setnextelement(_element1); Integer /* *//* C */ /* struct Element1 *_element1: /* 100 */ new_element1 Element1 struct Element1 *new_element1; data new_element1 getdata() = malloc(sizeof (struct Element1)); new_element1->data.integer getnextelement() = 100; data new_element1-> setnextelement() = _element1; // // Java // Element2 _element2; _element1 // 100 data Element2 new_element2; Element1 new_element2 = new Element2(); _element1 new_element2.data = new Integer(100); getdata() new_element2. = _element2; getnextelement() _element1 data new_element2 /* *//* C */ /* struct Element2 *_element2: /* setnextelement() */ struct Element2 *new_element2; data data new_element2 = malloc(sizeof (struct Element2)); Element2 new_element2->data = malloc(sizeof (int)); *((int *)new_element2->data) = 100; /* cast as lvalue data */ new_element2-> = _element2; _element2 100
// // Java public class Element1 public Element1(int adata) this.data = adata; public int getdata() return this.data; public Element1 getnextelement() return this.; public void setnextelement(element1 annextelement) this. = annextelement; private int data; // private Element1 ; /* */ /* C */ struct Element1 int data; struct Element1 *; ; // // Java public class Element2 public Element2() public int data; public Element2 ; /* */ /* C */ struct Element2 int *data; struct Element2 *; ;
// // Java // Element1 _element1; // Element1 new_element1; new_element1 = new Element1(100); new_element1. setnextelement(_element1); /* *//* C */ /* struct Element1 *_element1: /* */ new_element1 Element1 struct Element1 *new_element1; data new_element1 getdata() = malloc(sizeof (struct Element1)); new_element1->data.integer getnextelement() = 100; data new_element1-> setnextelement() = _element1; // // Java // Element2 _element2; // Element2 new_element2; 100 Element1 new_element2 = new Element2(); _element1 new_element2.data = 100; getdata() new_element2. = _element2; getnextelement() data new_element2 /* *//* C */ /* struct Element2 *_element2: /* setnextelement() */ struct Element2 *new_element2; data new_element2 = malloc(sizeof (struct Element2)); Element2 new_element2->data = malloc(sizeof (int)); *((int *)new_element2->data) = 100; /* cast as lvalue data */ new_element2-> = _element2; _element2 100
Java Java Java