week 1: Stack • Create a class that acts as a doubly linked list node. It should
ID: 3684965 • Letter: W
Question
week 1: Stack
• Create a class that acts as a doubly linked list node. It should contain all the required data fields, at least 1 constructor, and a method that prints the hero’s information.
• Create a data file with hero information. Each line should be of the following format: heroName Nemesis Time where Nemesis is 1 for the nemesis and 0 for everyone else and Time is in hours.
• Modify your list class to include the following stack methods: push, pop, popAll, printList. • Create a class that contains a main method for testing/demonstrating.
• In your main method, thoroughly test/demonstrate the methods from your list that you’ve implemented. You should be able to read your data file and use it to push heroes. hint: I find it helpful to use the scanner class for this but you can use something else if you prefer. You can find the scanner class documentation here: http://docs.oracle.com/javase/1.5.0/docs/api/java/util/Scanner.html.
week 2: Queue
• create a class that implements a doubly linked list with the following methods: enqueue, dequeue, dequeueAll.
• In your main method, thoroughly test/demonstrate the methods that you’ve implemented. You should be able to read your data file and use it to push heroes.
• Add the ability to switch from queue mode to stack mode. Be able to queue heroes until the nemesis is enqueued then switch to stack mode until the nemesis is popped then switch back to queue mode. hint: You may want to make helper functions that keep track of your state. For instance, capture might call push/enqueue appropriately when heroes are added and feedToSharks might pop/dequeue appropriately when heroes are removed.
• In your main method, thoroughly test/demonstrate the methods from your list that you’ve implemented. You should be able to read your data file and use it to enqueue heroes. hint: You may want to manually call your capture and feedToSharks methods to test/demonstrate that your class switches modes properly. week 3: Simulation — Complete version due • Modify your data file so that its first line contains a single integer: the number of sharks • Modify your code where you read your data file so that the first line is parsed as the number of sharks and subsequent lines are interpreted as containing heroes.
• Modify your main class so that it keeps track of time since the sharks have been fed & the number of sharks. When it reads in hero information, it should enqueue until the nemesis shows up, then push until the nemesis is fed to the sharks, then revert to enqueueing. Every Assumptions: • The client thinks 1 hour the longest he can afford to make his monologue. On the one hand, he has lots of gloating to do. But if he talks too long, his nemesis will probably whip out her can of shark repellant.
• The shark tank should contain an integer number of laser-sharks. You can’t have half a laser shark. • Your client has only one nemesis. • Assume that the sharks start hungry and eat the first hero right away. Also assume that sharks need to be fed every 8 hours but that they share. So 1 shark would eat every 8 hours, 2 sharks would eat every 4 hours, etc.
• Also assume that the sharks eat a bit extra if they are starving to make up for lost time. If there is 1 shark and a hero takes 9 hours to show up, the shark will want to eat in 7 hours. Either way, they eat every 8 hours if possible.
• You can make your own assumptions about heroes. Come up with a list of heroes. Pick a nemesis. Decide how long it would take each hero to find out someone is missing and get to the lair.
Explanation / Answer
doubly linked list with deque:
#include <stdlib.h>
#include <assert.h>
#include "deque.h"
struct elt {
int value;
struct elt *next[NUM_DIRECTIONS];
};
struct deque {
struct elt *head[NUM_DIRECTIONS];
};
Deque
dequeCreate(void)
{
Deque d;
d = malloc(sizeof(*d));
if(d) {
d->head[FRONT] = d->head[BACK] = 0;
}
return d;
}
void
dequePush(Deque d, int direction, int value)
{
struct elt *e;
assert(direction == FRONT || direction == BACK);
e = malloc(sizeof(*e));
if(e == 0) abort(); /* kill process on malloc failure */
e->next[direction] = d->head[direction];
e->next[!direction] = 0;
e->value = value;
if(d->head[direction]) {
d->head[direction]->next[!direction] = e;
}
d->head[direction] = e;
if(d->head[!direction] == 0) {
d->head[!direction] = e;
}
}
int
dequePop(Deque d, int direction)
{
struct elt *e;
int retval;
assert(direction == FRONT || direction == BACK);
e = d->head[direction];
if(e == 0) return EMPTY_QUEUE;
d->head[direction] = e->next[direction];
if(d->head[direction] != 0) {
d->head[direction]->next[!direction] = 0;
} else {
d->head[!direction] = 0;
}
retval = e->value;
free(e);
return retval;
}
int
dequeEmpty(Deque d)
{
return d->head[FRONT] == 0;
}
void
dequeDestroy(Deque d)
{
while(!dequeEmpty(d)) {
dequePop(d, FRONT);
}
free(d);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.