1.3.38删除第k个元素。实现一个类并支持表1.3.12中的API:

表1.3.12泛型一般队列的API

public class GeneralizedQueue<Item>

    GeneralizedQueue()//创建一条空队列

    boolean isEmpty()//队列是否为空

    void insert(Item x)//添加一个元素

    Item delete(int k)//删除并返回最早插入的第k个元素

用链表实现该数据类型。注意：我们在第3章中介绍的算法和数据结构可以保证insert()和delete()的实现所需的运行时间和和队列中的元素数量成对数关系-请参见练习3.5.27。

答:

public class GeneralizedQueue<Item>

{

    private class Node

    {

        Item item;

        Node next;

    }

    private Node first=new Node();

    private Node last=new Node();

    private int N=0;

   

    public GeneralizedQueue()

    {}

   

    public boolean isEmpty()

    {return N==0;}

   

   

    public void insert(Item x)

    {

        Node oldlast=last;

        last=new Node();

        last.item=x;

        if(isEmpty())  

            first=last;

        else

            oldlast.next=last;

        N++;

    }

   

    public Item delete(int k)

    {

        if(k<1 || k>N || N==0) return null;

        int i=1;

        Node current=new Node();

        current.next=first;

        while(i!=k)

        {

           current=current.next;

           i++;

        }

       //

       Item item;

       if(k==1 && N==1)

          {

             item=current.next.item;

             first=current.next.next;

             last=first;

         }

       else if(k==1 && N>1)

         {

           item=current.next.item;

           first=current.next.next;

          

         }

         else if(k==N && N>1)

         {

             item=current.next.item;

             last=current;

             last.next=null;

         }

         else

         {

            item=current.next.item;

            current.next=current.next.next;

         }

         N--;

        return item;

    }

  

    public void showAll()

    {

        Node current=first;

        while(current!=null)

        {

            StdOut.print(current.item+" ");

            current=current.next;

        }

    }

   

    public static void  main(String[] args)

    {

        int N=Integer.parseInt(args[0]);

        int k=Integer.parseInt(args[1]);

        GeneralizedQueue<Integer> gq=new GeneralizedQueue<Integer>();

        for(int i=0;i<N;i++)

            gq.insert(i);

        //

        StdOut.print("the k is "+k +" the value is "  +gq.delete(k));

        StdOut.printf("\nQueue left elements is:\n");

        gq.showAll();

    }

}