java - StackArray Generic class does not work -
i beginner in java , trying write stackarray. have tester test code. have run several times not pass push method , search method. can give me idea doing wrong? thank in advance!
import java.util.arrays; import java.util.nosuchelementexception; public class stack<e> implements stackadt<e>{ private e a[]; private int head, size; public stack(){ } /*adds specified element top of stack. returns item added.*/ public e push(e element){ if (a.length == size){ throw new illegalstateexception("cannot add full stack"); } // since remainder of stack right of stack, // adding new element pushes head left (+ wrap around) //head = (head - 1 + a.length) % a.length; return a[head++] = element; // return element; } /*removes , returns element top of stack*/ public e pop(){ if (empty()){ throw new java.util.emptystackexception(); } // need copy of old head before advance // new head. want return old head, not new head. e rval = a[head]; // why don't need add a.length here did in push? head = (head + 1) % a.length; return rval; } /*returns without removing element @ top of stack*/ public e peek(){ if (empty()){ throw new java.util.emptystackexception(); } return a[head]; } /*returns true if stack empty, false otherwise*/ public boolean empty(){ return size == 0; } /*returns 1-based position object on stack means if object o occurs item in stack, method returns distance top of stack of occurrence nearest top of stack - topmost item on stack considered @ distance 1.*/ public int search(object o){ // logical index (int = 0; < size; i++){ // p physical index int p = (head + i) % a.length; e e = a[p]; // e == o items (null or non-null same?) // if not same, @ least 1 of them // non-null , can compared other. if (e == o || e != null && e.equals(o)){ // distance = logical index + 1 per above description return + 1; } } // no match made throw new nosuchelementexception(); } /*returns string representation of queue*/ public string tostring(){ // output should like: [e_0, e_1, ..., e_n-1] // empty stack: [] if (empty()) return "[]"; // know there @ least 1 element in stack // since didn't return stringbuilder b = new stringbuilder(); b.append("[").append(a[head]); // start on second logical index (int = 1; < size; i++){ int p = (head + i) % a.length; e e = a[p]; b.append(", ").append(e); } b.append("]"); return b.tostring(); } }
the prominent error not instantiate instance variables of stack. java uses default values non-initialized values: primitive numbers set 0, booleans set false , reference-types (i.e., arrays , objects) set null. means head , size both initialized 0 while a initialized null. latter yields nullpointerexception when dereferencing content.
assuming want keep array internal representation, you'd have initialize instance of e[] somehow. unfortuantely, cannot call new e[size]. see this other question on how instantiate generic array.
as initial value of head, seems supposed point top of stack, not consistent in how want use it: in push, use head index of next free element in a , increment value after adding element. in tostring, peek , pop, use head index of element want return. either representation okay, must not mix them up.
assuming want head point last element, initialize -1 , increment value in push-method before accessing index in a. note difference between head++ , ++head:
int = head++; is equivalent to
int = head; head = head + 1; while
int = ++head; is equivalent
head = head + 1; int = head; so fix, change
return a[head++] = element; to
return a[++head] = element; but better add few lines of code , make logic more explicit incrementing value of head first.
now covered initialization, there's bug regarding value of size: push should increment size of stack while pop should decrement it: however, in code, size never modified, hence empty true.
also, don't quite understand idea behind line
// why don't need add a.length here did in push? head = (head + 1) % a.length; in pop. element removed (and not added) i'd should head = head - 1 or head-- if prefer postfix-operators.
putting together
initialize stack properly, e.g.,
private e a[]; private int head = -1; private int size = 0; public stack(class<e> c, int maxsize){ @suppresswarnings("unchecked") final e[] = (e[]) array.newinstance(c, maxsize); this.a = a; } update value of size in push , fix update head:
public e push(e element){ if (a.length == size){ throw new illegalstateexception("cannot add full stack"); } size++; return a[++head] = element; } update value of size , head in pop:
public e pop(){ if (empty()){ throw new java.util.emptystackexception(); } size--; return a[head--]; } fixing tostring
remark: kind of ignored comments, comments tend lie code gets refactored; noticed wrote in comment:
// since remainder of stack right of stack, // adding new element pushes head left (+ wrap around) which opposite of next line in code tells: return a[head++] = element;. proposed bugfixes based on code, not comment, hence remainder of stack left of head. because of that, implementation of tostring must changed print array right left instead of left right:
public string tostring(){ if (empty()) return "[]"; stringbuilder b = new stringbuilder(); b.append("[").append(a[head]); (int = head - 1; >= 0; i--){ e e = a[i]; b.append(", ").append(e); } b.append("]"); return b.tostring(); }
Comments
Post a Comment