分别用数组和链表实现队列

矫情吗；* 2022-04-21 14:10 141阅读 0赞

Java语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。 链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。从逻辑结构来看， 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）。从内存存储来看 ， (静态)数组从栈中分配空间, 对于查找删除,但是自由度小 ， 链表从堆中分配空间, 自由度大但是查找和管理比较麻烦。利用数组来组织数据结构 优点是：存储效率高，存取速度快。 但是，对于数据元素个数动态增长的情况，由于数组个数不能自由扩充（动态数组除外），一旦空间用完就不能再向里加入新元素，否则，就会导致系统停工。 利用链表则适用于插入或删除频繁、存储空间需求不定的情况，但是数据读取比较繁琐。  
因此，在处理某些不确定的数据时，我们常常要用到队列，下面我简单介绍一下队列的特点。队列是一种数据结构，有点类似栈，只是在队列中第一个插入的数据项也会最先被移除，而在栈中，最后插入的数据项最先移除。队列的作用就像电影院前的人们站成的排一样：第一个进入附属的人将最先到达队头买票。最后排队的人最后才能买到票。队列可以实现数据的增加、删除、好了，接下来我将为大家介绍用数组和链表实现自定义队列的方法。  
  
  
一、用数组实现队列

//测试类
    public class ListTest {
       
    	public static void main(String[] args) {
       
    		// 创建一个数组对象
    		Mylist<Integer> list = new Mylist<Integer>();
    		for (int i = 0; i < 10; i++) {
       
    			int s = 10*i;
    			list.add(s);
    
    		}
    		//再添加元素
    		list.add(100);
    		list.modify(10, 100);
    
    		// 取出元素
    		for (int i = 0; i < list.size(); i++) {
       
    			int s = list.get(i);
    			System.out.println(s);
    		}
    	}
    
    }
    
    
    /**
     * 创建一个数组队列
     * 
     * @author 闭耀尧
     * 
     */
    public class Mylist<E> {
       
    
    	// 创建一个空的初始数组
    	Object src[] = new Object[0];
    	Object  stroke[]=new Object[500];
    
    	/**
    	 * 给数组添加元素
    	 * 
    	 * @return
    	 */
    	public void add(E s) {
       
    		Object dest[] = new Object[src.length + 1];
    		// 将初始数组的值赋给新创建的数组中
    		for (int i = 0; i < src.length; i++) {
       
    
    			 dest[i] =  src[i];
    
    		}
    		// 将心数组的值赋给初始数组的最后一个位置
    		    dest[src.length]=s;
    			src = dest;
    
    
    	}
    
    	/**
    	 * 根据下标获取数组中的元素
    	 * 返回所获取的个数
    	 */
    	public E get(int index) {
       
    		E s=(E)src[index];
    
    		return s;
    
    	}
    
    	/**
    	 * 根据下标和元素名修改数组元素
    	 */
    	public void modify(int index,E s) {
       
    		src[index]=s;
    
    	}
    
    	/**
    	 * 根据元素名和下标插入数组
    	 */
    	public void insert(int index, E s) {
       
    		src[index]=s;
    	}
    
    	/**
    	 * 根据元素名和下标删除数组
    	 * 
    	 */
    	public void delete(int index, E s1) {
       
    		E s=(E)src[index];
    
    
    	}
    
    	/**
    	 * 统计数组大小
    	 * 返回所获取的大小
    	 */
    	public int size() {
       
    		return src.length;
    
    	}
    
    
    
    
    }

二、2.用链表实现的队列

