Overview These exercises will allow you to have some practice with the ideas beh
ID: 671237 • Letter: O
Question
Overview
These exercises will allow you to have some practice with the ideas behind the queue and stack data structures. They will also let you have some more practice with the idea of Object-oriented programming.
Objectives
Practice with programming fundamentals
Review of various Java fundamentals (branching, loops, variables, methods, etc.)
Practice with Java classes and Object Oriented Programming
Practice with queue and stack data structures
Practive with using Java interfaces
Exercise 1 Description
You will be examining the behavior of two different (but similar) data structures - the Queue (or FIFO Queue) and the Stack (or LIFO queue). FOR ALL EXERCISES: Make sure you place a comment block at hte top of the code with your name and your partner's name.
integerQueue.java
integerStack.java
Create a ClosedLab06 project folder. Then import both of the files above into that ClosedLab06 project folder. As a reminder, you can do this by selecting File -> Import, then expanding the General folder and selecting "File System". Then browse to the directory where you saved the two files above. (More detailed instructions can be found in the CSE 1223 Closed Lab 01 assignment).
Once you have both pieces of code imported, check to make sure that there are no errors. Both of these files should import "cleanly" so if there are errors you may have had a problem importing them. Once the errors are taking care of, try running integerQueue and see what it does. Then run integerStack and see what it does. Both pieces of code should work properly - trace through the code to make sure that the programs are doing what you think they should be doing. These pieces of code are modified versions of the simple Stack and Queue examples given in the course notes.
Your first task is to modify these pieces of code so that instead of just displaying lists of numbers, they should compute an alternating series using the numbers that you entered. An alternating series switches the sign of the number being added for every other number. For example, if we enter the number 1, 3, 15, 9 then we would compute the alternating series as 1 - 3 + 15 - 9 = 4. Modify the integerQueue code so that it computes the sum of an alternating series of the numbers as they are removed from the queue (so the first number is positive, the second is negative, etc.). Display the alternating series to the screen on a single line. So if the numbers 1, 3, 15, and 9 were entered by the user, the code should display:
Next modify the integerStack code so that it computes the sum of an alternating series of the numbers as they are removed from the stack (so the first number off the stack is positive, the second is negative, etc.). Display the alternating series to the screen on a single line as above. How is the result off the stack different from the result off the queue. In the comments section at the top of your code, explain how this is different than the result you get when using a queue. In addition, there are some cases where the result of using either a stack or a queue will be exactly the same. Indicate in your comment under what conditions the result will be the same. Finally, how could you modify your stack code so that it always gives the same result as your queue code? Indicate that in your comments as well.
Exercise 2 Description
Your next task is to take what we've done with integer queues and stacks and apply it to a new data type. You should make two new classes - stringQueue and stringStack. Using integerQueue and integerStack as a reference, write up two programs that will take a sequence of Strings from the console and place them into either a queue or a stack as appropriate until the user provides a line with XX as the first two characters. Then your code should process the queue (or stack) in the appropriate order, concatenating all of the strings together with a space between them into a single String and then, when the queue is empty, display that string to the console.
Again, consider the differences in the behaviors of the two data structures. When might we want to use a stack for String processing instead of a queue? Put a brief description of the differences between the two pieces of code into the comments of your stringStack code and give an example of when you might need to use a stack.
Exercise 3
Now that you've got the basic ideas of stacks and queues in place, we are going to use them to go beyond the basic data types. Download and import the following pieces of code into your project folder:
PlayingCard.java
CardDeck.java
CardDeckList.java
TestCardDeck.java
These should look familiar. The PlayingCard class here is a fully implemented version of the PlayingCard class that we've been looking at for the past few weeks. The CardDeck and CardDeckList classes are a bit different. CardDeck is an interface, and CardDeckList is a class that implements the CardDeck interface using an ArrayList as its underlying data structure. Import all of these files and run the TestCardDeck code to make sure that it all runs properly.
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 1-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
/**
* integerQueue
*
* A simple program to demonstrate the use of queues
*
* @author Jeremy Morris
* @version 20120923
*/
import java.util.*;
public class integerQueue {
public static void main(String[] args) {
Queue<Integer> myQueue = new LinkedList<Integer>();
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter numbers to store (negative number to quit):");
int newNum = keyboard.nextInt();
while (newNum >=0 ) {
myQueue.add(newNum);
newNum = keyboard.nextInt();
}
System.out.println("Displaying numbers in FIFO order: ");
String altstr = "";
int val = 0;
int i = 0;
while (!myQueue.isEmpty()) {
int head = myQueue.remove();
//compute alternating series
if(i == 0) {
altstr += head;
val = head;
} else if (i %2 ==0 ) {
altstr += "+"+head;
val += head;
} else {
altstr += "-"+head;
val -= head;
}
System.out.print(head+ " ");
i++;
}
System.out.print( "Alternating Series: "+altstr+" = "+val);
}
}
class StringQueue {
public static void main(String[] args) {
Queue<String> myQueue = new LinkedList<String>();
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter a String to store (Enter XX as the first two characters to quit):");
String newVal = keyboard.next();
while (newVal!= null && !newVal.trim().startsWith("XX") ) {
myQueue.add(newVal);
newVal = keyboard.next();
}
System.out.println("Displaying numbers in FIFO order: ");
String str = "";
int i = 0;
while (!myQueue.isEmpty()) {
String head = myQueue.remove();
//compute alternating series
str += head;
System.out.print(head+ " ");
i++;
}
System.out.print( "Queue: "+str);
}
}
/**
* integerStack
*
* A simple program to demonstrate the use of stacks
*
* @author Jeremy Morris
* @version 20120923
*
* Q) Difference b/w alternating serieses of Queue and stack
* Ans:- The value obtained in stack is of opposite sign of tha value obtained in the queue.
* Its due to difference in where the new values are inserted and from where the values are removed in queue and stack.
*
* Q) under what conditions the result will be the same
* Ans: 1) When sum of alternate values are same or all the values are same then the result will be 0 in both cases
*
* Q)how could you modify your stack code so that it always gives the same result as your queue code?
* Ans: The alternate series in stack code need to be modified such that the order of applying addition and division to be in reverse order.
* i.e in current way first addition , then subtraction and repeating this for other terms. Change this to first subtraction and next addition and so on.
*/
import java.util.*;
public class integerStack {
public static void main(String[] args) {
Stack<Integer> myStack = new Stack<Integer>();
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter numbers to store (negative number to quit):");
int newNum = keyboard.nextInt();
while (newNum >=0 ) {
myStack.push(newNum);
newNum = keyboard.nextInt();
}
String altstr = "";
int val = 0;
int i = 0;
System.out.println("Displaying numbers in LIFO order: ");
while (!myStack.isEmpty()) {
int head = myStack.pop();
//compute alternating series
if(i == 0) {
altstr += head;
val = head;
} else if (i %2 ==0 ) {
altstr += "+"+head;
val += head;
} else {
altstr += "-"+head;
val -= head;
}
System.out.print(head+ " ");
i++;
}
System.out.print( "Alternating Series: "+altstr+" = "+val);
}
}
/*
*
* Q) When might we want to use a stack for String processing instead of a queue?
* Ans) When we want to reverse a string, we can use stack by inputting characters of the string
*
* Put a brief description of the differences between the two pieces of code into the comments of your stringStack code
* Ans) Queue displays the string as the way it entered and stack in the reverse order of entering the values.
* and when we want to get reverse of a string we can use stack
*/
class StringStack1 {
public static void main(String[] args) {
Stack<String> myStack = new Stack<String>();
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter numbers to store (negative number to quit):");
String newVal = keyboard.next();
while (newVal!= null && !newVal.trim().startsWith("XX")) {
myStack.push(newVal);
newVal = keyboard.next();
}
String str = "";
int val = 0;
int i = 0;
System.out.println("Displaying numbers in LIFO order: ");
while (!myStack.isEmpty()) {
String head = myStack.pop();
//compute alternating series
str += head;
System.out.print(head+ " ");
i++;
}
System.out.print( "Stack: "+str);
}
}
///////////////////sample output of integer queue//////////////////////
Enter numbers to store (negative number to quit):
1
2
3
5
-1
Displaying numbers in FIFO order:
1 2 3 5 Alternating Series: 1-2+3-5 = -3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.