找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ JAVA开发技术 ] 【守望者 j2se】Queue结构模拟

2014-10-12 15:19| 发布者: zhouy | 查看: 976 | 收藏

摘要: 接着我们介绍queue数据结构,我们通过对简单的数据结构的模拟后是不是感觉自己的内功提高的呀,那有人会问什么是内功呢?其实我觉得就是一个思维意识,换句话来说就是你站得更好的。这样的话,我觉得我们的工作更加有 ...

接着我们介绍queue数据结构,我们通过对简单的数据结构的模拟后是不是感觉自己的内功提高的呀,那有人会问什么是内功呢?其实我觉得就是一个思维意识,换句话来说就是你站得更好的。这样的话,我觉得我们的工作更加有意义,我们以分享,交流,责任为目标学习分享技术.


1.基础的节点对象Node
  
public class Node {
private Object data;// 存放值
private Node next;// 下一个节点

public   Node(){}


public Node(Object data) {// 构造值为data的结点
  this(data,null);
}
public Node(Object data, Node next) {
  this.data = data;
  this.next = next;
}
public Object getData() {
  return data;
}
public void setData(Object data) {
  this.data = data;
}
public Node getNext() {
  return next;
}
public void setNext(Node next) {
  this.next = next;
}
}


2.Queue操作接口

public interface IQueue {

public void clear(); // 将一个已经存在的队列置成空
public boolean isEmpty(); // 测试队列是否为空
public int length();// 求队列中的数据元素个数并由函数返回其值
public Object peek();// 查看队列的头而不移除它,返回队列顶对象,如果此队列为空,则返回 null 
public Object poll();// 移除队列的头并作为此函数的值返回该对象,如果此队列为空,则返回 null 
public void offer(Object o) throws Exception;// 把指定的元素插入队列
public void display();// 打印函数,打印所有队列中的元素(队列头到队列尾)

}


3.链队列类(FIFO)

public class LinkQueue  implements  IQueue{
  
    private  Node  front;// 队头的引用
    private  Node  rear;// 队尾的引用,指向队尾元素

    public   LinkQueue()
    {
     this.front=null;
     this.rear=null;
     
    }

//清空队列
public void clear() {
  
   this.front=null;
   this.rear=null;
   
}
    //展示数据
public void display() {
  
  if(!this.isEmpty())
  {
       Node  p=front;
       while(p!=null)//未到尾部
       {
        System.out.println(p.getData()+"  ");
        p=p.getNext();
       }
  }
  else
  {
   System.out.println("此队列为空!!");
  }
}
   
//头指针指向空说明队列为空
public boolean isEmpty() {
  return this.front==null;
}
    
     //返回链表的长度
public int length() {
  
  Node  p=front;
  int   length=0;
  while(p!=null)
  {
   p=p.getNext();
   length++;
  }
  return length;
}
  
//添加元素(添加到队列最后)
public void offer(Object o) throws Exception {
  //在尾部压入元素
  Node   s=new  Node(o);
  Node  p=front;
  if(p!=null)//判断是否是空队列
  {
     this.rear.setNext(s);
     this.rear=s;
  }
  else//空队列的情况
  {
    this.front=s;
    this.rear=s;
  }
}


//查看队列的首项数据
public Object peek() {
  
  if(this.front!=null)//判断是否为空队列
  {
    return  this.front.getData();
  }
  else
  {
       return null;
  }
}

//取出首对象并移除
public Object poll() {
  
    //首先取出对象
     Node   p=front;
     if(p!=null)
     {
         //front指向下一个节点
         front=p.getNext();
      return  p.getData(); 
     }
     else
     {
      return null;
     }
}
public Node getFront() {
  return front;
}
public void setFront(Node front) {
  this.front = front;
}
public Node getRear() {
  return rear;
}
public void setRear(Node rear) {
  this.rear = rear;
}
}


