Lab #3: Stack, Queue, and String

Introduction

This 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. Stack

In this problem, your job is to implement the Stack_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. Queue

Implement the Queue_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 queue.c and we briefly explain the key idea here.

At any time, a queue is maintained internally as two separate lists: head and tail. The data structure for this reads: 

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 enQueue a queue q, we should insert at the head of the list pointed by tail. And when deQueue, we should delete the head of the list pointed by head.

Question: What about we want to deQueue a queue, but head is empty?

3. String

You don't need to write code for the low-level string CDT String_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 Str_t ADT, you should download this code to start with (str.h, str.c).

Note: for this problem, the code uses a polymorphic list to implement allStrs, which is correct but may be too slow.