Java 编程 - 圆形数组

Java Programming - Circular Array

提问by Hr0419

Can anyone tell me where I did wrong? My Queue class is working like a Stack, not a Queue. If I enqueue 1, 2, and 3 (in that order) and then dequeue, it removes the 3, not the 1.

谁能告诉我我哪里做错了？我的 Queue 类像堆栈一样工作，而不是队列。如果我将 1、2 和 3（按此顺序）入队，然后出队，它将删除 3，而不是 1。

Thank you in advance! I am not sure where I did wrong!

先感谢您！我不知道我哪里做错了！

Here is my code:

这是我的代码：

import java.util.NoSuchElementException;

public class Queue implements QueueADT
{
   private int front = 0;
   private int back = 0;
   private int [] a;
   private int size = 10;


   public Queue(){
       a = new int [10];
   }

   public Queue(int size){
       a = new int [size];
       this.size = size;
   }


   //enqueue - adds an element to the back of the queue
   public void enqueue(int element){

       if(((back+1) - front) == -1 || ((back+1) - front) == (a.length - 1))
           resizeArray();

       if (back == a.length - 1)
           back = 0;

           a[back++] = element;


   }

   //dequeue - removes and returns the element from the
   //front of the queue
   public int dequeue(){
       if(isEmpty())
           throw new NoSuchElementException("Dequeue: Queue is empty");


       if (front < back){
       front ++;
       return a[front-1];
       }

       else if (front > back){
       front--;
       return a[front++];  
       }

       return 1;
       }


   //peek - returns but does not remove the element from
   //the front of the queue
   public int peek(){
       if(isEmpty())
   throw new NoSuchElementException("Peek: Queue is empty");
   return a[front];
   }

   //isEmpty - determines if the queue is empty or not
   public boolean isEmpty(){
       return size() == 0;

   }

   private void resizeArray()
   {
       //double the size of the array
       int[] newA = new int[a.length * 2];
       int x = 0;
       while(x < size - 1){
           newA[x] = dequeue();

           x++;
       }
       size = size *2;
       front = 0;
       back = x;
       a = newA;

       }



   //size - returns the number of elements in our Queue
   public int size(){

       if (front > back ){
       return size - (front - (back + 1));}

       return back - front + 1;}



   //toString - returns a String representation of our Queue
   public String toString(){

       if(isEmpty()) {
throw new NoSuchElementException("Queue is empty");
       }

       {
       String s = "[ ";

       //print queue
       for(int i = 0; i < size(); i++)
           s += a[i] + " ";

       //print array
       for(int j = size(); j < a.length; j++)
           s += "* ";

       s += "]";
       return s;
       }
   }


   //equals - determines if two queues are equivalent
   //i.e. do they have the same elements in the same sequence
   //ignoring the structure they are stored in
   public boolean equals(Object otherQ){

           if(otherQ == null)
               return false;
           else
           {
               //Figure out how many interfaces the other guy
               //implements
               int numIs = otherQ.getClass().getInterfaces().length;
               boolean flag = false;

               //look at all of the other guys interfaces
               //and if he doesn't implement QueueADT, then
               //he clearly isn't a Queue and we return false
               for(int i = 0; i < numIs; i++)
               {
                   if(this.getClass().getInterfaces()[0] ==
                       otherQ.getClass().getInterfaces()[i])
                   {
                       flag = true;
                   }
               }
               if(!flag)
                   return false;
               else //we know that the other guy exists and
                   //we know that he implements QueueADT
               {
                   QueueADT q = (QueueADT)otherQ;
                   if(this.size() != q.size())
                       return false;
                   else
                   {
                       boolean queuesEqual = true;
                       for(int i = 0; i < this.size(); i++)
                       {
                           int ourElement = this.dequeue();
                           int qElement = q.dequeue();

                           if(ourElement != qElement)
                               queuesEqual = false;

                           this.enqueue(ourElement);
                           q.enqueue(qElement);
                       }
                       //return our final answer
                       return queuesEqual;
                   }
               }


           }
       }


   public void showInnerWorkings(){
       System.out.print("[");
       for (int i = 0; i < this.a.length; i++)
           System.out.print(this.a[i] +
                           (i != this.a.length - 1 ? ", " : ""));
       System.out.println("]");
   }

   }

QueueADT interface:

队列ADT接口：

public interface QueueADT
{
   //enqueue - adds an element to the back of the queue
   public void enqueue(int element);

   //dequeue - removes and returns the element from the
   //front of the queue
   public int dequeue();

   //peek - returns but does not remove the element from
   //the front of the queue
   public int peek();

   //isEmpty - determines if the queue is empty or not
   public boolean isEmpty();

   //size - returns the number of elements in our Queue
   public int size();

   //toString - returns a String representation of our Queue
   public String toString();

   //equals - determines if two queues are equivalent
   //i.e. do they have the same elements in the same sequence
   //ignoring the structure they are stored in
   public boolean equals(Object otherQ);
}

回答by Paddle

What do you really want? A Queue or a circular array ?

你真正想要的是什么？队列还是循环数组？

1. Circular array :

1. 圆形阵列：

You should have a look there. As you can see, the simpliest (and the best) way is to extend the ArrayList class and override the get() method.

你应该去那里看看。如您所见，最简单（也是最好）的方法是扩展 ArrayList 类并覆盖 get() 方法。

1. Queue :

2. 队列 ：

Just use the java.util.Queueinterface.

只需使用java.util.Queue接口。