4.循环顺序队列
public class CircleSqQueue  implements IQueue {
    
private Object[] queueElem; // 队列存储空间
private int front;// 队首的引用,若队列不空,指向队首元素
private int rear;// 队尾的引用,若队列不空,指向队尾元素的下一个位置

// 循环队列类的构造函数
public CircleSqQueue(int maxSize) {
  front=rear=0;// 队头、队尾初始化为0
  queueElem = new Object[maxSize];// 为队列分配maxSize个存储单元
}


// 将一个已经存在的队列置成空
public void clear() {
  front = rear = 0;
}
// 测试队列是否为空
public boolean isEmpty() {
  return front == rear;
}


// 求队列中的数据元素个数并由函数返回其值
public int length() {
  return (rear - front + queueElem.length) % queueElem.length;
}

// 把指定的元素插入队列
public void offer(Object x) throws Exception {
  if ((rear + 1) % queueElem.length == front)// 队列满
   throw new Exception("队列已满");// 输出异常
  else {// 队列未满
   queueElem[rear] = x;// x赋给队尾元素
   rear = (rear + 1) % queueElem.length;// 修改队尾指针
  }
}

// 查看队列的头而不移除它,返回队列顶对象,如果此队列为空,则返回 null
public Object peek() {
  if (front == rear)// 队列为空
   return null;
  else
   return queueElem[front]; // 返回队首元素
}


// 移除队列的头并作为此函数的值返回该对象,如果此队列为空,则返回 null
public Object poll() {
  if (front == rear)// 队列为空
   return null;
  else {
   Object t = queueElem[front];// 取出队首元素
   front = (front + 1) % queueElem.length;// 更改队首的位置
   return t;// 返回队首元素
  }
}


// 打印函数,打印所有队列中的元素(队首到队尾)
public void display() {
  if (!isEmpty()) {
   for (int i = front; i != rear; i = (i + 1) % queueElem.length)
    // 从队首到队尾
    System.out.println(queueElem.toString() + " ");
  } else {
   System.out.println("此队列为空");
  }
}
}



小结:目前像个大家一个自己练习的题目,如何实现优先值队列呢?我提供如下参考答案:


1.基础结构对象PriorityQData
  public class PriorityQData {

private Object elem;// 结点的值
private int priority;// 结点的优先级
// 构造函数
public PriorityQData(Object elem, int priority) {
  this.elem = elem;
  this.priority = priority;
}
public Object getElem() {
  return elem;
}
public int getPriority() {
  return priority;
}
public void setElem(Object elem) {
  this.elem = elem;
}
public void setPriority(int priority) {
  this.priority = priority;
}
}
//实现
public class PriorityQueue  implements  IQueue{

private Node front;// 队头的引用
private Node rear;// 队尾的引用,指向队尾元素
// 优先队列类的构造函数
public PriorityQueue() {
  front = rear = null;
}
// 将一个已经存在的队列置成空
public void clear() {
  front = rear = null;
}
// 测试队列是否为空
public boolean isEmpty() {
  return front == null;
}
// 求队列中的数据元素个数并由函数返回其值
public int length() {
  
  Node p = front;
  int length = 0;// 队列的长度
  while (p != null) {// 一直查找到队尾
   p = p.getNext();
   length++;
  }
  
  return length;
}
// 把指定的元素插入队列
public void offer(Object o) {
  
  PriorityQData pn = (PriorityQData) o;
  Node s = new Node(pn); // 构造一个新的结点
  if (front == null) // 队列为空
   front = rear = s;// 修改队列头尾结点
  
  else {
   Node p = front,q = front;
   while (p != null &&  pn.getPriority() >= ((PriorityQData) p.getData()).getPriority()) {// 新结点的值与队列结点中的元素的值相比较
    q = p;
    p = p.getNext();
   }
   if (p == null) {// p为空,表示遍历到了队列尾部
    rear.setNext(s);// 在队列中加入新结点
    rear = s;// 修改队尾指针
   } else if (p == front) {// p的优先级大于头结点的优先级
    s.setNext(front);
    front = s;// 修改头结点的值
   } else {// 新结点加入队列中部
    q.setNext(s);
    s.setNext(p);
   }
  }
}
// 查看队列的头而不移除它,返回队列顶对象,如果此队列为空,则返回 null
public Object peek() {
  if (front == null)// 队列为空
   return null;
  else
   // 返回队列头结点的值
   return front.getData();
}
// 移除队列的头并作为此函数的值返回该对象,如果此队列为空,则返回 null
public Object poll() {
  if (front == null)// 队列为空
   return null;
  else {// 返回队列头结点的值,并修改队列头指针
   Node p = front;
   front = p.getNext();
   return p.getData();
  }
}
// 打印函数,打印所有队列中的元素(队列头到队列尾)
public void display() {
  if (!isEmpty()) {
   Node p = front;
   while (p != null) {// 从对头到队尾
    PriorityQData q = (PriorityQData) p.getData();
    System.out.println(q.getElem() + "      " + q.getPriority());// 打印
    p = p.getNext();
   }
  } else {
   System.out.println("此队列为空");// 打印
  }
}
}

