1.3.33Deque。一个双向队列（或者称为deque)和栈或队列类似，但它同时支持在两端添加或删除元素。Deque能够存储一组元素并支持表1.3.9中的API:

表1.3.9泛型双向队列的API

public class Deque<Item> implements Iterable<Item>

    Deque()//创建空双向队列

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

    int size()//双向队列中的元素数量

    void pushLeft(Item item)//向左端添加一个新元素

    void pushRight(Item item)//向右端添加一个新元素

    Item popLeft() 从左端删除一个元素

    Item popRight()从右端删除一个元素

编写一个使用双向链表实现这份API的Deque类。

答:

import java.util.Iterator;

public class Deque<Item> implements Iterable<Item>

{

   private class Node

    {

        Item item;

        Node prev;

        Node next;

    }

   

   private int N;

   private Node left;

   private Node right;

  

    public Deque()

    {

        left=null;

        right=null;

        N=0;

    }

   

    public boolean isEmpty()

    {return N==0;}

   

    public int size()

    {return N;}

   

    public void pushLeft(Item item)

    {

        Node oldLeft=left;

        left=new Node();

        left.item=item;

        left.prev=null;

        left.next=oldLeft;

      

        if(isEmpty())

            right=left;

        else

             oldLeft.prev=left;

        N++;

    }

   

    public void pushRight(Item item)

    {

        Node oldRight=right;

        right=new Node();

        right.item=item;

        right.prev=oldRight;

        right.next=null;

        if(isEmpty())

            left=right;

        else

            oldRight.next=right;

           

        N++;

    }

   

    public Item popLeft()

    {

        Item item;

       if(size()==0)

       {

           item=null;

       }

       else if(size()==1)

       {

           item=left.item;

           left=null;

           right=null;

           N--;

       }

       else

       {

           Node oldLeft=left;

           left=left.next;

           left.prev=null;

           oldLeft.next=null;

           item=oldLeft.item;

           N--;

       }

        return item;

    }

   

    public Item popRight()

    {

        Item item;

        if(size()==0)

        {

            item=null;

        }

        else if(size()==1)

        {

            item=right.item;

            left=null;

            right=null;

            N--;

        }

        else

        {

            Node oldRight=right;

            right=right.prev;

            oldRight.prev=null;

            right.next=null;

            item=oldRight.item;

            N--;

         }

        return item;

    }

 

    public Iterator<Item> iterator()  {return new ListIterator();}

   

    private class ListIterator implements Iterator<Item>

    {

        private Node current=left;

        public boolean hasNext(){return current!=null;}

        public void remove(){}

        public Item next()

        {

            Item item=current.item;

            current=current.next;

            return item;

        }//end next

      }//end class ListIterator

   

    public static void main(String[] args)

    {

        Deque<String> q=new Deque<String>();

        In in1=new In(args[0]);

        In in2=new In(args[0]);

        In in3=new In(args[0]);

        In in4=new In(args[0]);

        //pushLeft and popLeft

   

        StdOut.printf("\n---pushLeft and popLeft---\n");

        while(!in1.isEmpty())

        {

            String item=in1.readString();

            q.pushLeft(item);

        }

         while(!q.isEmpty())

        {

        StdOut.print(q.popLeft()+" ");

        }

   

        //pushLeft and popRight

   

        StdOut.printf("\n---pushLeft and popRight---\n");

        while(!in2.isEmpty())

        {

            String item=in2.readString();

            q.pushLeft(item);

        }

        while(!q.isEmpty())

        {

        StdOut.print(q.popRight()+" ");

        }

    

        //pushRight and popLeft

        StdOut.printf("\n---pushRight and popLeft---\n");

        while(!in3.isEmpty())

        {

            String item=in3.readString();

            q.pushRight(item);

        }

        while(!q.isEmpty())

        {

        StdOut.print(q.popLeft()+" ");

        }

     

        //pushRight and popRight

        StdOut.printf("\n---pushRight and popRight---\n");

        while(!in4.isEmpty())

        {

            String item=in4.readString();

            q.pushRight(item);

        }

        while(!q.isEmpty())

        {

        StdOut.print(q.popRight()+" ");

        }

 

    }

}