We're going to implement a data structure called Squeue , because its a bit like both a Stack and a Queue, that allows new elements to be added / removed / peeked at both ends of the list.
It is essential that you use the EXACT function prototypes provided.
We're going to implement our Squeue by using Nodes that have links in both directions (forwards and backwards), plus we are going to keep two special pointers: one to the first element and one to the last element. The following shows the structs we expect.
struct Node{
char* val;
struct Node* next;
struct Node* prev;
};
typdef struct{
struct Node* first;
struct Node* last;
} Squeue;
You must implement the Squeue using the exact structs above. We have provided you with a header file that contains all the signatures of all functions you need to implement.
void initSqueue (Squeue **squeue);
bool isEmpty (const Squeue *squeue);
void addFront (Squeue *squeue, char *val);
void addBack (Squeue *squeue, char *val);
void leaveFront (Squeue *squeue);
char* peekBack (const Squeue *squeue);
void leaveBack (Squeue *squeue);
char* peekFront (const Squeue *squeue);
void print (const Squeue * squeue, char direction);
void nuke (Squeue *squeue);
void mergeFront(Squeue *squeue, char direction);
void mergeBack(Squeue *squeue, char direction);
void reverse(Squeue *squeue);
void destroySqueue(Squeue **squeue);
The following is an example of a main program that shows what is expected from each function.
int main1 () {
Squeue *s1 = NULL;
initSqueue (&s1);
addFront (s1, "alpha");
addFront (s1, "beta");
addFront (s1, "gamma");
addBack (s1, "delta");
printf("This prints \"gamma beta alpha delta\" across four lines
with a tab before each element, and preceded by
\"squeue is:\" on its own line:\n");
print (s1, 'f');
printf("This prints \"delta alpha beta gamma\" across four lines
with a tab before each element, and preceded by
\"squeue is:\" on its own line:\n");
print (s1, 'r');
mergeFront(s1, 'f');
printf("This prints \"gammabeta alpha delta\" across three lines
with a tab before each element, and preceded by
\"squeue is:\" on its own line:\n");
print(s1, 'f');
mergeBack(s1, 'r');
printf("This prints \"gammabeta deltaalpha\" across two lines
with a tab before each element, and preceded by
\"squeue is:\" on its own line:\n");
print(s1, 'f');
leaveFront (s1);
printf("This prints \"deltaalpha\" in one line
with a tab before each element, and preceded by
\"squeue is:\" on its own line:e\n");
print(s1, 'f');
addFront(s1, "zeta");
addFront(s1, "eta");
leaveBack (s1);
printf("This prints \"eta zeta\" across two lines
with a tab before each element, and preceded by
\"squeue is:\" on its own line:\n");
print(s1, 'f');
printf("This prints \"eta zeta\" in one line \n");
printf("%s %s\n", peekFront(s1), peekBack(s1));
printf("This nuke has no output, but is good form to call when done\n");
nuke (s1);
printf("This assertion should succeed\n");
assert (isEmpty (s1));
printf("Illegal direction should cause error message\n");
print (s1, 'k');
addBack (s1, "alpha");
addBack (s1, "beta");
addBack (s1, "gamma");
reverse(s1);
printf("This prints \"gamma beta alpha\" across two lines
with a tab before each element, and preceded by \"squeue is:\"
on its own line:\n");
print(s1, 'f');
//we will always call this for any squeue we test with so make sure
//it is implemented correctly
//to free any allocated memory
destroySqueue(&s1);
return 0;
}
void initSqueue (Squeue **squeue);
initSqueue initializes the given squeue to an empty squeue. After calling initSqueue on a given squeue , we should be able to add elements to that squeue by calling addFront or addBack .
bool isEmpty (const Squeue *squeue);
isEmpty checks if the given squeue is empty. Returns true if it is empty and false if not.
void addFront (Squeue *squeue, char* val);
addFront adds the given string (i.e., val ) to the front of the given squeue. Make sure you adjust all pointers of the squeue appropriately. You need to dynamically allocate memory for the new string. You cannot assume any maximum size for the string.
void addBack (Squeue *squeue, char* val);
addBack adds the given string (i.e., val) to the back of the given squeue. Make sure you adjust all pointers of the squeue appropriately. You need to dynamically allocate memory for the new string. You cannot assume any maximum size for the string.
void leaveFront (Squeue *squeue);
leaveFront deletes the first element from the front of the given squeue. Make sure you adjust all pointers of the squeue appropriately and delete any unneeded struct instances. The first line of the function should be: assert (!isEmpty(s)); to ensure that you don't try accessing elements from an empty squeue.
void leaveBack (Squeue *squeue);
leaveBack deletes the last element at the back of the given squeue. Make sure you adjust all pointers appropriately and delete any unneeded struct instances. The first line of the function should be: assert (!isEmpty(s)); to ensure that you don't try accessing elements from an empty squeue.
char* peekFront (const Squeue *squeue);
peekFront returns the value of the first element from the front of the squeue without changing the squeue. The first line of the function should be: assert (!isEmpty(s)); to ensure that you don't try accessing elements from an empty squeue.
char* peekBack (const Squeue *squeue);
peekBack returns the value of the last element from the back of the squeue without changing the squeue. The first line of the function should be: assert (!isEmpty(s)); to ensure that you don't try accessing elements from an empty squeue.
void print (const Squeue *squeue, char direction);
print takes a Squeue and a single char that represents the direction, f for forward and r for reverse, and then prints the squeue in the desired direction. If the direction passed in is not 'f' or 'r', then print the following message to stderr:
Error, illegal direction < entered direction>. Note that < entered direction> must be replaced by the direction passed in as an arugment. For example, if the function was called with direction b , the message printed to stderr will be Error, illegal direction b . If an illegal direction is detected, just print that message; do not try to print the contents of squeue , and do not exit the program or make an assertion that could cause the program to abort. To output elements of the stack, the function prints squeue is: on a line, followed by each element on its own line. Each element is preceded with a tab. See example code.
void nuke (Squeue *squeue);
nuke takes a Squeue , deletes all of the internal Nodes, and sets the first and last pointers of the Squeue instance to NULL .
void mergeFront(Squeue* squeue, char direction);
mergeFront takes a Squeue and a single char that represents the direction, f for forward and r for reverse. It concatenates the two strings contained in the first two nodes of the squeue in the desired direction, stores the concatenated string in the first node, and then deletes the second node. See the provided main function example above to understand what mergeFront does. Note that it is an error if you call mergeFront on a squeue with less than 2 nodes. You should have an assert to check for this. If the direction passed in is not 'f' or 'r', then print the following message to stderr:
Error, illegal direction < entered direction> . Note that < entered direction> must be replaced by the direction passed in as an arugment. For example, if the function was called with direction b , the message printed to stderr will be Error, illegal direction b . If an illegal direction is detected, just print that message; do not try to do the merge, and do not exit the program or make an assertion that could cause the program to abort.
void mergeBack(Squeue* squeue, char direction);
mergeBack takes a Squeue and a single char that represents the direction, f for forward and r for reverse. It concatenates the two strings contained in the last two nodes of the squeue in the desired direction, stores the concatenated string in the node before last, and then deletes the last node. See the provided main function example above to understand what mergeBack does. Note that it is an error if you call mergeBack on a squeue with less than 2 nodes. You should have an assert to check for this. If the direction passed in is not 'f' or 'r', then print the following message to stderr:
Error, illegal direction < entered direction> . Note that < entered direction> must be replaced by the direction passed in as an arugment. For example, if the function was called with direction b , the message printed to stderr will be Error, illegal direction b . If an illegal direction is detected, just print that message; do not try to do the merge, and do not exit the program or make an assertion that could cause the program to abort.
void reverse(Squeue* squeue);
reverses the elements in the given squeue. If the squeue was a->b->c->d , where first points to a and last points to d , calling reverse would change the squeue contents to d->c->b->a , and make first point to d and last point to a .
void destroySqueue(Squeue **squeue);
destroySqueue safely deletes all members of the given squeue as well as any memory allocated for squeue. After calling destroySqueue on a given squeue , that squeue would point to NULL .