java - Java - 使用数组的有界队列

Question

我被要求创建一个有界队列类，其条件如下：

仅使用原始类型，实现有界队列来存储整数。数据结构应该针对算法运行时间、内存使用和内存吞吐量进行优化。不应导入和/或使用任何外部库。解决方案应以提供以下功能的一类交付：

构造函数 - 类应该提供一种创建对象的方法，该方法需要一个整数来设置队列的大小。
enqueue - 如果队列未满，函数应该取一个整数并将其存储在队列中。该函数应正确处理队列已满的情况。
dequeue - 如果当前存储在队列中，函数应该返回一个整数。该函数应正确处理队列为空的情况。

我写了这门课，但我想通过让别人测试它来寻求帮助，看看它是否能正常工作。我写了一个小的主类来测试它，一切似乎都在工作，但我希望在提交之前用另一双眼睛看看它。是为了实习。先感谢您。

public class Queue<INT>
{


    int size;
    int spacesLeft;
    int place= 0;
    int[] Q;


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

    //enqueue - function should take an integer and store it in the queue if the queue isn't full.
    //The function should properly handle the case where the queue is already full
    public void enque(int newNumber) throws Exception
    {
        if(place <= size)
        {
            Q[place] = newNumber;
            place++;
            spacesLeft--;

        }
        else
            throw new Exception();
    }


    //dequeue - function should return an integer if one is currently stored in the queue. 
    //The function should properly handle the case where the queue is empty.
    public int deque() throws Exception
    {
        int dequeNum;


        if(spacesLeft == size)
            throw new Exception();
        else
        {
            dequeNum = Q[0];
            spacesLeft++;
        }

        int[] tempAry = new int[size];  
        for (int i=0; i < Q.length; i++)
        {  
            if(i < size-1)
            {
                tempAry[i] = Q[i+1]; // put in destination  
            }

        }

        Q = tempAry;

        for(int i = 0; i < Q.length; i++)
        {
            System.out.println("value in Q"+Q[i]);

        }


        return dequeNum;


    }
}

score 7 · Accepted Answer

这是根据您的规范的实现。

这是相同的源代码。

import java.util.Arrays;

public class Queue {

    private int enqueueIndex;// Separate index to ensure enqueue happens at the end
    private int dequeueIndex;// Separate index to ensure dequeue happens at the
                            // start
    private int[] items;
    private int count;
    // Lazy to add javadocs please provide
    public Queue(int size) {
        enqueueIndex = 0;
        dequeueIndex = 0;
        items = new int[size];
    }
    // Lazy to add javadocs please provide
    public void enqueue(int newNumber) {
        if (count == items.length)
            throw new IllegalStateException();
        items[enqueueIndex] = newNumber;
        enqueueIndex = ++enqueueIndex == items.length ? 0 : enqueueIndex;
        ++count;
    }
    // Lazy to add javadocs please provide
    public int dequeue() {
        if (count == 0)
            throw new IllegalStateException();
        int item = items[dequeueIndex];
        items[dequeueIndex] = 0;
        dequeueIndex = ++dequeueIndex == items.length ? 0 : dequeueIndex;
        --count;
        return item;
    }

    @Override
    public String toString() {
        return Arrays.toString(items);
    }
}

score 2 · Accepted Answer

在 enque 函数中

 if(place <= size)
    {
        Q[place] = newNumber;
        place++;
        spacesLeft--;

    }

当 place == size --> 你会得到一个索引超出范围的异常时会发生什么。

在出队函数中，您总是返回 Q[0] 并且每次分配新内存并将旧数组移动到新数组！！！！这真的会很慢。

score 1 · Accepted Answer

检查这个。它使用数组作为占位符。

http://c-madeeasy.blogspot.com/2011/08/queue-using-array-in-java-complete.html

你也检查一下。这个使用链表作为占位符。

http://algs4.cs.princeton.edu/13stacks/Queue.java.html

score 0 · Accepted Answer

package com.test;
public class QueueUsingArray {

    int sizeofArr; 
    int[] Q;
    int frontindex = -1;
    int rearindex = -1;
    int cnt=0;


    public QueueUsingArray(int sizeOfArr) {
        // TODO Auto-generated constructor stub
        this.sizeofArr = sizeOfArr;
        this.Q = new int[sizeOfArr];
    }

