java This week, we\'ll consolidate our understanding of data structures involvin
ID: 3594095 • Letter: J
Question
java
This week, we'll consolidate our understanding of data structures involving nodes and links between them.
Specifically, we're going to concentrate on implementation of the Deque (aka Dequeue) data structure, and a simple application. Feel free to use notes/code from the earlier labs (especially LinkedQueue.java), in addition to ideas from you instructor/TA and neighbors.
If you already successfully implemented the Deque in the previous lab, this will be a relatively short day for you. We're covering Deque again because I want to be certain that we all understand references between nodes, and how to manipulate them.
Deque. A double-ended queue or deque (pronounced "deck") is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure. Create a generic data type Deque, based on the LinkedQueue.java code from the previous lab, that implements the following API:
Corner cases. Throw a java.lang.NullPointerException if the client attempts to add a null item; throw a java.util.NoSuchElementException if the client attempts to remove an item from an empty deque; throw a java.lang.UnsupportedOperationException if the client calls the remove() method in the iterator; throw a java.util.NoSuchElementException if the client calls the next() method in the iterator and there are no more items to return.
Performance requirements. Your deque implementation must support each deque operation (including construction) in constant worst-case time and use space linear in the number of items currently in the deque. It is possible to implement such a deque with a circular array (beyond the scope of this class), but here, we'll do it with a doubly-linked list (in which each node has a "next" and "prev" link). If you completed your Deque implementation in the previous lab, you may reuse it here.
Your Deque implementation should include an iterator that supports each operation (including construction) in constant worst-case time. Your main function should include code that tests this with a sequence of add and remove actions.
FixedSizedStack. Frankly, Deques are more likely to be valuable as an instrument of instruction (teaching you about linked structures, so you're prepared to understand graphs and trees) than in code you'll write in the future. I know of only a couple of real-world applications:
the A-Steal job scheduling algorithm (read about it here, if interested)
A fixed sized stack, in which you may push and pop off the front of the stack as usual, but you also remove items off the back of the stack once capacity has been reached.
Today, you will implement the second one in FixedSizedStack.java, which will be a client of the Deque.
This class should primarily involve pass-through code, making liberal use of the Deque API. For example, a call to push will simply call addFirst, then possibly removeLast.
Client. You'll now write a client program called FSclient.java. It should use (and test) your implementations of the two classes above. Your code should work like the Unit Test from the ResizingArrayStack from Lab2, so that it takes a sequence of tokens like:
treating non-dash tokens as "push" requests, and dash characters as pop requests. It should run like:
The result of such a command should be (a) the stack is limited to size 4, so it should never contain more than 4 items, and (b) on each pop request, the popped term should be printed. You may use the main function from ResizingArrayStack as a guide:
Once you have implemented it, test with several input files, to ensure that it is working as expected. How does it deal with pop requests on an empty stack? You may find it useful to test the contents of the FS-stack after each action, using its iterator.
Explanation / Answer
Given below is the code for the question. Please don't forget to rate the answer if it helped. Thank you.
To indent code, select code by pressing Ctrl+A and then Ctrl+i
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class Deque<Item> implements Iterable<Item> {
class Node
{
Item data;
Node prev;
Node next;
Node(Item t)
{
this(t, null, null);
}
Node(Item t, Node pr, Node nx)
{
data = t;
prev = pr;
next = nx;
}
}
private Node head, tail;
private int size;
public Deque() // construct an empty deque
{
head = null;
tail = null;
size = 0;
}
public void addFirst(Item item) // add the item to the front
{
if(item == null)
throw new NullPointerException("null not allowed");
Node n = new Node(item, null, head);
if(head != null)
head.prev = n;
head = n;
if(tail == null)
tail = n;
size++;
}
public void addLast(Item item) // add the item to the end
{
if(item == null)
throw new NullPointerException("null not allowed");
Node n = new Node(item, tail, null);
if(tail != null)
tail.next = n;
tail = n;
if(head == null)
head = n;
size++;
}
public Item removeFirst() // remove and return the item from the front
{
if(isEmpty())
throw new NoSuchElementException("deque is empty");
Item val = head.data;
head = head.next;
size --;
if(head != null)
{
head.prev = null;
}
else //now queue is empty
tail = null;
return val;
}
public Item removeLast() // remove and return the item from the end
{
if(isEmpty())
throw new NoSuchElementException("deque is empty");
Item val = tail.data;
tail = tail.prev;
size --;
if(tail != null)
tail.next = null;
else //now queue is empty
head = null;
return val;
}
public boolean isEmpty() // is the deque empty?
{
return size == 0;
}
public int size() // return the number of items on the deque
{
return size;
}
public Iterator<Item> iterator() // return an iterator over items in order from front to end
{
return new DequeIterator();
}
class DequeIterator implements Iterator<Item>
{
Node current;
public DequeIterator() {
current = head;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
if(!hasNext())
throw new NoSuchElementException("deque is empty");
Item val = current.data;
current = current.next;
return val;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
public String toString()
{
String str = "";
Node n = head;
while(n != null)
{
str += n.data.toString() + " ";
n = n.next;
}
str += " ";
return str;
}
public static void main(String[] args) // unit testing (required)
{
Deque<Integer> d = new Deque<>();
for(int i = 1; i <= 5; i++)
{
System.out.println("addLast(" + i + ")");
d.addLast(i);
}
System.out.println("displaying using iterator... ");
Iterator<Integer> it = d.iterator();
while(it.hasNext())
System.out.print(it.next()+ " " );
System.out.println();
for(int i = 6; i <= 10; i++)
{
System.out.println("addFirst(" + i + ")");
d.addFirst(i);
}
System.out.println(d);
for(int i = 0; i < 4; i ++)
{
System.out.println("removeFirst() = " + d.removeFirst());
}
while(!d.isEmpty())
{
System.out.println("removeLast() = " + d.removeLast());
}
}
}
output
addLast(1)
addLast(2)
addLast(3)
addLast(4)
addLast(5)
displaying using iterator...
1 2 3 4 5
addFirst(6)
addFirst(7)
addFirst(8)
addFirst(9)
addFirst(10)
10 9 8 7 6 1 2 3 4 5
removeFirst() = 10
removeFirst() = 9
removeFirst() = 8
removeFirst() = 7
removeLast() = 5
removeLast() = 4
removeLast() = 3
removeLast() = 2
removeLast() = 1
removeLast() = 6
import java.util.Iterator;
public class FixedSizedStack<Item> implements Iterable<Item> {
private int capacity;
Deque<Item> deque;
public FixedSizedStack(int c) // construct an empty FS-stack, with capacity c
{
capacity = c;
deque= new Deque<Item>();
}
public boolean isEmpty() // is it empty?
{
return deque.isEmpty();
}
public int size() // return the number of items on the FS-stack
{
return deque.size();
}
public void push(Item item) // add the item to the front, and remove an item from the back if capacity is reached
{
if(deque.size() == capacity) //already stack reached its fixed capacity
deque.removeLast();
deque.addFirst(item);
}
public Item pop() // remove the item from the front
{
return deque.removeFirst();
}
public Iterator<Item> iterator() // return an iterator over items in order from front to end
{
return deque.iterator();
}
private static void display(FixedSizedStack stk)
{
System.out.print("Stack contents: ");
Iterator it = stk.iterator();
while(it.hasNext())
System.out.print(it.next() + " ");
System.out.println();
}
public static void main(String[] args) // unit testing (required)
{
FixedSizedStack<String> stk = new FixedSizedStack(4);
String[] words = {"the", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog"};
for(int i = 0; i < words.length; i++)
{
System.out.println("Pushing '" + words[i] + "'");
stk.push(words[i]);
display(stk);
}
while(!stk.isEmpty())
{
System.out.println("Stack size: " + stk.size());
System.out.println("Popped " + stk.pop());
}
}
}
output
Pushing 'the'
Stack contents: the
Pushing 'quick'
Stack contents: quick the
Pushing 'brown'
Stack contents: brown quick the
Pushing 'fox'
Stack contents: fox brown quick the
Pushing 'jumped'
Stack contents: jumped fox brown quick
Pushing 'over'
Stack contents: over jumped fox brown
Pushing 'the'
Stack contents: the over jumped fox
Pushing 'lazy'
Stack contents: lazy the over jumped
Pushing 'dog'
Stack contents: dog lazy the over
Stack size: 4
Popped dog
Stack size: 3
Popped lazy
Stack size: 2
Popped the
Stack size: 1
Popped over
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.