数组队列和链表队列

   上一周我们学习了用数组来实现队列和用链表来实现队列。数组和链表还有队列的本质都是一样的，都可以理解为用来装东西的容器。
    无论使用数组还使用链表来实现队列，都是要实现几个基本的任务，例如添加，取出，删除和插入等。他们的区别在于使用的形式不同。
    用数组实现队列的关键是创建两个数组，在实现类的内部，还是使用数组保存装入的队列的对象，每次新加入对象时，则创建一个比原来数组长度大于1的数组。优点是可以实现存储多个数据而不必担心数组越界，缺点是存储过程中如果要在指定位置插入和删除会比较麻烦，必须要把指定位置后面的数组整个后移或者前移。
    用链表实现队列的好处是可以很方便的实现定点插入和删除，麻烦的是链表的遍历。
    在使用数组或者链表实现队列的时候，我们可以先定义一个接口list实现基本操作如添加，删除，插入和查找等，然后再用具体的数组队列arraylist，链表队列linklist去实现list的基本方法。
    下面是我写的一段代码，本来是想写五子棋的，可是只写到现在，还不能实现五子棋的人机对战。不过里面有写用链表队列来保存鼠标按下点的坐标。
package cn.netjava.cf0413;

import java.awt.Color;
import java.awt.Graphics;

import javax.swing.JFrame;


public class RewritePaint extends JFrame {
  
MouListener dl;
public static void main(String[] args) {
RewritePaint rp=new RewritePaint();
rp.unit();
}
public void unit(){

//设置窗体的各项参数
this.setSize(900, 700);
this.setLocationRelativeTo(null);
this.setVisible(true);
   Graphics g=this.getGraphics();
//加一个鼠标监听器
      dl=new MouListener(g);
   this.addMouseListener(dl);
}

public void paint(Graphics g){
//绘制五子棋的表格
super.paint(g);
    int x=100,y=100;
    int h=50,n=12,m=15;
    for(int k=0;k<n;k++){
    //绘制表格中的横线
    g.drawLine(x, y+k*h, x+14*h, y+k*h);
             }
    for(int k=0;k<m;k++){
    //绘制表格中的竖线
    g.drawLine(x+k*h, y, x+k*h, y+11*h);
   
    }
    int i=0;
    //接口List实例化一个list对象，用来取出所存的数据
    List<Point>  list = dl.getList();
    for(int k = 0; k < list.size(); k++){
    Point p = list.get(k);
    System.out.println("x="+p.x+" y="+p.y);
    //按照记录的坐标点重画五子棋，并实现黑白颜色的转换
    int x1,y1;
    x1 = p.x;
y1 = p.y;
if(i%2==0){
    g.setColor(Color.BLACK);
}
else{
g.setColor(Color.WHITE);
}
     m=(x1-100)%50;
     n=(y1-100)%50;
    if(m<25){
    x1=(x1-m);
       }
    else{
    x1=(x1-m)+50;
       }
    if(n<25){
    y1=(y1-n);
       }
    else{
    y1=(y1-n)+50;
    }
g.fillOval(x1-25, y1-25,50,50);
i++;
   
    }
    }

}
package cn.netjava.cf0413;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;

public class MouListener implements MouseListener {
private Graphics g;
int i=0;
int x1,y1;
private LinkList<Point> list = new LinkList<Point>();
public MouListener(Graphics g) {
this.g = g;
}
//取出接口List中记录的数据
public List<Point> getList(){
return list;
}

public void mouseClicked(MouseEvent e) {
System.out.println("按下");
x1 = e.getX();
y1 = e.getY();
if(i%2==0){
    g.setColor(Color.BLACK);
}
else{
g.setColor(Color.WHITE);
}
    int m=(x1-100)%50;
    int n=(y1-100)%50;
    if(m<25){
    x1=(x1-m);
       }
    else{
    x1=(x1-m)+50;
       }
    if(n<25){
    y1=(y1-n);
       }
    else{
    y1=(y1-n)+50;
    }
g.fillOval(x1-25, y1-25,50,50);
i++;
//用point类记录x1,y1
Point point = new Point(x1,y1);
  //用接口list实现添加坐标到队列
list.add(point);

}
  
public void mousePressed(MouseEvent e) {

}


public void mouseReleased(MouseEvent e) {

}


public void mouseEntered(MouseEvent e) {

}


public void mouseExited(MouseEvent e) {

}


}
package cn.netjava.cf0413;
//创建一个Point类用来记录坐标点
public class Point {
public int x;
public int y;

public Point(int x, int y){
this.x = x;
this.y = y;
}
}
package cn.netjava.cf0413;

public interface List<E> {

//实现添加操作
public void add(E obj);
//求长度
public int size();
//取出操作
public E get(int index);
//删除操作
public void remove(int index);
//插入操作
public void insert(int index, E obj);
}
package cn.netjava.cf0413;
//定义一个链表，实现链表的基本操作
public class Node<E> {

private E e;
Node<E> next;
public E getData() {
return e;
}
public void setData(E e) {
this.e = e;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}

}package cn.netjava.cf0413;
//用链表队列实现接口的方法，用链表队列来记录坐标点
public class LinkList<E> implements List<E> {
private Node<E> root;
private Node<E> last;

public void add(E obj) {
Node<E> node = new Node<E>();
node.setData(obj);

if(root==null){
root = node;
last = root;
} else {
last.setNext(node);
last = node;
}
}

public int size() {
int size = 0;
if(root != null){
Node<E> temp = root;
while(temp != null){
size++;
temp = temp.getNext();
}
}
return size;
}

@Override
public E get(int index) {
int len = size();
if(index < 0 || index >= len)
throw new java.lang.ArrayIndexOutOfBoundsException("超出范围：0-"+len);
Node<E> temp = root;
for(int i = 0; i < index; i++){
temp = temp.getNext();
}

return temp.getData();
}

@Override
public void remove(int index) {
// TODO Auto-generated method stub

}

@Override
public void insert(int index, Object obj) {
// TODO Auto-generated method stub

}

}
上面的代码是用的链表队列记录坐标点，如果想实现用数组队列记录的话，就只需要重新写一个ArrayList实现接口List的方法，然后再将鼠标监听器方法中的private LinkList<Point> list = new LinkList<Point>();改成private ArrayList<Point> list = new ArrayList<Point>();
ArrayList代码如下：
package cn.netjava.cf0413;
//用数组队列来实现List的方法，记录坐标点
public class ArrayList<E> implements List<E> {
private Object[] arr = new Object[10];
private int len = 0;

public void add(E obj) {
if(len < arr.length){
arr[len++] = obj;
} else {
Object[] arr2 = new Object[arr.length+10];
for(int i = 0; i < arr.length; i++){
arr2[i] = arr[i];
}
arr2[len++] = obj;
arr = arr2;
}
}

public int size() {
return len;
}

public E get(int index) {
if(index < 0 || index > len)
throw new java.lang.ArrayIndexOutOfBoundsException("超出范围： 0-"+len);
return (E)arr[index];
}

public void remove(int index) {

}


public void insert(int index, Object obj) {

}


}