diff options
Diffstat (limited to 'src/01/01b/stack_test.c')
| -rw-r--r-- | src/01/01b/stack_test.c | 127 |
1 files changed, 7 insertions, 120 deletions
diff --git a/src/01/01b/stack_test.c b/src/01/01b/stack_test.c index b34c191..457f656 100644 --- a/src/01/01b/stack_test.c +++ b/src/01/01b/stack_test.c @@ -1,124 +1,5 @@ #include <cgreen/cgreen.h> - -/* -Implement the stack methods using two queues - -* `push(x)` -* `pop()` - -Analyze the running time of the `push(x)` and `pop()` operations based on this implementation. -*/ - -struct node { - int data; - struct node *next; -}; - -typedef struct node Node; - -typedef struct { - Node *head; - int size; -} Queue; - -typedef struct { - Queue *q1; -} Stack; - -static Queue *newQueue(){ - Queue *queue = malloc(sizeof(Queue)); - queue->size = 0; - queue->head = NULL; - return queue; -} - -static Stack *initialize() { - Stack *stack = malloc(sizeof(Stack)); - stack->q1 = newQueue(); - return stack; -} - -Node *newNode(int data) { - Node *node = malloc(sizeof(Node)); - node->data = data; - node->next = NULL; - return node; -} - -void enqueue(Queue *q, int data) { - Node *node = newNode(data); - q->size++; - - if (q->head == NULL) { - q->head = node; - } else { - Node *tail = q->head; - - while (tail->next != NULL) - tail = tail->next; - tail->next = node; - } -} - -int dequeue(Queue *q) { - if (q->head == NULL) return -1; - - Node *node = q->head; - int data = node->data; - - q->head = node->next; - free(node); - return data; -} - -// The running time is linear time. -static void push(Stack *stack, int data) { - enqueue(stack->q1, data); -} - -// The running time is linear time. -static int pop(Stack *stack) { - int count = stack->q1->size - 1; - Queue *tmp = newQueue(); - - for (int i = 0; i < count; i++) - enqueue(tmp, dequeue(stack->q1)); - - int data = dequeue(stack->q1); - free(stack->q1); - stack->q1 = tmp; - return data; -} - -int size(Stack *stack) { - return stack->q1->size; -} - -static void destroy(Stack *stack) { - int count = size(stack); - - for (int i = 0; i < count; i++) - pop(stack); - - free(stack->q1); - free(stack); -} - -static void inspect(Queue *q) { - Node *tmp = q->head; - - if (q->size == 0) { - printf("[]\n"); - return; - } - - printf("["); - for (int i = 0; i < q->size; i++) { - printf("%d,", tmp->data); - tmp = tmp->next; - } - printf("\b]\n"); -} +#include "stack.h" Describe(Stack); BeforeEach(Stack){ } @@ -166,3 +47,9 @@ TestSuite *stack_tests() { return suite; } + +int main(int argc, char **argv) { + TestSuite *suite = create_test_suite(); + add_suite(suite, stack_tests()); + return run_test_suite(suite, create_text_reporter()); +} |