    public boolean isFull()
    {
      if (cnt == sizeofArr)
          return true;
          else
              return false;

    }
    public void enQueue(int Number) throws Exception
    {
        if(!isFull() ) /*Q is not Full and rearindx is not on last element of Array*/
        {  
            if(cnt == 0)
            {
                frontindex++;  
            }

            if (rearindex+1 != sizeofArr)
            {
                 Q[++rearindex] = Number;
            }
            else 
            {    rearindex= -1;
                 Q[++rearindex] = Number;   
            }
            cnt++;


        }

        else 
            throw new Exception("Queue Overflow");

    }

    public int deQueue() throws Exception
    {
        int x;
        if(cnt != 0)
        {
           cnt--;
           if (frontindex !=sizeofArr)
           {
                x = Q[frontindex];
                Q[frontindex] = -1;
                frontindex++;
                return x;
           }    
           else
           {   frontindex = 0;
                x = Q[0];
                Q[0] = -1;     
                return x;

           }   
        }  
        else
         throw new Exception("Queue Underflow");

    }
    public int size()
    {
        return cnt;

    }
      /*printQ method is not optimized to print Q from front to rear, and it just for verification     
       purpose */
    public void printQ()
    {
        System.out.println("current Q:");
        for(int i=0;i<Q.length;i++)
        {
            System.out.println(Q[i]);
        }

    }


    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
      try{
        QueueUsingArray q = new QueueUsingArray(5);

        //System.out.println("Is QueuFull ?" + q.isFull());
        System.out.println("CurrentQueue Size is:" + q.size());
        //System.out.println(q.deQueue()); 

        q.enQueue(1);
        q.enQueue(2);
        q.enQueue(3);
        q.enQueue(4);
        q.enQueue(5);
        q.printQ();
        System.out.println("CurrentQueue Size is:" + q.size());
        System.out.println("Is QueuFull ?" + q.isFull());

        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println("CurrentQueue Size is:" + q.size());

        q.enQueue(6);
        q.enQueue(7);
        q.enQueue(8);
        q.printQ();
        System.out.println(q.deQueue());
        q.enQueue(9);
        q.printQ();
        System.out.println("CurrentQueue Size is:" + q.size());

         }catch(Exception e)
           {
              e.printStackTrace();  
           }
  }

}

score 0 · Accepted Answer

刚刚尝试使用 LinkedList 实现 Queue ...如果有任何帮助，请随时重新/修改以使其高效。

package com.test;


public class QueueUsingLinkeList {

public class Node{
    Object data; 
    Node next;

    public Node(Object data)
    {
        this.data = data;
        this.next = null;
    }


}

int cnt=0;
Node front=null;
Node rear=null;

public void enQueue(int number)
{
    Node n = new Node(number);

   if(front== null && rear==null)
       front = rear = n ; 
   else
   {
       rear.next = n;
       rear = rear.next;
   }
   cnt++;

}

public Object deQueue() throws Exception
{
    Node temp;
    if(front == null && rear == null)
    {   throw new Exception("Queue underflow, can not DeQueue any element");

    }
    else if (front== rear && front.next == null)
    {
         temp = front;
         front = rear = null;
         return temp.data;
    }
    else
    {
        temp = front;
        front = front.next;
        cnt--;
        return temp.data;
    }
}
public int size()
{
    return cnt;
}

public QueueUsingLinkeList() {



}

public void printQ()
{
    Node traverse = front;
    System.out.print("Current Queue::");
    for(int i=0;i<cnt;i++)
    {
        System.out.print(traverse.data.toString()+ "  ");
        traverse = traverse.next;
    } 

}
/**
 * @param args
 */
public static void main(String[] args) {
    try{
        QueueUsingLinkeList q = new QueueUsingLinkeList();

        //System.out.println("Is QueuFull ?" + q.isFull());
        System.out.println("CurrentQueue Size is:" + q.size());
        //System.out.println(q.deQueue()); 

        q.enQueue(1);
        q.enQueue(2);
        q.enQueue(3);
        q.enQueue(4);
        q.enQueue(5);
        q.printQ();
        System.out.println("CurrentQueue Size is:" + q.size());


        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        q.printQ();
        System.out.println("CurrentQueue Size is:" + q.size());

        q.enQueue(6);
        q.enQueue(7);
        q.enQueue(8);
        q.printQ();
        System.out.println("CurrentQueue Size is:" + q.size());

        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
                    q.enQueue(9);
        q.printQ();
        System.out.println("CurrentQueue Size is:" + q.size());
}catch(Exception e)
{
   e.printStackTrace(); 
}

}

}

java - Java - 使用数组的有界队列

5 回答 5

Related

Reference