Lab #3: Stack, Queue, and StringIntroductionThis lab is split into three parts. The first part concentrates on the implementation of stack. The second part deals with queue. And finally the third part delves into strings.
1. StackIn this problem, your job is to implement theStack_t ADT
as we discussed in class. Download
this code to start with (the
newly added files are stack.h, stack.c ).
You may want to make use of any concrete representation for a linear list. And you may use either the method of boxing a linear list internally (as I did in the class) or write your own code from scratch (as this code does).
2. QueueImplement theQueue_t ADT as we talked about in class. Download
this code to start with (the
newly added files are queue.h and queue.c ).
As in problem 1, you may want to any concrete representation for a linear list. And you may use either the method of boxing a linear list internally (as I did in the class) or write your own code from scratch (as this code does).
Here, this problem makes use of a somewhat different data
structure to
represent a queue. You should read
At any time, a queue is maintained internally as
two separate lists: typedef struct node { poly data; struct node *next; } *node; struct T { node *tail; node *head; int size; };where head points to head part of a queue, whereas
tail points to tail part of queue in reverse order.
For instance, for a queue
q = [2, 5, 7, 3, 4]this data structure looks like: tail = [4, 3, 7] head = [2, 5]and it's easy to see that this equation (invariant) q = head @ rev(tail)holds, where @ stands for list concatenation
and rev reverses a list.
Obviously, when
Question: What about we want to 3. StringYou don't need to write code for the low-level string CDTString_t .
Instead, the code we've offered you
in lib/string.h, lib/string.c . Your job is simply read
the code and make sure you fully understand them. Be able to answer
this question: why should we bother to design such
implementations for string, rather than to use the C's default
char * ?
For the high-level
Note: for this problem, the code uses a polymorphic list to
implement
|