linkqueue.java~1~

源程序（包括最初的版本

package queue;
/*用在了图的求两个顶点之间的一条路径长度最短的路径中
1) 将链队列的结点改为“双链”结点。即
结点中包含next 和prior两个指针;
2) 修改入队列的操作。插入新的队尾结点时，
令其prior域的指针指向刚刚出队列的结点，即
当前的队头指针所指结点;
3) 修改出队列的操作。出队列时，仅移动队
头指针，而不将队头结点从链表中删除。
*/
public class LinkQueue implements Queue
{
    QueueNode front;
    QueueNode rear;
    int size;

    public LinkQueue(int initialCapacity)
    {
        front=rear;
       // front.next=rear.next=null;
    }

    public LinkQueue()
        {this(0);}

    public boolean isEmpty()
    {return size==0;}
    public Object getFrontElement()
    {return front.element;}
    public Object getRearElement()////////?
    {return rear.element;}
    public void put(Object theObject)
    {
        QueueNode p = new QueueNode(theObject,front,null);
        //p.element = theObject;
       // p.next = null;
        //p.prior = front;
        if(front==null)
            front=p;
        else
            rear.next = p;
        rear = p;
        size++;
    }
    public Object remove()
    {
        Object removeElement = front.element;
        front = front.next;
        //Object removeElement = front.element;
        size--;
        return removeElement;
    }
    public String toString()
         {
            StringBuffer s = new StringBuffer("[");

            // 放元素到缓冲区buffer
            QueueNode p = rear;
            while(p != null)
            {
               if (p.element == null)
                  s.append("null, ");
               else
                  s.append(p.element.toString() + ", ");
               p = p.prior;
            }
            if (size > 0)
               s.delete(s.length() - 2, s.length());  // 去掉最后一个", "
            s.append("]");

            // 返回创建的等值串
            return new String(s);
         }
         /*
         public static void main(String [] args)
              {
                 // 测试缺省的构造函数
                 LinkQueue x = new LinkQueue();

                 // 测试元素个数size
        //  System.out.println("Initial size is " + queue.length);

          // 测试判空isEmpty
          if (x.isEmpty())
             System.out.println("The queue is empty");
          else System.out.println("The queue is not empty");

          // 测试插入add
          x.put(new Integer(2));
          x.put(new Integer(6));
          x.put(new Integer(1));
          x.put(new Integer(4));
         // x.put(new Integer(17));


          // 测试字符串输出toString
          System.out.println("The queue is " + x);
          System.out.println("List size is " + x.size);//?????
          System.out.println("The front is "+x.getFrontElement());
          System.out.println("The rear is "+x.getRearElement());

          System.out.println(x.remove() + " removed");
          System.out.println("The queue is " + x);
          System.out.println("List size is " + x.size);//???
          System.out.println("The front is "+x.getFrontElement());
          System.out.println("The rear is "+x.getRearElement());

          System.out.println(x.remove() + " removed");
          System.out.println("The queue is " + x);
          System.out.println("List size is " + x.size);//???
          System.out.println("The front is "+x.getFrontElement());
          System.out.println("The rear is "+x.getRearElement());

          x.put(new Integer(17));
          System.out.println("The queue is " + x);
          System.out.println("List size is " + x.size);//???
          System.out.println("The front is "+x.getFrontElement());
          System.out.println("The rear is "+x.getRearElement());

          System.out.println(x.remove() + " removed");
          System.out.println("List size is " + x.size);//???
          System.out.println("The queue is " + x);
          System.out.println(x.remove() + " removed");
          System.out.println("List size is " + x.size);//???
          System.out.println("The queue is " + x);
          //System.out.println(x.remove() + " removed");
          //System.out.println("List size is " + x.size);//???
          //System.out.println("The queue is " + x);
          //System.out.println("List size is " + x.size);//???

       }

*/
}