Create a Stack and Queue using a linked list implementation. The LinkedQueue cla
ID: 3674033 • Letter: C
Question
Create a Stack and Queue using a linked list implementation.
The LinkedQueue class must have the following features:
At least one primitive variable
At least two ListNode variables: front and rear
A LinkedQueueConstructor initializing the primitive and ListNode variables
The following Methods:
//Adds data to the rear of the queue
public void enqueue(int data)
//Removes the data at the front of the queue and returns a reference to it.
//Throws an Eception if the queue is empty
public int dequeue() throws Exception
//Returns a reference to the data at the front of the queue.
//The data is not removed from the queue. Throws an Exception if the queue is empty.
public int first() throws Exception
//Returns true if this queue is empty and false otherwise
public boolean isEmpty()
//Returns the number of elements in this queue
public int size()
//Return a string representation of this queue
public String toString()
The LinkedStack class must have the following features:
At least one primitive variable
At least one ListNode variable: top
A LinkedStact Constructor initializing the primitive and ListNode variables
The following Methods:
//Removes the data at the top of this stack and returns a reference to it.
//Throws as EmptyStackException of the Stack is empty
public int pop() thros EmptyStackException
//Returns a reference to the data at the top of this stack.
//The data is not removed from the stack.
//Throws an EmptyStackException if the stack is empty
public int peek() throws EmptyStackException
//Returns true if this stack is empty and false otherwise
public boolean isEmpty()
//Returns the number of elements in the stack
public int size()
//Returns a string representation of this stack.
public String toString()
Explanation / Answer
package datastructures.queues;
import java.util.Iterator;
import datastructures.lists.*;
/**
* A LinkedQueue is a queue which uses a DoublyLinkedList as the underlying implementation.
* Such a queue never needs data resizing and can grow as long as the system allows it to.
* We use a DoublyLinkedList instead of a LinkedList for the underlying implementation such that we have
* constant time enqueueings and dequeuings (a singly linked list would provide linear time for one
* of the two operations).
*
* @param <T> The type of Object contained within the LinkedQueue.
*/
public class LinkedQueue<T> implements Queue<T>{
private DoublyLinkedList<T> data;
/**
* Constructor simply initializes the data structure.
*/
public LinkedQueue(){
data = new DoublyLinkedList<T>();
}
/**
* Copy constructor initializes the current object as a carbon copy
* of the parameter object.
* @param oqueue The queue to copy the elements from.
*/
public LinkedQueue(Queue<T> oqueue){
/* Since we allow copying from any type that implements the
* Queue<T> interface, we cannot straightforwardly do a downcasting of the parameter
* and call the copy constructor for DoublyLinkedLists, because the parameter is not
* guaranteed to be a DoublyLinkedList (the downcasting is unsafe).
*/
data = new DoublyLinkedList<T>();
for(T el: oqueue)
enqueue(el);
}
/**
* Standard equals() method. Checks whether two Queues have the exact same elements
* at the same order.
* @param other The Object to compare this queue to.
* @return true If the two queues are equal as per the contract established above.
*/
@Override
public boolean equals(Object other){
if(other == null)
return false;
if(!(other instanceof Queue<?>))
return false;
@SuppressWarnings("unchecked")
Queue<T> oqueue = (Queue<T>)other;
if(size() != oqueue.size())
return false;
Iterator<T> ito = oqueue.iterator(), itc = iterator();
while(ito.hasNext())
if(!ito.next().equals(itc.next()))
return false;
return true;
}
/** Overriding of the iterator() method, required for Iterables.
* In this implementation of iterator(), the accessors of the method returned may throw
* a ConcurrentModificationException if the user tries to further traverse the queue
* after removing an element. This is similar to what the Java Standard Library Collections are
* doing and it's there because typically removal of an element leaves it in an inconsistent state
* w.r.t further traversing its elements.
* @return An Iterator<T> which can be used to scan the elements in the queue in a linear order.
*/
@Override
public Iterator<T> iterator() {
return data.iterator();
}
/**
* Standard toString() method. Returns all the elements of the queue in a Stringified representation.
* @return A String-like representation of the object.
*/
@Override
public String toString(){
return data.toString(); // We use the exact same Stringified representation for Queues.
}
@Override
public void enqueue(T element) {
data.pushBack(element);
}
@Override
public T dequeue() throws EmptyQueueException {
T retVal = null;
try {
retVal = data.getFirst();
data.remove(0);
} catch (EmptyListException e) {
throw new EmptyQueueException("dequeue(): Queue is empty.");
} catch(IllegalListAccessException exc){
// Dummy catchblock, since this type of exception will never be generated.
}
return retVal;
}
@Override
public T first() throws EmptyQueueException {
try {
return data.getFirst();
}catch(EmptyListException exc){
throw new EmptyQueueException("first(): Queue is empty.");
}
}
@Override
public int size() {
return data.size();
}
@Override
public boolean isEmpty() {
return (data.size() == 0);
}
@Override
public void clear() {
data.clear();
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
package datastructures.stacks;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import datastructures.lists.*;
/** LinkedStack is a Stack generic ADT which uses a LinkedLinearList
* as its underlying implementation. It is thus a purely dynamic data
* structure which does not rely on expensive resizing of the underlying
* storage. We improve efficiency of the basic stack operations by assuming
* that the top of the Stack is located at the front of the underlying List.
*
*/
public class LinkedStack<T> implements Stack<T> {
private List<T> data;
protected boolean modificationFlag;
/** Constructor initializes the underlying store. */
public LinkedStack(){
data = new LinkedList<T>();
modificationFlag = false;
}
/** Copy constructor. Initializes the current element with the data contained
* in the parameter object.
* @param other The Stack<T> object to compare ourselves to. Notice that we allow for copying
* any kind of Stack.
*/
public LinkedStack(Stack<T> other){
if(other == null)
return;
data = new LinkedList<T>();
for(T el: other)
data.pushFront(el);
modificationFlag = false;
}
/**
* Standard equals() method. Two ArrayStacks are considered to be equal
* if they contain the exact same elements at the exact same positions.
* @param other The object to compare the current object to.
* @return true if the objects are considered "equal", with equality established
* by the contract above.
*/
@Override
public boolean equals(Object other){
if(!(other instanceof Stack<?>))
return false;
@SuppressWarnings("unchecked")
Stack<T> ostack = (Stack<T>)other;
if(size() != ostack.size())
return false;
// Stacks, being Iterables, expose iterators!
Iterator<T> ito = ostack.iterator(), itc = this.iterator();
while(ito.hasNext())
if(!ito.next().equals(itc.next()))
return false;
return true;
}
@Override
public T pop() throws EmptyStackException {
T top = null;
try {
top = data.getFirst();
data.remove(0);
} catch(EmptyListException exc){
throw new EmptyStackException("pop(): Stack was empty!");
} catch(IllegalListAccessException exc){
// The compiler complains if we do not add a dummy catchblock for remove().
}
modificationFlag = true;
return top;
}
@Override
public void push(T element) {
data.pushFront(element); // O(1) operation
modificationFlag = true;
}
@Override
public T peek() throws EmptyStackException {
T top = null;
try {
top = data.getFirst();
} catch(EmptyListException exc){
throw new EmptyStackException("peek(): Stack was empty!");
}
return top;
}
@Override
public int size() {
return data.size();
}
@Override
public boolean empty() {
return data.size() == 0;
}
@Override
public void clear() {
data.clear();
modificationFlag = true;
}
@Override
public String toString(){
String answer = "";
for(T el: data)
answer += ("|" + el + "| ");
answer += "___"; // Good practice to never add extra newline in toString(), since people might println() the object anyway...
return answer;
}
@Override
public Iterator<T> iterator() {
return new LinkedStackIterator<T>();
}
class LinkedStackIterator<T2> implements Iterator<T2>{
private int currInd;
LinkedStackIterator(){
currInd = data.size() - 1;
modificationFlag = false;
}
@Override
public boolean hasNext() {
// We have another element coming our way
// if we query for it and don't receive an
// exception from the underlying List.
try {
data.get(currInd);
} catch(EmptyListException | IllegalListAccessException e ) { // Thank you Java 7
return false;
}
return true;
}
@SuppressWarnings("unchecked")
@Override
public T2 next() throws ConcurrentModificationException{
if(modificationFlag)
throw new ConcurrentModificationException("next(): Stack was modified while accessing it through iterator.");
T2 retVal = null;
try {
retVal = (T2) data.get(currInd--);
} catch (EmptyListException | IllegalListAccessException e) {
// Dummy
}
return retVal;
}
@Override
public void remove() throws IllegalStateException{
if(currInd == data.size() - 1)
throw new IllegalStateException("Need at least one call to next() before attempting removal.");
try {
data.remove(currInd + 1);
} catch (IllegalListAccessException e) {}
}
}
}