在上一篇博文中通过java实现了队列的连续存储,下面来讨论队列的链式存储,即链队列。
链队列的定义:
队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。
链队列的数据存储形式:
链队列基本运算的实现:
[java]
view plain
copy
package study_02.datastructure.queue; public class LinkQueue<T> { private class Node{ public T data; public Node next; public Node(){} public Node(T data,Node next){ this.data=data; this.next=next; } } private Node front; private Node rear; private int size=0; public LinkQueue(){ Node n=new Node(null,null); n.next=null; front=rear=n; } public void enqueue(T data){ Node s=new Node(data,null); rear.next=s; rear=s; size++; } public T dequeue(){ if(rear==front){ try { throw new Exception("堆栈为空"); } catch (Exception e) { e.printStackTrace(); } return null; }else{ Node p=front.next; T x=p.data; front.next=p.next; if(p.next==null) rear=front; p=null; size--; return x; } } public int size(){ return size; } public boolean isEmpty(){ return size==0; } public String toString() { if(isEmpty()){ return "[]"; }else{ StringBuilder sb = new StringBuilder("["); for(Node current=front.next;current!=null;current=current.next){ sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } public static void main(String[] args) { LinkQueue<Integer> queue=new LinkQueue<Integer>(); queue.enqueue(1); queue.enqueue(2); queue.enqueue(3); queue.enqueue(4); queue.enqueue(5); queue.enqueue(6); System.out.println(queue); System.out.println("出队:"+queue.dequeue()); System.out.println("队列长度="+queue.size()); System.out.println(queue); System.out.println("出队:"+queue.dequeue()); System.out.println("队列长度="+queue.size()); System.out.println(queue); System.out.println("出队:"+queue.dequeue()); System.out.println("队列长度="+queue.size()); System.out.println(queue); } }
输出结果:
[1, 2, 3, 4, 5, 6] 出队:1 队列长度=5 [2, 3, 4, 5, 6] 出队:2 队列长度=4 [3, 4, 5, 6] 出队:3 队列长度=3 [4, 5, 6]
原文地址:http://blog.csdn.net/sky_zhangfan/article/details/3959847
转载请注明原文地址: https://ju.6miu.com/read-1296451.html