基础的数组/链表实现的队列
程序员文章站
2022-03-24 17:28:08
...
上周我们学习了队列的实现，我们可以通过数组或者链表实现队列，队列是对数据的一种存储方式，但是它更优于数组和链表，下面是编写的简单的数组/链表对队列的实现，完善版的还没有完全搞好，先是最基础的实现类：
数组实现的队列：
package lyw.study0411;
/**
* 通过数组来实现队列
* 作用 ：用来实现一个队列类用来存储对象
* @author 刘俞雯 2013-04-11
*/
public class MyQueue {
//定义一个数组内用来存储数据的数组，初始长度为0
private MyStudent[] srcA=new MyStudent[0];
/**
* 用来给数组中添加MyStudent对象
* @param ms MyStudent类的对象名
*/
public void add(MyStudent ms){
//1.新建一个学生类的数组，长度是原数组长度+1
MyStudent[] srcB=new MyStudent[srcA.length+1];
//2.将要加入的对象ms放入新数组的最后一位
srcB[srcA.length]=ms;
//3.把原数组放入新数组
for(int i=0;i<srcA.length;i++){
srcB[i]=srcA[i];
System.out.println("此时加入了："+srcB[i]);
}
//4.指向新建的数组
srcA=srcB;
}
/**
* 用来取得队列中index位置的对象
* @param index 要取得对象的位置
* @return 一个学生对象
*/
public MyStudent get(int index){
MyStudent ms=srcA[index];
return ms;
}
/**
* 得到队列的长度
* @return 队列中元素个数
*/
public int size(){
return srcA.length;
}
public void PrintArray(){
for(int index=0;index<srcA.length;index++)
System.out.println("队列的第"+(index+1)+"个位置的数据是"+srcA[index]);
}
}
这是简单的数组对队列的实现，后面还有编写的简单测试类:
package lyw.study0411;
public class MyStudent {
//定义学生的性命年龄属性
private String name;
private int age;
static MyStudent a1;
static MyStudent a2;
static MyStudent a3;
/**
* 入口主函数
* @param args
*/
public static void main(String[] args) {
//实例化一个队列对象
MyQueue mq=new MyQueue();
//调用它的各种方法
mq.add(a1);
mq.add(a2);
mq.add(a3);
mq.get(2);
System.out.println("2号位置的学生："+mq.get(2));
mq.size();
System.out.println("队列的长度："+mq.size());
mq.PrintArray();
}
//编写构造方法传入属性
public MyStudent(String name,int age){
this.name=name;
this.age=age;
}
public MyStudent(){
}
}
刚开始编写的时候在队列里传入的是学生类，所以只好只能加入学生类的对象，但是上面的代码中加入的学生对象a1等都是空值，以后会通过设置Object类来添加各种不同类型的对象，目前程序正在完善。
通过链表实现的队列：
package lyw.study0416;
/**
* 通过链表实现一个队列类
* 作用 实现一个队列类，用来存储对象
* @author 刘俞雯 2013-04-16
*
*/
public class MyQueue2 {
//根结点
private static MyNode2 root;
//另外的结点用来保存根结点
private MyNode2 other;
//计数器
private int count=1;
//队列的初始长度
private int size=0;
/**
* 向队列中添加元素
* @param mn 向队列中添加的对象
*/
public void add(Object mn){
//开始加入元素
if(root==null){
//实例化一个结点，为根结点
root=new MyNode2();
//把要传入的数据加入根结点
root.date=mn;
// System.out.println("root="+root.date);
//之后把other指向root
other=root;
}else{
//新实例化一个结点类对象node
MyNode2 node=new MyNode2();
//把要传入的数据加入新结点
node.date=mn;
//other的下一个结点为node
other.next=node;
//other指向他的下一个结点
other=other.next;
// System.out.println("other="+other.date);
}
}
/**
* 从队列中取出元素
* @param index 取出元素的位置
* @return 查找位置的结点
*/
public Object get(int index){
//实例化一个新的结点对象ms为需要返回的结点
MyNode2 ms=new MyNode2();
//把other指向root
other=root;
//遍历链表查找对应位置的结点
while(count<=index){
System.out.println("count="+count);
if(count==index){
//需要返回的值为other结点
ms=other;
count ++;
}else{
count++;
other=other.next;
ms=other;
}
}
return ms;
}
/**
* 取得当前队列的长度
* @return 当前链表的长度
*/
public int size(){
//新实例化一个结点node
MyNode2 node=new MyNode2();
other=root;
if(other==null){
return size;
}else{
while(other!=null){
size++;
node=other.next;
other=node;
}
return size;
}
}
/**
* 打印链表中的数据
* @param root 根结点的数据
*/
public void printLink(MyNode2 root,int index){
if(root!=null){
System.out.println("第"+index+++"个位置的数据是："+root.date);
MyNode2 next=root.next;
printLink(next,index++);
}
}
public static void main(String[] args) {
//新建一个队列对象
MyQueue2 mq=new MyQueue2();
//调用mq的各种方法
mq.add(123);
mq.add("刘");
mq.add("刘俞雯");
mq.add("哈哈");
mq.add("哈");
mq.add("You");
mq.add(1267);
MyNode2 mn1=(MyNode2) mq.get(3);
System.out.println("第三位的 ："+mn1.date);
int si=mq.size();
System.out.println("链表的长度为："+si);
int index = 1;
mq.printLink(root,index);
}
}
后面是定义的结点类:
package lyw.study0416;
/**
* 通过链表实现一个队列类
* 作用 实现一个队列类，用来存储对象
* @author 刘俞雯 2013-04-16
*
*/
public class MyQueue2 {
//根结点
private static MyNode2 root;
//另外的结点用来保存根结点
private MyNode2 other;
//计数器
private int count=1;
//队列的初始长度
private int size=0;
/**
* 向队列中添加元素
* @param mn 向队列中添加的对象
*/
public void add(Object mn){
//开始加入元素
if(root==null){
//实例化一个结点，为根结点（由于刚开始的时候在root前又加了MyNode2，相当于新的一个root对象，
//而不是属性中的root，导致无法加入，最后在改进下改正了过来
）
root=new MyNode2();
//把要传入的数据加入根结点
root.date=mn;
// System.out.println("root="+root.date);
//之后把other指向root
other=root;
}else{
//新实例化一个结点类对象node
MyNode2 node=new MyNode2();
//把要传入的数据加入新结点
node.date=mn;
//other的下一个结点为node
other.next=node;
//other指向他的下一个结点
other=other.next;
// System.out.println("other="+other.date);
}
}
/**
* 从队列中取出元素
* @param index 取出元素的位置
* @return 查找位置的结点
*/
public Object get(int index){
//实例化一个新的结点对象ms为需要返回的结点
MyNode2 ms=new MyNode2();
//把other指向root
other=root;
//遍历链表查找对应位置的结点
while(count<=index){
System.out.println("count="+count);
if(count==index){
//需要返回的值为other结点
ms=other;
/**
*开始在这一步没加count++，导致当到了索引的位置之后，
*因为while中的count<=index也一直成立，形成了死循环，
*导致电脑卡机。。。。。。-_- !。。之后经过调试才改了过来o(∩_∩)o
*/
count ++;
}else{
count++;
other=other.next;
ms=other;
}
}
return ms;
}
/**
* 取得当前队列的长度
* @return 当前链表的长度
*/
public int size(){
//新实例化一个结点node
MyNode2 node=new MyNode2();
other=root;
if(other==null){
return size;
}else{
while(other!=null){
size++;
node=other.next;
other=node;
}
return size;
}
}
/**
* 打印链表中的数据
* @param root 根结点的数据
*/
public void printLink(MyNode2 root,int index){
if(root!=null){
System.out.println("第"+index+++"个位置的数据是："+root.date);
MyNode2 next=root.next;
printLink(next,index++);
}
}
public static void main(String[] args) {
//新建一个队列对象
MyQueue2 mq=new MyQueue2();
//调用mq的各种方法
mq.add(123);
mq.add("刘");
mq.add("刘俞雯");
mq.add("哈哈");
mq.add("哈");
mq.add("You");
mq.add(1267);
MyNode2 mn1=(MyNode2) mq.get(3);
System.out.println("第三位的 ："+mn1.date);
int si=mq.size();
System.out.println("链表的长度为："+si);
int index = 1;
mq.printLink(root,index);
}
}
下面是程序执行后的结果：
count=1
count=2
count=3
第三位的 ：刘俞雯
链表的长度为：7
第1个位置的数据是：123
第2个位置的数据是：刘
第3个位置的数据是：刘俞雯
第4个位置的数据是：哈哈
第5个位置的数据是：哈
第6个位置的数据是：You
第7个位置的数据是：1267
对于数组或者链表实现的队列，刚开始做的时候还有好多细节方面的错误，导致刚开始测试的时候的初的结果不是运行不起来要么就是运行结果不正确，之后通过一步步的测试，发现并且改正下，得到了最终的程序，而这只是最简单的初始队列的实现，之后还会做出有插入删除等的队列，还有用双向链表实现的队列。
上一篇： 并查集总结
下一篇： 队列（数组实现和链表实现）