推荐阅读

【守望者  j2se】ConcurrentHashMap原理分析
【守望者 j2se】ConcurrentHashMap原
集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据
【守望者  j2se】双向链表模拟
【守望者 j2se】双向链表模拟
我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.1.基础结构
【守望者 高并发】现有高并发WEB服务器 lighttpd Apache Nginx比较
【守望者 高并发】现有高并发WEB服务器
lighttpd网络服务器基于的Lighttpd的网络服务器具有这样的特点:占用内存资源
【守望者 高并发】C10K/C500K与I/O框架
【守望者 高并发】C10K/C500K与I/O框架
C10K、C/500K问题C10K 的意思是10000并发请求,C500K意思是500 000并发请求,
【守望者  JMM】理解volatile内存语义
【守望者 JMM】理解volatile内存语义
理解volatile变量对写多线程程序还是很有帮助的,这样就会避免一上来就是syn这
【守望者  j2se】虚拟机各部分内存溢出情况
【守望者 j2se】虚拟机各部分内存溢出
通过简单的小例子程序,演示java虚拟机各部分内存溢出情况:(1).java堆溢出:
【守望者 高并发】使用CAS实现高效并发处理
【守望者 高并发】使用CAS实现高效并发
守望者:在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较
【守望者 大数据】Mahout学习路线图
【守望者 大数据】Mahout学习路线图
Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Z
【守望者  j2se】吃透 java I/O 工作机制-1
【守望者 j2se】吃透 java I/O 工作机
I/O 问题可以说是当今互联网 Web 应用中所面临的主要问题之一,因为当前在这
【守望者 j2se】ConcurrentMap之putIfAbsent(key,value)用法讨论
【守望者 j2se】ConcurrentMap之putIfA
先看一段代码:public class Locale { private final static MapString, Lo
【守望者  javascript】判断IE浏览器世界上最短的代码
【守望者 javascript】判断IE浏览器世
最短的IE判定var ie=!-分析以前最短的IE判定借助于IE不支持垂直制表符的特性
【守望者 大数据】机器学习已成为大数据的基石
【守望者 大数据】机器学习已成为大数
机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、
【守望者  j2se】多线程与并发知识点总结
【守望者 j2se】多线程与并发知识点总
对于多线程和并发编程这个比较大的技术模块,我们会整理一些帖子方便知识点的
【守望者  j2se】二叉树模拟
【守望者 j2se】二叉树模拟
接着我们就要写一个比较复杂的数据结构的,但是这个数据结构是很重要的,假如
【守望者 SRS  】SRS 源代码分析笔记(0.9.194)-分析服务器对端口的监听 ...
【守望者 SRS 】SRS 源代码分析笔记(
第一部分 分析服务器对端口的监听 端口监听与初始化(一)全局变量_srs_confi

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved