myqueue.java

来自「用分支界限法解决的几个问题:包括0-1背包问题,最大团问题,电路布线问题,最大装」· Java 代码 · 共 112 行

/*
 * Queue.java
 *
 * Created on 2006年4月14日, 下午12:40
 *
 * To change this template, choose Tools | Options and locate the template under
 * the Source Creation and Management node. Right-click the template and choose
 * Open. You can then make changes to the template in the Source Editor.
 */

/**
 *
 * @author michael
 */
package test;
public class MyQueue {
    
    /** Creates a new instance of Queue */
    int NodeCount=0;
    QueueNode front,rear;
    public MyQueue() {
        front=null;
        rear=null;
    }
    public boolean enQueue(Object Value,int key){
        QueueNode prt=front;
        front=new QueueNode();
        front.Value=Value;
        front.key=key;
        front.last=null;
        front.next=prt;        
        if (NodeCount<=0 && front!=null)rear=front;
        else prt.last=front;

        NodeCount++;
        //if (front.Value!=null) System.out.print(((Qnode)front.Value).weight);
       // QSort(0, NodeCount-1);
        return true;
    }
    public Object deQueue(){
        QueueNode prt=front;
        if (NodeCount==0){
            front=rear=null;
            return null;
        }
        else{
             prt=rear;
             rear=rear.last;
             //rear.next=null;
             NodeCount--;
             //System.out.println(NodeCount);
             return prt.Value;   
        }
    }
    public void print(){
        QueueNode prt=front;
        for (int i=0;i<NodeCount;i++){System.out.print(((Qnode)prt.Value).weight+" ");prt=prt.next;}
    }
    public boolean isEmpty(){  //队为空
        if (NodeCount<=0) return true;
        else return false;
    }
  
    private boolean QSort(int nLow,int nHigh)
    //快速排序的递归算法
    {

            int nPriovLoc;
            //if (nLow>=nHigh && nHigh<2) return false;
            if (nLow<nHigh)
            {	
                    //nPriovLoc=Partition(nLow,nHigh);
                    //QSort(nPriovLoc+1,nHigh);
                    //QSort(nLow,nPriovLoc-1);
            }
            QueueNode prt=front;
            while(prt.next!=rear && prt.next!=null) {prt=prt.next;System.out.print(prt.key+" ");}
            System.out.println(" ");
            return true;
    }

    private int Partition(int nLow, int nHigh)
    {
            int Privokey=getNode(nLow).key;
            QueueNode prt;
                    while (nLow<nHigh)
            {	
                    while (nLow<nHigh && getNode(nHigh).key>=Privokey) nHigh--;
                     if (nLow>0) getNode(nLow-1).next=getNode(nHigh-1).next;
                    while (nLow<nHigh && getNode(nLow).key<=Privokey) nLow++;
                     if (nLow>0)  getNode(nHigh-1).next=getNode(nLow-1).next;
            }
            getNode(nLow).key=Privokey;
            return nLow;
    }
    QueueNode getNode(int index){
        QueueNode prt=front;
        int i=0;
        while (i++!=index && prt.next!=null){prt=prt.next;}
        return prt;
    }
    class QueueNode{
        Object Value;
        int key;
        QueueNode next;
        QueueNode last;
        public QueueNode(){this.next=null;}
        public Object getValue(){return Value;}
        public int getKey(){return key;}
    }

}