队列

   用数组来存取数据的好处是数据是有序的，便于通过下标对其进行操作。但是数组一旦定义，其长度就是固定的。当用户不知道要存入的数据个数时，用数组就不方便了，因为如果定义长度太大会造成资源的浪费，可如果定义的长度太小又会不能将所有数据存入。因而，需要一个可以动态分配存储空间还可以有序的存放对象的数据结构，队列恰好可以满足上述条件。  
   队列的实现实际也是通过在实现类的内部使用数组保存入队的对象，每次增加新对象时，创建一个比原来数组长度大1的新数组，然后将要加入数据放在新数组的最后一位，再将原数组中的数据放入新数组中，最后让原数组指向新数组的内存地址。
   具体代码如下：
/**
* 定义一个队列类
* @author Administrator
*
*/
public class Queue {
String[] src = new String[0];
/**
  * 实现一个添加元素的方法
  * @param s 是要添加的元素
  */
public void add(String s){
//定义一个新的数组，长度为原数组长度+1
String[] dest = new String[src.length+1];
//将原来数组中的元素依次存入新数组
for(int i=0;i<src.length;i++){
dest[i] = src[i];
}
//将s放入新数组的最后一位
dest[src.length] = s;
//将新数组赋值给原数组
src = dest;
}

/**
* 在下标为i的位置插入s
* @param i
* @param s
*/
public void insert(int i,String s){
//定义一个新的数组，长度为原数组长度+1
String[] dest = new String[src.length+1];
for(int j=0;j<i;j++){
dest[j] = src[j];
}
dest[i] = s;
for(int j=i+1;j<dest.length;j++){
dest[j] = src[j-1];
}
//将新数组赋值给原数组
src = dest;
        }
/**
  * 打印出队列元素
  */
public void print(){
for(int i=0;i<src.length;i++){
String s = src[i];
System.out.println(s);
}
}
/**
* 删除下标为i的元素
* @param i
*/
public void delete(int i){
//定义一个新的数组，长度为原数组长度+1
String[] dest = new String[src.length-1];
for(int j=0;j<i;j++){
dest[j] = src[j];
}
for(int j=i;j<dest.length;j++){
dest[j] = src[j+1];
}
//将新数组赋值给原数组
src = dest;

}


/**
* 查找下标为i的元素
* @param i
* @return
*/
public String get(int i){
String s = src[i];
return s;
}

/**
* 修改下标为i的元素
* @param i
*/
public void modify(int i,String s){
src[i] = s;
}
public int size(){
return src.length;
}
}




import java.util.Scanner;

/**
* 定义一个队列测试类
* @author Administrator
*
*/
public class QueueTest {
      public static void main(String args[]){

Queue qu = new Queue();
//给队列添加元素
for(int i=0;i<10;i++){
qu.add("姓名"+i);
} 
qu.print();

System.out.println("输入1执行的是插入操作");
System.out.println("输入2执行的是删除操作");
System.out.println("输入3执行的是找操作");
System.out.println("输入4执行的是找操作");
System.out.println("请输入：");

for(int i=0;i<4;i++){
    Scanner input = new Scanner(System.in);
             int choose = input.nextInt();
             switch(choose){
        case 1:  qu.insert(3,"插入者");break;
        case 2:  System.out.println("请输入删除的元素位置：");
int n = input.nextInt();
qu.delete(n); break;
        case 3:   System.out.println("请输入查找的元素位置：");
int m = input.nextInt(); String s =qu.get(m);
System.out.println(s);return;
        case 4:   qu.modify(1,"被改了");break;  
        default : System.out.println("请输入1至4");
}

    qu.print();
    System.out.println();
}
}
}

评论

4 楼 smartan 2013-03-24  

话说这就是所谓的以时间换空间吧

3 楼 NX 2013-03-23  

是的，真心感谢各位提出的意见和建议，我也在修改代码，主要是在怎样扩容和实现“泛型”方面。

2 楼 xchd 2013-03-23  

队列不是先进先出吗？好像没有体现这点。

1 楼 kidding87 2013-03-23  

你这里应该和jdk学习下，动态的容量，怎么去扩容，你这里效率非常低，每次add一个就要new一个新的数组这样很浪费

jdk的ArrayList做法是固定的按照比例来扩容 初始容量 加 负载因子 一般容量是2^n次个
然后使用System.arrayCopy来复制数组，这里也很快

还有楼主队列，一般来说，有两种实现，一种是链表 一种是数组
你这个还有待提高