Java实现队列结构(数据结构)

先给出一些应用队列的场景

　　1):当作业被送到打印机的时候，就可以按到达的顺序排起来，因此每一份作业是队列的节点。

　　2):售票口的人买票的顺序的按照先来先买的顺序售票。

　　3):当所有的终端被占用，由于资源有限，来访请求需要放在一个队列中等候。

队列是先进先出的!

　　我们设置一个叫做LinkQueue<T>的泛型集合类，该类里面有 Node 作为内部类（作为节点用），它包含了泛型元素和下一个node节点的指向next（Node）。

在Linkqueue的里面设置队列头指针 front和队列尾指针rear，长度size=0；我们先设置一个构造器LinkQueue()，用来初始化这两个指针节点，当然，刚开始初始化的

时候 这两个指针仅仅是一个节点而已，里面的data是空的，我们还让这两个指针相等。

 

 //链的数据结构  
    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;

 

 

 

　　

public LinkQueue(){  
        Node n=new Node(null,null);  
        n.next=null;  
        front=rear=n;  
    }  

 

 

 

　　当我们向该队列添加元素的时候，就会生成一个新的节点，其data就是你要加的元素，（当添加一个节点时，该节点就是队尾指针指向的最后的节点，一直排在最后），所以

队尾rear.next=newNode(“新创建的节点”).这是第一个节点，也是最后一个节点，所以front.next=newNode.然后我们再让rear=newNode（不断更新）。

　　

 public void enqueue(T data){  
        //创建一个节点  
        Node s=new Node(data,null);  
        //将队尾指针指向新加入的节点，将s节点插入队尾  
        rear.next=s;  
        rear=s;  
        size++;  
    }  

 

　　当队列出队的时候，还记得我们有一个Node是front.next=newNode 吗？这就是第一个节点。先暂且把它叫做p，所以p.next=第二个节点，这时我们再把front.next=p.next;这样头指针就指向了第二个元素(每一次调用的时候队列头指针指会发生变化)。

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;  
            //判断出队列长度是否为1  
            if(p.next==null)  
                rear=front;  
            //删除节点  
            p=null;  
            size--;  
            return  x;  
        }  
    }  

到此为止，队列的核心操作就完毕了，剩下的比如说size(长度)，isEmpty(是否为空)，就不在说了。(因为太简单了！)

具体源码如下：

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;  
    }  
      
    /** 
     * 队列入队算法 
     * @param data 
     * @author WWX 
     */  
    public void enqueue(T data){  
        //创建一个节点  
        Node s=new Node(data,null);  
        //将队尾指针指向新加入的节点，将s节点插入队尾  
        rear.next=s;  
        rear=s;  
        size++;  
    }  
      
    /** 
     * 队列出队算法 
     * @return 
     * @author WWX 
     */  
    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;  
            //判断出队列长度是否为1  
            if(p.next==null)  
                rear=front;  
            //删除节点  
            p=null;  
            size--;  
            return  x;  
        }  
    }  
      
    /** 
     * 队列长队 
     * @return 
     * @author WWX 
     */  
    public int size(){  
        return size;  
    }  
      
    /** 
     * 判断队列是否为空 
     * @return 
     * @author WWX 
     */  
    public  boolean isEmpty(){  
        return  size==0;  
          
    }  
      
      }

 另：我曾经看过一本JavaScript数据结构书，里面讲的浅显易懂，很适合前端搞js开发的让人理解的更为深入，在此给予推荐。<<数据结构与算法JavaScript描述>>

 

>>