Java – 使用数组的有界队列

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

仅使用基本类型，实现有界队列以存储整数。 应针对算法运行时，内存使用和内存吞吐量优化数据结构。 不应导入和/或使用外部库。 解决方案应该在一个提供以下function的类中提供：

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

我写了这个课程，但我想通过让某人测试它以及看它是否正常工作来寻求帮助。 我写了一个小的主要类来测试它，一切似乎都在工作，但我想在提交它之前看看另一双眼睛。 它是为了实习。 先谢谢你。

public class Queue { 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; } } 

Answer 1

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

这是相同的源代码。

 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); } } 

Answer 2

在enquefunction

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

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

在出队function中，你总是返回Q [0]并且每次分配新内存并将旧arrays移动到新arrays！ 这将是非常缓慢的。

Answer 3

检查一下。 它使用数组作为占位符。

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

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

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

Answer 4

刚尝试使用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 

Answer 5

 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