基礎となる構造として配列とリンク リストを使用してキューを作成するクラスの各メソッドとコンストラクターの複雑さのメトリック (Big-theta 表記法) を決定しようとしています。具体的には、各メソッドまたはコンストラクターが O(k) か O(n) かを調べてすばやく判断する方法がわかりません。誰かがこれを説明できますか？
配列クラス:
public class UnboundedQueueArray<T> implements UnboundedQueue<T> {
// elements stored in array
private T[] elements;
// the number of elements currently in the queue
private int numElems;
// initial length of queue
private static final int INITIAL_LENGTH = 10;
/**
* Constructs the UnboundedQueueArray object.
*/
@SuppressWarnings("unchecked")
public UnboundedQueueArray() {
elements = (T[]) new Object[INITIAL_LENGTH];
numElems = 0;
}
/**
* This method inserts the specified element, unless the
* queue is full.
*
* @param o The element to be inserted.
*/
public void insert(T o) {
// checks and enlarges capacity if necessary
ensureExtraCapacity(1);
elements[numElems] = o;
numElems++;
}
// this helper method ensures there is always extra capacity
// in the queue to insert elements
@SuppressWarnings("unchecked")
private void ensureExtraCapacity(int extraCapacity) {
if(numElems + extraCapacity > elements.length) {
// double old capacity
int newCapacity = elements.length * 2 + extraCapacity;
// allocate new array
T[] newElements = (T[]) new Object[newCapacity];
// copy contents of old array into new array
for(int i = 0; i < length(); i++) {
newElements[i] = elements[i];
}
// replace old array with new array
elements = newElements;
}
}
/**
* This method returns the element at the front of the
* queue, unless the queue is empty.
*
* @return The element at the front of the queue.
* @throws EmptyQueueException If the queue is empty.
*/
public T front() throws EmptyQueueException {
if(length() == 0) {
throw new EmptyQueueException("Queue is empty.");
}
return elements[0];
}
/**
* This method retrieves and removes the element at the front
* of the queue, unless the queue is empty.
*
* @return The element at the front of the queue.
* @throws EmptyQueueException If the queue is empty.
*/
public T remove() throws EmptyQueueException {
if(length() == 0) {
throw new EmptyQueueException("Queue is empty.");
}
// retrieve element at front of queue
T frontElem = elements[0];
// shift elements to the left
for(int i = 1; i < length(); i++) {
elements[i - 1] = elements[i];
}
// "null out" last element
elements[numElems - 1] = null;
// decrement number of elements
numElems--;
return frontElem;
}
/**
* This method reports whether or not the queue contains
* element(s).
*
* @return If one or more elements exists or not.
*/
public boolean hasMember() {
return (length() > 0);
}
/**
* This method returns the current length of the queue.
*
* @return The length of the queue.
*/
public int length() {
return numElems;
}
/**
* This method provides a string representation of the queue.
*
* @return The String representation of the queue.
*/
public String toString() {
// for empty queue
if(length() == 0) {
String str = "[ " + length() + " : ]";
return str;
}
// fencepost algorithm
String str = "[ " + length() + " : " + elements[0];
for(int i = 1; i < length(); i++) {
str += ", " + elements[i];
}
str += " ]";
return str;
}
}
リンク リスト クラス:
public class UnboundedQueueLinkedList<T> implements UnboundedQueue<T> {
// the reference to the first link
private Link first;
// the reference to the last link (if it exists)
private Link last;
// the number of links in the queue
private int numLinks;
// initial length of queue
private static final int INITIAL_LENGTH = 10;
/**
* Constructs the UnboundedQueueLinkedList object.
*/
@SuppressWarnings("unchecked")
public UnboundedQueueLinkedList() {
first = null;
last = null;
numLinks = 0;
}
/**
* This method inserts the specified element, unless the
* queue is full.
*
* @param o The element to be inserted.
*/
public void insert(T o) {
Link newLink = new Link(o, null);
if(first == null) {
// we are adding the first link
first = newLink;
} else { // there are existing links, so add newLink after old last link
last.next = newLink;
}
// update the last link
last = newLink;
// increment the number of links in the queue
numLinks++;
}
/**
* This method returns the element at the front of the
* queue, unless the queue is empty.
*
* @return The element at the front of the queue.
* @throws EmptyQueueException If the queue is empty.
*/
@SuppressWarnings("unchecked")
public T front() throws EmptyQueueException {
if(length() == 0) {
throw new EmptyQueueException("Queue is empty.");
}
T frontElem;
// get link at front of queue
Link frontLink = getLinkAtPos(0);
frontElem = (T) frontLink.item;
return frontElem;
}
// this helper method gets the link at the specified position
private Link getLinkAtPos(int pos) {
Link p = first;
for(int i = 0; i < pos; i++) {
p = p.next;
}
return p;
}
/**
* This method retrieves and removes the element at the front
* of the queue, unless the queue is empty.
*
* @return The element at the front of the queue.
* @throws EmptyQueueException If the queue is empty.
*/
@SuppressWarnings("unchecked")
public T remove() throws EmptyQueueException {
if(length() == 0) {
throw new EmptyQueueException("Queue is empty.");
}
T removedElem;
removedElem = (T) first.item;
// remove "first" link
first = first.next;
// update "last" if necessary
if(first == null) {
last = null;
}
// decrement the number of links in the queue
numLinks--;
return removedElem;
}
/**
* This method reports whether or not the queue contains
* element(s).
*
* @return If one or more elements exists or not.
*/
public boolean hasMember() {
return (length() > 0);
}
/**
* This method returns the current length of the queue.
*
* @return The length of the queue.
*/
public int length() {
return numLinks;
}
/**
* This method provides a string representation of the queue.
*
* @return The String representation of the queue.
*/
public String toString() {
// for empty queue
if(length() == 0) {
String str = "[ " + length() + " : ]";
return str;
}
Link p = first;
String str = "[ " + length() + " : " + p.item;
for(int i = 1; i < numLinks; i++) {
p = p.next;
str += ", " + p.item;
}
str += " ]";
return str;
}
// this helper class creates the links that structure the list
class Link<T> {
// data associated with this link
public Object item;
// next link, or null if no next link
public Link next;
/**
* Constructs the Link object.
*
* @param item The data to be associated with this Link object.
* @param next The next link (or null if no next link exists).
*/
public Link(Object item, Link next) {
this.item = item;
this.next = next;
}
}
}
編集: ここにスタック配列クラスがあります:
public class UnboundedStackArray<T> implements UnboundedStack<T> {
// elements stored in array
private T[] elements;
// the number of elements currently in the stack
private int numElems;
// initial depth of stack
private static final int INITIAL_DEPTH = 10;
/**
* Constructs the UnboundedStackArray object.
*/
@SuppressWarnings("unchecked")
public UnboundedStackArray() {
elements = (T[]) new Object[INITIAL_DEPTH];
numElems = 0;
}
/**
* This method "pushes" an element onto the top of the stack.
*
* @param o The element to be "pushed" (or added) onto the top
* of the stack.
*/
public void push(T o) {
// ensure space to add element
ensureExtraCapacity(1);
elements[numElems] = o;
// increment the number of elements in the stack
numElems++;
}
// this helper method ensures there is always extra capacity
// in the stack to "push" (or add) elements onto top of stack
@SuppressWarnings("unchecked")
private void ensureExtraCapacity(int extraCapacity) {
if(numElems + extraCapacity > elements.length) {
// double old capacity
int newCapacity = elements.length * 2 + extraCapacity;
// allocate new array
T[] newElements = (T[]) new Object[newCapacity];
// copy contents of old array into new array
for(int i = 0; i < depth(); i++) {
newElements[i] = elements[i];
}
// replace old array with new array
elements = newElements;
}
}
/**
* This method retrieves the element at the top of the stack,
* unless the stack is empty.
*
* @return The element at the top of the stack.
* @throws EmptyStackException If the stack is empty.
*/
public T top() throws EmptyStackException {
if(depth() == 0) {
throw new EmptyStackException("Stack is empty");
}
return elements[numElems - 1];
}
/**
* This method retrieves and removes the element at the top of
* the stack, unless the stack is empty.
*
* @return The element at the top of the stack.
* @throws EmptyStackException If the stack is empty.
*/
public T pop() throws EmptyStackException {
if(depth() == 0) {
throw new EmptyStackException("Stack is empty");
}
// retrieve element at top of stack
T topElem = elements[numElems - 1];
// "null out" element at top of stack
elements[numElems - 1] = null;
// decrement number of elements
numElems--;
return topElem;
}
/**
* This method reports whether or not the stack contains
* element(s).
*
* @return If one or more elements exists or not.
*/
public boolean hasMember() {
return (depth() > 0);
}
/**
* This method returns the current depth (or length) of the stack.
*
* @return The depth of the stack.
*/
public int depth() {
return numElems;
}
/**
* This method provides a string representation of the stack.
*
* @return The String representation of the stack.
*/
public String toString() {
// for empty stack
if(depth() == 0) {
String str = "[ " + depth() + " : ]";
return str;
}
String str = "[ " + depth() + " : " + elements[numElems - 1];
for(int i = numElems - 2; i >= 0; i--) {
str += ", " + elements[i];
}
str += " ]";
return str;
}
}
スタック リンク リスト クラスは次のとおりです。
public class UnboundedStackLinkedList<T> implements UnboundedStack<T> {
// the reference to the first link
private Link first;
// the reference to the last link (if it exists)
private Link last;
// the number of links in the stack
private int numLinks;
// initial length of stack
private static final int INITIAL_LENGTH = 10;
/**
* Constructs the UnboundedStackLinkedList object.
*/
@SuppressWarnings("unchecked")
public UnboundedStackLinkedList() {
first = null;
last = null;
numLinks = 0;
}
/**
* This method "pushes" an element onto the top of the stack.
*
* @param o The element to be "pushed" (or added) onto the top
* of the stack.
*/
public void push(T o) {
Link newLink = new Link(o, null);
if(first == null) {
// add the first link
first = newLink;
} else { // there are existing links, so add newLink after old last link
last.next = newLink;
}
// update the last link
last = newLink;
// increment the number of links in the queue
numLinks++;
}
/**
* This method retrieves the element at the top of the stack,
* unless the stack is empty.
*
* @return The element at the top of the stack.
* @throws EmptyStackException If the stack is empty.
*/
@SuppressWarnings("unchecked")
public T top() throws EmptyStackException {
if(depth() == 0) {
throw new EmptyStackException("Stack is empty.");
}
T topElem;
// get link at front of queue
Link topLink = getLinkAtPos(numLinks - 1);
topElem = (T) topLink.item;
return topElem;
}
// this helper method gets the link at the specified position
private Link getLinkAtPos(int pos) {
Link p = first;
for(int i = 0; i < pos; i++) {
p = p.next;
}
return p;
}
/**
* This method retrieves and removes the element at the top of
* the stack, unless the stack is empty.
*
* @return The element at the top of the stack.
* @throws EmptyStackException If the stack is empty.
*/
@SuppressWarnings("unchecked")
public T pop() throws EmptyStackException {
if(depth() == 0) {
throw new EmptyStackException("Stack is empty.");
}
T removedElem;
removedElem = (T) last.item;
Link p = first;
for(int i = 0; i < depth() - 2; i++) {
p = p.next;
}
//p.next = null;
last = p;
// update "last" if necessary
if(first == null) {
last = null;
}
// decrement the number of links in the queue
numLinks--;
return removedElem;
}
/**
* This method reports whether or not the stack contains
* element(s).
*
* @return If one or more elements exists or not.
*/
public boolean hasMember() {
return (depth() > 0);
}
/**
* This method returns the current depth (or length) of the stack.
*
* @return The depth of the stack.
*/
public int depth() {
return numLinks;
}
/**
* This method provides a string representation of the stack.
*
* @return The String representation of the stack.
*/
@SuppressWarnings("unchecked")
public String toString() {
// for empty stack
if(depth() == 0) {
String str = "[ " + depth() + " : ]";
return str;
}
Link pL = last;
String str = "[ " + depth() + " : " + pL.item;
for(int i = numLinks - 2; i >= 0; i--) {
Link tempLink = getLinkAtPos(i);
str += ", " + tempLink.item;
}
str += " ]";
return str;
}
// this helper class creates the links that structure the list
class Link<T> {
/**
* Data associated with this link.
*/
public Object item;
/**
* Next link, or null if no next link.
*/
public Link next;
/**
* Constructs the Link object.
*
* @param item The data to be associated with this Link object.
* @param next The next link (or null if no next link exists).
*/
public Link(Object item, Link next) {
this.item = item;
this.next = next;
}
}
}