thanks in advance! \"We don\'t see the difference between stacks and queues,\" t
ID: 3593042 • Letter: T
Question
thanks in advance!
"We don't see the difference between stacks and queues," the Galaxers begin, "since our add0 method for both looks exactly the same" public void add (T item) ensureSpace); array[size] - item; size++ That's because with stacks, you always add to the top, and with queues, to the rear. Since we're using the end of the array to represent both locations, the method will be the same. The difference lies in how they remove items. With a stack, it's always from the same end (the top), with a queue, it's from the opposite end (the front). Let me write the two array-based versions for you...." l/ removing from stack (also known as pop0) public T remove0)Explanation / Answer
Please find my implementation if it is implemented using NODE class.
// Stack
import java.util.NoSuchElementException;
class Stack<T> {
private int n; // size of the stack
private Node first; // top of stack
// helper linked list class
private class Node {
private T item;
private Node next;
}
/**
* Initializes an empty stack.
*/
public Stack() {
first = null;
n = 0;
}
/**
* Is this stack empty?
* @return true if this stack is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in the stack.
* @return the number of items in the stack
*/
public int size() {
return n;
}
/**
* Adds the item to this stack.
* @param item the item to add
*/
public void push(T item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
n++;
}
/**
* Removes and returns the item most recently added to this stack.
* @return the item most recently added
* @throws java.util.NoSuchElementException if this stack is empty
*/
public T remove() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
T item = first.item; // save item to return
first = first.next; // delete first node
n--;
return item; // return the saved item
}
}
######
Queue
import java.util.NoSuchElementException;
class LinkedQueue<T> {
private int n; // number of elements on queue
private Node first; // beginning of queue
private Node last; // end of queue
// helper linked list class
private class Node {
private T item;
private Node next;
}
/**
* Initializes an empty queue.
*/
public LinkedQueue() {
first = null;
last = null;
n = 0;
}
/**
* Is this queue empty?
* @return true if this queue is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this queue.
* @return the number of items in this queue
*/
public int size() {
return n;
}
/**
* Returns the item least recently added to this queue.
* @return the item least recently added to this queue
* @throws java.util.NoSuchElementException if this queue is empty
*/
public T peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
/**
* Adds the item to this queue.
* @param item the item to add
*/
public void add(T item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
n++;
}
/**
* Removes and returns the item on this queue that was least recently added.
* @return the item on this queue that was least recently added
* @throws java.util.NoSuchElementException if this queue is empty
*/
public T remove() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
T item = first.item;
first = first.next;
n--;
if (isEmpty()) last = null; // to avoid loitering
return item;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.