首页 > 代码库 > 浅谈Java中的数据结构（队列）
浅谈Java中的数据结构（队列）
借助Java语言用数组和链表实现队列
队列 (Queue)
一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时，称为空队列。
Part 1 用链表实现队列
QueueNode类是用来表示一个链表节点的类，QueueLinked是链表实现的队列，
其中front是对首指针，rear是队尾指针，队首出队，队尾入队。
1 package test; 2 /** 3 * 链表节点类 4 */ 5 class QueueNode { 6 Object data; // 节点存储的数据 7 QueueNode next; // 指向下个节点的指针 8 9 public QueueNode() {10 this(null, null);11 }12 public QueueNode(Object data) {13 this(data, null);14 }15 public QueueNode(Object data, QueueNode next) {16 this.data =http://www.mamicode.com/ data;17 this.next = next;18 }19 }20 /**21 * 单向链表实现的队列22 */23 public class Manager {24 QueueNode front; // 队首指针25 QueueNode rear; // 队尾指针26 27 public Manager() {28 this.rear = null;29 this.front = null;30 }31 /**32 * 将一个对象追加到队列的尾部33 */34 public void enqueue(Object obj) {35 //如果队列是空的36 if (rear == null && front == null) {37 rear = new QueueNode(obj);38 front = rear;39 } else {40 QueueNode node = new QueueNode(obj);41 rear.next = node;42 rear = rear.next;43 }44 }45 /**46 * 队首对象出队47 * @return 出队的对象，队列空时返回null48 */49 public Object dequeue() {50 //如果队列空51 if (front == null) {52 return null;53 }54 //如果队列中只剩下一个节点55 if (front == rear && rear != null) {56 QueueNode node = front;57 rear = null;58 front = null;59 return node.data;60 }61 Object obj = front.data;62 front = front.next;63 return obj;64 }65 66 public static void main(String[] args) {67 //遍历输出68 Manager q = new Manager();69 q.enqueue("。");70 q.enqueue("。。");71 q.enqueue("。。。");72 q.enqueue("。。。。");73 for (int i = 0; i < 4; i++) {74 System.out.println(q.dequeue());75 }76 }77 }
Part 2 用数组实现队列
1 package test; 2 /** 3 * 顺序存储结构队列 4 */ 5 public class Manager { 6 private static final int MAX_SIZE = 100; 7 private Object[] queue; //队列 8 private int front; //头指针 9 private int rear; //尾指针10 private int length; //队列初始化长度 11 //初始化队列12 private void init(){13 queue = new Object[this.length + 1]; 14 front = rear = 0;15 }16 //入队17 public void put(Object object) throws Exception{18 if(isFull()){19 throw new Exception("入队失败!队列已满!");20 }21 queue[rear] = object;22 rear = (rear + 1) % queue.length;23 }24 //出队25 public Object get() throws Exception{26 if(isEmpey()){27 throw new Exception("出队失败!队列为空!");28 }29 Object object = queue[front];30 queue[front] = null; //释放对象31 front = (front + 1) % queue.length;32 return object;33 }34 //清空队列35 public void clear(){36 queue = null;37 queue = new Object[this.length];38 }39 //获得队列当前大小40 public int size(){41 return (rear - front + queue.length ) % queue.length;42 }43 //判断队列是否已满44 public boolean isFull(){45 return (rear + 1) % queue.length == front;46 }47 //判断队列是否为空48 public boolean isEmpey(){49 return front == rear;50 }51 public Manager(){52 this.length = MAX_SIZE;53 init();54 }55 public Manager(int length){56 this.length = length;57 init();58 }59 60 public static void main(String[] args) {61 Manager queue = new Manager(5);62 char[] data = http://www.mamicode.com/new char[]{‘1‘,‘2‘,‘3‘,‘4‘,‘5‘};63 try {64 for (int i = 0; i < data.length; i++) {65 System.out.println("入队数据:" + data[i]);66 queue.put(data[i]);67 }68 System.out.println("队大小:" + queue.size());69 System.out.println("---------------------");70 while(!queue.isEmpey()){71 System.out.println("出队数据:" + queue.get());72 }73 System.out.println("队空否?\t" + queue.isEmpey());74 }catch (Exception e) {75 e.printStackTrace();76 }77 }78 }
浅谈Java中的数据结构（队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。