Download and import the following pieces of code into your project folder: Playi

Question

Download and import the following pieces of code into your project folder:

PlayingCard.java

CardDeck.java

CardDeckList.java

TestCardDeck.java

Once you know that it is all running, your job is to create a new class that will implement the CardDeck interface using a Stack instead of an ArrayList. Create a new class with the name CardDeckStack but instead of just clicking Finish when you put the class name in, select the Add button next to the Interfaces box. Type CardDeck into the "Choose interfaces" box and click OK, then continue on with creating your class. You should get a skeleton of a class with stubs for all of the methods in the CardDeck interface. Use the code in CardDeckList to fill out the class where appropriate, but replace the ArrayList of PlayingCard objects in the class with a Stack of PlayingCard objects (and remember to use push() and pop() instead of add() and remove() in your code). Modify TestCardDeck to be able to test your stack code. Does your stack code behave differently from the CardDeckList class? How? Indicate the differences in the comment section of your CardDeckStack code (make sure you put a comment header into your code with your names and the date in it).

If you get all of that done, create another CardDeck implementation that uses a Queue instead of a Stack, following the same steps as above. You may run into a small problem using the shuffle() and sort() methods (shuffle and sort expect to pass something of type List to the Collections.shuffle() and Collections.sort() methods, so you will need to cast your Queue object to a List type to use the shuffle method). Does your Queue implementation work differently than the Stack? Does it work differently than the List? Indicate in your comments in the header how it is the same/different from the other two implementations.

Exercise 4

Once you have finished exercies 3, write a second test program that does the following:

Prompts the user for a type of CardDeck to create (queue, stack or list)

Creates a deck of the appropriate type, fills it with cards, shuffles it, and displays it on a single line via toString()

Creates a second deck of the same type, fills it with cards, shuffles it, and displays it on a single line via toString()

Piles the two decks together by picking one deck, taking all of the cards off of it one at a time and adding them to the second deck. When the final large deck is assembled, display it on a single line using toString()

Shuffle the larger deck

Create an empty deck of the same type as the above decks

Deal out the cards one at a time, displaying them one per line as with the TestCardDeck code, and adding them to the empty deck

When the large deck is empty, display the contents of the large deck (should be empty) and the contents of the "discard" deck (which should now have all of the cards) each on their own line

Sort the discard deck and display it on a line of its own

You should only have to write one piece of code that can use CardDeckList, CardDeckQueue or CardDeckStack as determined by the input from the user. Make use of the fact that all of these classes implement the CardDeck interface in your code.

Explanation / Answer

/******************************************************************************
* Compilation: javac LinkedStack.java
* Execution: java LinkedStack < input.txt
* Dependencies: StdIn.java StdOut.java
*
* A generic stack, implemented using a linked list. Each stack
* element is of type Item.
*
* % more tobe.txt
* to be or not to - be - - that - - - is
*
* % java LinkedStack < tobe.txt
* to be not that or be (2 left on stack)
*
******************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
* The <tt>LinkedStack</tt> class represents a last-in-first-out (LIFO) stack of
* generic items.
* It supports the usual <em>push</em> and <em>pop</em> operations, along with methods
* for peeking at the top item, testing if the stack is empty, and iterating through
* the items in LIFO order.
* <p>
* This implementation uses a singly-linked list with a non-static nested class for
* linked-list nodes. See {@link Stack} for a version that uses a static nested class.
* The <em>push</em>, <em>pop</em>, <em>peek</em>, <em>size</em>, and <em>is-empty</em>
* operations all take constant time in the worst case.
* <p>
* For additional documentation,
* see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class LinkedStack<Item> implements Iterable<Item> {
private int N; // size of the stack
private Node first; // top of stack

// helper linked list class
private class Node {
private Item item;
private Node next;
}

/**
* Initializes an empty stack.
*/
public LinkedStack() {
first = null;
N = 0;
assert check();
}

/**
* 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(Item item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
assert check();
}

/**
* 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 Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item; // save item to return
first = first.next; // delete first node
N--;
assert check();
return item; // return the saved item
}

/**
* Returns (but does not remove) the item most recently added to this stack.
* @return the item most recently added to this stack
* @throws java.util.NoSuchElementException if this stack is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}

/**
* Returns a string representation of this stack.
* @return the sequence of items in the stack in LIFO order, separated by spaces
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}

/**
* Returns an iterator to this stack that iterates through the items in LIFO order.
* @return an iterator to this stack that iterates through the items in LIFO order.
*/
public Iterator<Item> iterator() { return new ListIterator(); }

// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }

public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}

// check internal invariants
private boolean check() {

// check a few properties of instance variable 'first'
if (N < 0) {
return false;
}
if (N == 0) {
if (first != null) return false;
}
else if (N == 1) {
if (first == null) return false;
if (first.next != null) return false;
}
else {
if (first == null) return false;
if (first.next == null) return false;
}

// check internal consistency of instance variable N
int numberOfNodes = 0;
for (Node x = first; x != null && numberOfNodes <= N; x = x.next) {
numberOfNodes++;
}
if (numberOfNodes != N) return false;

return true;
}

/**
* Unit tests the <tt>LinkedStack</tt> data type.
*/
public static void main(String[] args) {
LinkedStack<String> s = new LinkedStack<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) s.push(item);
else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
}
StdOut.println("(" + s.size() + " left on stack)");
}
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.