//设置节点
    public class LinkNode {
       
    	private Object obj;// 节点内数据对象
    	private LinkNode child;// 对下一个节点的引用
    	private LinkNode parent;// 对下一个节点的引用
    	public LinkNode(Object obj) {
       
    		this.obj = obj;
    	}
    
    	public void setObject(Object obj) {
       
    		this.obj = obj;
    	}
    
    	public Object getObject() {
       
    		return obj;
    	}
    
    	public void setChild(LinkNode child){
       
    		this.child =child ;
    	}
    
    	public LinkNode getChild() {
       
    		return child;
    	}
    	public void setParent(LinkNode parent){
       
    		this.parent =parent ;
    	}
    
    	public LinkNode getParent() {
       
    		return parent;
    	}
    }
    //链表实现队列
    public class NodeQueue {
       
    	public static LinkNode front = null;// 第一个节点
    	public static LinkNode last = null;// 最后一个节点
    
    	/**
    	 * 程序入口
    	 * 
    	 * @param args
    	 */
    	public static void main(String[] args) {
       
    		NodeQueue nq = new NodeQueue();
    		nq.add("aa");
    		nq.add("bb");
    		nq.add("cc");
    		nq.ModiFyLinkNode(0, "更改");
    		// nq.inserLinkNode(2, "插入");
    		nq.deleteLinkNode(2);
    		nq.printLinkNode(front);
    	}
    
    	// 添加节点
    	public void add(Object object) {
       
    		// 创建一个新的节点
    		LinkNode node = new LinkNode(object);
    		if (null == front) {// 如果链表为空
    			front = node;
    			last = front;
    		} else {
       
    			last.setChild(node);
    			node.setParent(last);
    			last = node;
    		}
    	}
    
    	// 根据索引删除元素
    	public void deleteLinkNode(int index) {
       
    		if (this.getLinkLenght() < index || index < 0) {
       
    			throw new RuntimeException("下标越界：" + index + "size:"
    					+ this.getLinkLenght());
    		} else {
       
    			// 得到当前索引位置的节点
    			LinkNode node = this.getLinkNode(index);
    			// 得到父节点
    			LinkNode f_node = node.getParent();
    			// 得到子节点
    			LinkNode c_node = node.getChild();
    			if (f_node == null) {
       
    				front = c_node;
    			} else if (c_node == null) {
       
    				f_node.setChild(null);
    			} else {
       
    				f_node.setChild(c_node);
    				c_node.setParent(f_node);
    
    			}
    		}
    	}
    
    	// 根据索引和对象名修改节点
    	public void ModiFyLinkNode(int index, Object object) {
       
    		if (this.getLinkLenght() < index || index < 0) {
       
    			throw new RuntimeException("下标越界  ： " + index + "  size:  "
    					+ this.getLinkLenght());
    		}
    		LinkNode node = this.getLinkNode(index);
    		node.setObject(object);
    	}
    
    	// 获取节点对象
    	public LinkNode getLinkNode(int index) {
       
    		if (this.getLinkLenght() < index || index < 0) {
       
    			throw new RuntimeException("下标越界：" + index + "size:"
    					+ this.getLinkLenght());
    		} else {
       
    			int num = 0;
    			LinkNode node = front;
    			while (num != index) {
       
    				node = node.getChild();
    				num++;
    			}
    			return node;
    		}
    
    	}
    
    	// 插入节点
    	public void inserLinkNode(int index, Object object) {
       
    		if (this.getLinkLenght() < index || index < 0) {
       
    			throw new RuntimeException("下标越界" + index + "size:"
    					+ this.getLinkLenght());
    		} else {
       
    			// 创建新节点
    			LinkNode newnode = new LinkNode(object);
    			// 得到当前节点
    			LinkNode node = this.getLinkNode(index);
    			if (index == 0) {// 如果链表没有节点
    				front = newnode;
    			} else if (index == this.getLinkLenght()) {// 如果为最后一个节点
    				node.setChild(newnode);
    				newnode.setParent(node);
    			} else {
       
    				// 得到父节点
    				LinkNode fnode = node.getParent();
    				fnode.setChild(newnode);
    				newnode.setChild(node);
    			}
    			// 新的引用关系
    			newnode.setParent(front);
    
    			node.setParent(newnode);
    		}
    	}
    
    	// 获取节点数,返回链表长度
    	public int getLinkLenght() {
       
    		int count = 0;
    		if (front == null) {
       
    			return count;
    		}
    		LinkNode node = front.getChild();
    		while (null != node) {
       
    			count++;
    			node = node.getChild();
    		}
    		return count + 1;
    	}
    
    	// 遍历链表方法
    	public void printLinkNode(LinkNode root) {
       
    		if (null != root) {
       
    			Object data = root.getObject();
    			System.out.println(data);
    			LinkNode temp = root.getChild();
    			printLinkNode(temp);
    		}
    	}
    }