Homework Assignment: Stack/Queue Implementation Back Objectives Gain familiarity
ID: 659880 • Letter: H
Question
Homework Assignment: Stack/Queue Implementation
Back
Objectives
Gain familiarity with implementing stacks and queues using arrays and linked lists for underlying storage.
Gain familiarity with raising exceptions.
The goal of this assignment is to implement the stack and queue data structures.
The Interfaces
These are the interfaces that we worked with in the previous homework: LA 5 and HW 4.
Implementation notes
Do not use any classes from the java.util package to implement the queue or stack.
Provide complexity metrics (Big-O / Big-Theta) for the stack and queue operations that you implemented. Include the Big-O metrics in the JavaDoc comments for each of the operations inherited from one of the interface. (That is, you don't have to report Big-O metrics for any helper methods that are creating in the stack or queue implementations.) Needless to say, the Big-O values must be associated with the methods in the classes. They cannot be associated with the methods in the interfaces.
The constructors for the bounded stack and bounded queue shall take a single int value as its parameter, the capacity of the data structure.
The constructors for the unbounded stack and unbounded queue shall be parameterless.
For more information about the standard behavior of the stack and queue, please refer to the Powerpoint slides posted on the Moodle site. Another good source of information about stacks and queues is Wikipedia:
http://en.wikipedia.org/wiki/Stack_(data_structure)
http://en.wikipedia.org/wiki/Queue_(data_structure)
Standard Option
For the standard option, there will be two implementations for the unbounded data structures.
Within the csc143.data_structures package, provide one implementation the bounded queue and the bounded stack. Use an array as the underlying data structure.
Within the csc143.data_structures package, provide two implementations of the unbounded stack and the unbounded queue. For one of the implementations, use a linked list as the underlying data structure; for the other, an array.
The initial size of the underlying array for the unbounded stack and unbounded queue shall be ten (10) elements.
The initial size requirement for the underlying array may prompt you to make some changes within the project. Make sure you note that in your report notes.
Note: You will use these classes to implement the next assignment. You may find it easier to use these classes if they are generic. This is one of the pieces of the Challenge option.
Challenge Option
For the challenge option, add the following features:
Constant-time operations
Generic support
Constant-time operations
It is possible to have "all" of the operations be O(k). (The word "all" is in quotes because it is not necessary to have the "debug" methods be O(k). So, capacity, size, and toString can be O(N) and still be acceptable for Challenge points.) Make sure that the implementation for each method is O(k) for the challenge option, with the noted exclusion.
Hint: Refer to the Wikipedia articles listed above for a technique to make the methods O(k).
Generic support
Make the stack and queue interfaces and implementations generic. It should not affect the usefulness of your JUnit test cases. They will "default" to java.lang.Object, if the generic formal type is omitted. However, you are welcome to update the JUnit test cases for generics.
However, implementing the generic data structures adds a little wrinkle. Because of language limitations, one cannot instantiate an array of the generic type, the type given by the parameter. For a full discussion, see the generic tutorial on the Oracle website.
So, there will be a warning issued when the implementation is compiled. The warning message from the compiler should be suppressed using the annotation, @SuppressWarnings. If this annotation is used, it should be applied to the most limited scope and as infrequently as possible. For more information, check the tutorial on annotations or ask in the forum.
Explanation / Answer
stack array:
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;
}
}
For Stack array class:
UnboundedStackArray: O(1)
push: O(1) + ensureExtraCapacity
ensureExtraCapacity: wcs is O(n), bcs is O(1)
top: O(1)
pop: O(1)
depth: O(1)
toString: O(n)
----
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;
}
}
}
Stack linked list:
UnboundedStackLinkedList: O(1)
push: O(1)
Again, it looks like the functionality is incorrect
top: O(1) + getLinkAtPos
getLinkAtPos: O(n)
pop: O(n)
depth: O(1)
toString: O($n^2$)
This could be much more efficient.
If you create a stack, you only have to keep track of the top item. Each time you push, the top item gets replaced by the new item and the next linked item of the new item is the old top. Each time you pop, the top item gets popped and its reference it set as the new top. The only method that would be more than O(1) would be the toString() method.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.