所以我在Java中创建了一个DoubleQueue ..它用于我的数据结构和算法类,我们试图证明可以使用DoubleQueue来实现堆栈和队列。以下是它的工作方式:Java通用堆栈错误
它使用数组来存储项目,头部指向数组中的前项,尾部指向数组的后项。该阵列是圆形的,当容量达到90%时它会扩展。现在我认为扩张正在大肆渲染。当我将一堆整数添加到堆栈时,将它们全部删除,它们显示正常,按照相反的顺序。但是,我试图通过按String.charAt来反转字符串,然后弹出所有字符并将其打印出来。这适用于足够短而不需要扩展的字符串。但是,一旦需要扩展,我开始得到一个奇怪的输出,它涉及到乱码字符(不正确的顺序,缺少字符)以及空值。
我认为它有事情做与我怎样投荷兰国际集团的数组:
/**
* Expands the capacity of the storage array that holds the collection of items
* within the DoubleQueue *** only if expansion is needed ***
* @return True if the array was expanded; False otherwise
*/
@SuppressWarnings({"unchecked"})
public boolean expandArray() {
// First, see if need to expand
if((double) size/storage.length >= CAPACITY_EXPAND) {
// Create a temporary pointer to the storage array
E[] temp = storage;
// First out what type of expansion we're doing and create a new, larger array
if(expansionRule == EXPANSION_DOUBLE)
storage = (E[])new Object[ 2 * temp.length ];
else
storage = (E[])new Object[ temp.length + INCREASE_CONSTANT ];
int i = 0; // Counter for storage
int j = tail; // Counter for temp
// Copy temp to storage
while(j != head) {
storage[ i ] = temp[ j ];
if(j == temp.length - 1) j = 0; // If we have to wrap around the array
else j++;
i++;
}
storage[ i ] = temp[ j ];
return true;
}
return false;
}
这里是整个代码:
public class DoubleQueue<E> {
/** CONSTANTS **/
private final int INCREASE_CONSTANT = 10; // The amount to increase by if expansion rule is increase by constant
private final double CAPACITY_EXPAND = 0.9; // The size:capacity ratio at which the storage should be expanded
public static final char EXPANSION_DOUBLE = 'd'; // Parameter for expansionRule()
public static final char EXPANSION_CONSTANT = 'c'; // Parameter for expansionRule()
/** VARIABLES **/
private char expansionRule; // Stores the current expansion rule
private int head; // Keeps track of the index of the first element
private int tail; // Keeps track of the index of the last element
private int size; // Keeps track of the number of items in storage
private E storage[]; // Holds the collection of items
/** CONSTRUCTORS **/
/**
* Creates an empty DoubleQueue with a given capacity. Initializes variables
* and sets the default expansion rule.
* @param capacity The initial capacity of the DoubleQueue
*/
@SuppressWarnings({ "unchecked" })
public DoubleQueue(int capacity) {
size = 0;
head = -1;
tail = -1;
storage = (E[])new Object[ capacity ];
setExpansionRule(EXPANSION_DOUBLE);
}
/**
* Creates an empty DoubleQueue of initial capacity 10.
*/
public DoubleQueue() {
this(10);
}
/** METHODS **/
/**
* Checks to see if the DoubleQueue is currently empty
* @return True if the DoubleQueue is empty; False otherwise
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Adds an item at the beginning of the DoubleQueue
* @param item The item to be added to the DoubleQueue
* @return True if the item was successfully added
*/
public boolean addFirst(E item) {
// First, perform expansion if neccessary
expandArray();
// Put the head and tail pointers in the right spots
if(isEmpty()) {
head = 0;
tail = 0;
} else if(head == storage.length - 1) head = 0;
else head++;
// Add the item
storage[ head ] = item;
// Increment the size
size++;
return true;
}
/**
* Adds an item at the end of the DoubleQueue
* @param item The item to be added to the DoubleQueue
* @return True if the item was successfully added
*/
public boolean addLast(E item) {
// First, perform expansion if neccessary
expandArray();
// Put the head and tail pointers in the right place
if(isEmpty()) {
head = 0;
tail = 0;
} else if(tail == 0) tail = storage.length - 1;
else tail--;
// Add the item
storage[ tail ] = item;
// Increment the size
size++;
return true;
}
/**
* Expands the capacity of the storage array that holds the collection of items
* within the DoubleQueue *** only if expansion is needed ***
* @return True if the array was expanded; False otherwise
*/
@SuppressWarnings({"unchecked"})
public boolean expandArray() {
// First, see if need to expand
if((double) size/storage.length >= CAPACITY_EXPAND) {
// Create a temporary pointer to the storage array
E[] temp = storage;
// First out what type of expansion we're doing and create a new, larger array
if(expansionRule == EXPANSION_DOUBLE)
storage = (E[])new Object[ 2 * temp.length ];
else
storage = (E[])new Object[ temp.length + INCREASE_CONSTANT ];
int i = 0; // Counter for storage
int j = tail; // Counter for temp
// Copy temp to storage
while(j != head) {
storage[ i ] = temp[ j ];
if(j == temp.length - 1) j = 0; // If we have to wrap around the array
else j++;
i++;
}
storage[ i ] = temp[ j ];
return true;
}
return false;
}
/**
* Gets the element at the front of the DoubleQueue & removes it
* @throws EmptyDoubleQueueException if the queue is empty and there is no item to remove
* @return The item at the front of the DoubleQueue
*/
public E removeFirst() throws EmptyDoubleQueueException {
// If the DoubleQueue is empty we obviously can't get an element from it..
if(size == 0) throw new EmptyDoubleQueueException();
// Create a temporary record of the item and remove it from storage
E temp = storage[ head ];
storage[ head ] = null;
size--; // Decrease the size of the DoubleQueue
if(size == 0) { // If we're taking the last element
head = -1;
tail = -1;
} else if (head == 0) head = storage.length - 1; // Wrap around the array
else head--;
return temp;
}
/**
* Gets the item at the back of the DoubleQueue & removes it
* @throws EmptyDoubleQueueException if the queue is empty and there is no item to return
* @return The item at the back of the doubleQueue
*/
public E removeLast() throws EmptyDoubleQueueException {
// If the DoubleQueue is empty we obviously can't get an element from it..
if(size == 0) throw new EmptyDoubleQueueException();
// Create a temporary record of the item and remove it from storage
E temp = storage[ tail ];
storage[ tail ] = null;
size--; // Decrease the size of the DoubleQueue
if(size == 0) { // If we're taking the last element
head = -1;
tail = -1;
} else if (tail == storage.length - 1) tail = 0; // Wrap around the array
else tail++;
return temp;
}
/**
* Gets the item at the front of the DoubleQueue
* @return The item at the front of the DoubleQueue; null if list is empty
*/
public E peekFirst() {
if(size == 0) return null; // Nothing to return
return storage[ head ];
}
/**
* Gets the item at the back of the DoubleQueue
* @return The item at the back of the DoubleQueue; null if list is empty
*/
public E peekLast() {
if(size == 0) return null; // Nothing to return
return storage[ tail ];
}
/**
* Trims the size of the underlying collection to the exact number of items within
* the collection
*/
@SuppressWarnings({"unchecked"})
public void truncate() {
E[] temp = storage; // Create a temporary pointer to storage
storage = (E[])new Object[ storage.length ]; // Create a new storage array that is the size of the # of elements in storage
int i = 0; // Pointer to iterate storage
int j = 0; // Pointer to iterate temp
// Copy values from temp to storage
while(j != head) {
storage[ i ] = temp[ j ];
i++;
if(j == temp.length - 1) j = 0; // Wrap around array
else j++;
}
}
/**
* Sets the type of expansion to be used when the underlying array nears capacity
* @param rule The type of expansion to be used in the future
* @throws InvalidInputException when the input provided does not correspond to an expansion type
* @return True if the expansion rule was set successfully
*/
public boolean setExpansionRule(char rule) {
// Check to make sure the rule provided was valid
if(rule != EXPANSION_CONSTANT && rule != EXPANSION_DOUBLE)
throw new InvalidInputException();
// Set the rule
expansionRule = rule;
return true;
}
/**
* Returns the current capacity of the array that holds the collection of
* items currently in the DoubleQueue. This method is used for testing
* purposes only and WOULD NOT BE INCLUDED in a public release of DoubleQueue.
* @return The capcity of the storage array
*/
public int getCapacity() {
return storage.length;
}
/**
* Gets the number of elements currently in the DoubleQueue
* @return The number of elements currently in the DoubleQueue
*/
public int getSize() {
return size;
}
}
,这里是司机:
public class Driver {
public static void main(String[] args) {
// First, check the isEmpty() method
System.out.println("Check isEmpty() method:");
DoubleQueue<Integer> dq = new DoubleQueue<Integer>();
if(dq.isEmpty()) System.out.println("isEmpty() method returns true when DoubleQueue is empty.");
else System.out.println("ERROR: isEmpty() method returns false when DoubleQueue is empty.");
// Add something and check the isEmpty() method again
dq.addFirst(1);
if(dq.isEmpty()) System.out.println("ERROR: isEmpty() method returns true when DoubleQueue is not empty.");
else System.out.println("isEmpty() method returns false when DoubleQueue is not empty.");
System.out.println();
// Test expansion using default expansion (double)
System.out.println("Check expansion by doubling (should double in capacity when the 10th element is added and again when the 19th element is added):");
dq = new DoubleQueue<Integer>();
System.out.println("Capacity before adding elements: " + dq.getCapacity());
for(int i = 1; i <= 20; i++) {
dq.addFirst(i);
System.out.println("Added element #" + i + ". Capacity: " + dq.getCapacity() + ".");
}
// Test expansion using constant expansion
System.out.println();
System.out.println("Check expansion by constant (should add ten to capacity when the 10th and 19th elements are added).");
dq = new DoubleQueue<Integer>();
dq.setExpansionRule(DoubleQueue.EXPANSION_CONSTANT);
System.out.println("Capacity before adding elements: " + dq.getCapacity());
for(int i = 1; i <= 20; i++) {
dq.addFirst(i);
System.out.println("Added element #" + i + ". Capacity: " + dq.getCapacity() + ". ");
}
// Test functionality as a STACK
DoubleQueue<Character> stack = new DoubleQueue<Character>();
String toBeReversed = "reht olleh";
System.out.println();
System.out.println("String to be reversed: " + toBeReversed);
// Add string to be reversed letter by letter into strck
for(int i = 0; i < toBeReversed.length(); i++) {
char j = toBeReversed.charAt(i);
stack.addLast(j);
System.out.println("Added letter " + j);
}
System.out.println(stack.getCapacity());
System.out.println(stack.getSize());
// Print stack
while(!stack.isEmpty()) {
try {
System.out.print(stack.removeLast());
} catch(EmptyDoubleQueueException e) {
}
}
/**
// This first bit tests the DoubleQueue as a stack, to reverse a strign
DoubleQueue<Character> dq1 = new DoubleQueue<Character>();
String toBeReversed = "hello";
for(int i = 0; i < toBeReversed.length(); i++) {
dq1.addLast(toBeReversed.charAt(i));
}
while(!dq1.isEmpty()) {
try {
System.out.print(dq1.removeFirst());
} catch(EmptyDoubleQueueException e) {
// Do nothing
}
}**/
}
}
也许你应该尝试隔离问题......太多的代码行甚至想想问题(恕我直言)。 – home
您是否尝试过使用调试器单步执行代码? –
从Driver类输出中报告以下问题是否存在问题:'hlo thernullnull'? –