From 24700ade3ae9ff643b0c092ff617fb065d9f19f1 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sat, 4 Jul 2020 13:04:54 -0600 Subject: Switch 06 and 01b --- src/01/01b/Makefile | 37 ---------- src/01/01b/README.md | 7 +- src/01/01b/main.c | 8 --- src/01/01b/min_stack.c | 72 ------------------- src/01/01b/min_stack.h | 16 ----- src/01/01b/min_stack_test.c | 87 ----------------------- src/01/01b/stack_test.c | 168 ++++++++++++++++++++++++++++++++++++++++++++ src/01/06/Makefile | 37 ++++++++++ src/01/06/README.md | 7 +- src/01/06/main.c | 8 +++ src/01/06/min_stack.c | 72 +++++++++++++++++++ src/01/06/min_stack.h | 16 +++++ src/01/06/min_stack_test.c | 87 +++++++++++++++++++++++ src/01/06/stack_test.c | 168 -------------------------------------------- 14 files changed, 395 insertions(+), 395 deletions(-) delete mode 100644 src/01/01b/Makefile delete mode 100644 src/01/01b/main.c delete mode 100644 src/01/01b/min_stack.c delete mode 100644 src/01/01b/min_stack.h delete mode 100644 src/01/01b/min_stack_test.c create mode 100644 src/01/01b/stack_test.c create mode 100644 src/01/06/Makefile create mode 100644 src/01/06/main.c create mode 100644 src/01/06/min_stack.c create mode 100644 src/01/06/min_stack.h create mode 100644 src/01/06/min_stack_test.c delete mode 100644 src/01/06/stack_test.c (limited to 'src') diff --git a/src/01/01b/Makefile b/src/01/01b/Makefile deleted file mode 100644 index 8120d17..0000000 --- a/src/01/01b/Makefile +++ /dev/null @@ -1,37 +0,0 @@ -#!/usr/bin/make -f -SHELL=/bin/sh - -CC=clang -TEST_LIBS = -lcgreen - -BUILDDIR := build -OBJS := $(addprefix $(BUILDDIR)/,min_stack.o) -TEST_OBJS := $(addprefix $(BUILDDIR)/,min_stack_test.o) - -$(BUILDDIR)/%.o : %.c - $(COMPILE.c) $(OUTPUT_OPTION) $< - -.PHONY: all -all: $(OBJS) $(BUILDDIR)/main.o - $(CC) $(OBJS) $(BUILDDIR)/main.o -o $(BUILDDIR)/program - -.PHONY: test -test: $(OBJS) $(TEST_OBJS) - $(CC) $(OBJS) $(TEST_OBJS) $(TEST_LIBS) -o $(BUILDDIR)/test - -$(OBJS): | $(BUILDDIR) - -$(TEST_OBJS): | $(BUILDDIR) - -$(BUILDDIR): - mkdir $(BUILDDIR) - -.PHONY: clean -clean: - rm -fr build - -run : all - ./build/program - -run_test : test - cgreen-runner -c -v $(BUILDDIR)/test diff --git a/src/01/01b/README.md b/src/01/01b/README.md index f288e0f..ceab17a 100644 --- a/src/01/01b/README.md +++ b/src/01/01b/README.md @@ -1,14 +1,13 @@ -# Learning Profile for Assignment #1 - Question #6 - Computer Science 272: Data Structures and Algorithms +# Learning Profile for Assignment #1 - Question #1b - Computer Science 272: Data Structures and Algorithms Name: Mo Khan Student ID: 3431709 1. Problem Statement: -Design and implement a MinStack data structure that can store comparable elements and supports the stack operations `push(x)`, `pop()`, and `size()`, -as well as the `min()` operation, which returns the minimum value currently stored in the data structure. +Implement the stack methods `push(x)` and `pop()` using two queues. -All operations should run in constant time. +Analyze the running time of the push(x) and pop() operations based on this implementation. 2. Description of the Code: 3. Errors and Warnings: diff --git a/src/01/01b/main.c b/src/01/01b/main.c deleted file mode 100644 index f90e37f..0000000 --- a/src/01/01b/main.c +++ /dev/null @@ -1,8 +0,0 @@ -#include -#include - -int main(int argc, char *argv[]) -{ - printf("=== COMP-272 - Assignment 1 - Question 1b ===\n"); - return 0; -} diff --git a/src/01/01b/min_stack.c b/src/01/01b/min_stack.c deleted file mode 100644 index adb96c8..0000000 --- a/src/01/01b/min_stack.c +++ /dev/null @@ -1,72 +0,0 @@ -#include -#include -#include "min_stack.h" - -Stack *initialize() { - Stack *self = malloc(sizeof(Stack)); - self->head = NULL; - return self; -} - -int size(Stack *self) { - Node *current = self->head; - int i; - for (i = 0; current != NULL; i++) - current = current->next; - return i; -} - -static Node *new(int data) { - Node *node = malloc(sizeof(Node)); - node->next = NULL; - node->data = data; - return node; -} - -static int compare(int x, int y) { - return x == y ? 0 : (x > y) ? 1 : -1; -} - -static void insert(Node **self, int data) { - int comparison = compare(data, (*self)->data); - Node *node = new(data); - - switch(comparison) { - case 1: - if ((*self)->next) - insert(&((*self)->next), data); - else - (*self)->next = node; - break; - default: - node->next = *self; - *self = node; - break; - } -} - -void push(Stack *self, int data) { - if (self->head) - insert(&self->head, data); - else - self->head = new(data); -} - -int min(Stack *self) { - if (self && self->head) - return self->head->data; - - return (int)NULL; -} - -int pop(Stack *self) { - if (!self->head) - return (int)NULL; - - Node *current = self->head; - int data = current->data; - self->head = current->next; - current->next = NULL; - free(current); - return data; -} diff --git a/src/01/01b/min_stack.h b/src/01/01b/min_stack.h deleted file mode 100644 index 567b0a4..0000000 --- a/src/01/01b/min_stack.h +++ /dev/null @@ -1,16 +0,0 @@ -struct node { - int data; - struct node *next; -}; - -typedef struct node Node; - -typedef struct { - Node *head; -} Stack; - -Stack *initialize(); -void push(Stack *self, int data); -int pop(Stack *self); -int size(Stack *self); -int min(Stack *self); diff --git a/src/01/01b/min_stack_test.c b/src/01/01b/min_stack_test.c deleted file mode 100644 index a02c163..0000000 --- a/src/01/01b/min_stack_test.c +++ /dev/null @@ -1,87 +0,0 @@ -#include -#include "min_stack.h" - -Describe(MinStack); -BeforeEach(MinStack){ } -AfterEach(MinStack){ } - -Ensure(MinStack, when_empty) { - Stack *stack = initialize(); - - assert_that(size(stack), is_equal_to(0)); - assert_that(min(stack), is_equal_to(NULL)); - assert_that(pop(stack), is_equal_to(NULL)); - - free(stack); -} - -Ensure(MinStack, when_pushing_a_single_integer) { - Stack *stack = initialize(); - - push(stack, 1); - - assert_that(size(stack), is_equal_to(1)); - assert_that(min(stack), is_equal_to(1)); - assert_that(pop(stack), is_equal_to(1)); - assert_that(size(stack), is_equal_to(0)); - - free(stack); -} - -Ensure(MinStack, when_pushing_multiple_integers_out_of_order) { - Stack *stack = initialize(); - - push(stack, 2); - push(stack, 3); - push(stack, 1); - - assert_that(size(stack), is_equal_to(3)); - assert_that(min(stack), is_equal_to(1)); - - assert_that(pop(stack), is_equal_to(1)); - assert_that(size(stack), is_equal_to(2)); - - assert_that(pop(stack), is_equal_to(2)); - assert_that(size(stack), is_equal_to(1)); - - assert_that(pop(stack), is_equal_to(3)); - assert_that(size(stack), is_equal_to(0)); - - assert_that(pop(stack), is_equal_to(NULL)); - assert_that(size(stack), is_equal_to(0)); - - free(stack); -} - -Ensure(MinStack, when_pushing_duplicate_values_on_to_the_stack) { - Stack *stack = initialize(); - - push(stack, 2); - push(stack, 1); - push(stack, 2); - - assert_that(size(stack), is_equal_to(3)); - assert_that(min(stack), is_equal_to(1)); - - assert_that(pop(stack), is_equal_to(1)); - assert_that(pop(stack), is_equal_to(2)); - assert_that(pop(stack), is_equal_to(2)); - assert_that(pop(stack), is_equal_to(NULL)); - - free(stack); -} - -TestSuite *min_stack_tests() { - TestSuite *suite = create_test_suite(); - - add_test_with_context(suite, MinStack, when_empty); - add_test_with_context(suite, MinStack, when_pushing_a_single_integer); - add_test_with_context(suite, MinStack, when_pushing_multiple_integers_out_of_order); - return suite; -} - -int main(int argc, char **argv) { - TestSuite *suite = create_test_suite(); - add_suite(suite, min_stack_tests()); - return run_test_suite(suite, create_text_reporter()); -} diff --git a/src/01/01b/stack_test.c b/src/01/01b/stack_test.c new file mode 100644 index 0000000..b34c191 --- /dev/null +++ b/src/01/01b/stack_test.c @@ -0,0 +1,168 @@ +#include + +/* +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"); +} + +Describe(Stack); +BeforeEach(Stack){ } +AfterEach(Stack){ } + +Ensure(Stack, push_onto_stack) { + Stack *stack = initialize(); + + push(stack, 1); + assert_that(size(stack), is_equal_to(1)); + + push(stack, 2); + assert_that(size(stack), is_equal_to(2)); + + destroy(stack); +} + +Ensure(Stack, pop_single_item) { + Stack *stack = initialize(); + + push(stack, 1); + + assert_that(pop(stack), is_equal_to(1)); + destroy(stack); +} + +Ensure(Stack, pop_successive_items) { + Stack *stack = initialize(); + + push(stack, 1); + push(stack, 2); + + assert_that(pop(stack), is_equal_to(2)); + assert_that(pop(stack), is_equal_to(1)); + + destroy(stack); +} + +TestSuite *stack_tests() { + TestSuite *suite = create_test_suite(); + + add_test_with_context(suite, Stack, push_onto_stack); + add_test_with_context(suite, Stack, pop_single_item); + add_test_with_context(suite, Stack, pop_successive_items); + + return suite; +} diff --git a/src/01/06/Makefile b/src/01/06/Makefile new file mode 100644 index 0000000..8120d17 --- /dev/null +++ b/src/01/06/Makefile @@ -0,0 +1,37 @@ +#!/usr/bin/make -f +SHELL=/bin/sh + +CC=clang +TEST_LIBS = -lcgreen + +BUILDDIR := build +OBJS := $(addprefix $(BUILDDIR)/,min_stack.o) +TEST_OBJS := $(addprefix $(BUILDDIR)/,min_stack_test.o) + +$(BUILDDIR)/%.o : %.c + $(COMPILE.c) $(OUTPUT_OPTION) $< + +.PHONY: all +all: $(OBJS) $(BUILDDIR)/main.o + $(CC) $(OBJS) $(BUILDDIR)/main.o -o $(BUILDDIR)/program + +.PHONY: test +test: $(OBJS) $(TEST_OBJS) + $(CC) $(OBJS) $(TEST_OBJS) $(TEST_LIBS) -o $(BUILDDIR)/test + +$(OBJS): | $(BUILDDIR) + +$(TEST_OBJS): | $(BUILDDIR) + +$(BUILDDIR): + mkdir $(BUILDDIR) + +.PHONY: clean +clean: + rm -fr build + +run : all + ./build/program + +run_test : test + cgreen-runner -c -v $(BUILDDIR)/test diff --git a/src/01/06/README.md b/src/01/06/README.md index ceab17a..f288e0f 100644 --- a/src/01/06/README.md +++ b/src/01/06/README.md @@ -1,13 +1,14 @@ -# Learning Profile for Assignment #1 - Question #1b - Computer Science 272: Data Structures and Algorithms +# Learning Profile for Assignment #1 - Question #6 - Computer Science 272: Data Structures and Algorithms Name: Mo Khan Student ID: 3431709 1. Problem Statement: -Implement the stack methods `push(x)` and `pop()` using two queues. +Design and implement a MinStack data structure that can store comparable elements and supports the stack operations `push(x)`, `pop()`, and `size()`, +as well as the `min()` operation, which returns the minimum value currently stored in the data structure. -Analyze the running time of the push(x) and pop() operations based on this implementation. +All operations should run in constant time. 2. Description of the Code: 3. Errors and Warnings: diff --git a/src/01/06/main.c b/src/01/06/main.c new file mode 100644 index 0000000..f90e37f --- /dev/null +++ b/src/01/06/main.c @@ -0,0 +1,8 @@ +#include +#include + +int main(int argc, char *argv[]) +{ + printf("=== COMP-272 - Assignment 1 - Question 1b ===\n"); + return 0; +} diff --git a/src/01/06/min_stack.c b/src/01/06/min_stack.c new file mode 100644 index 0000000..adb96c8 --- /dev/null +++ b/src/01/06/min_stack.c @@ -0,0 +1,72 @@ +#include +#include +#include "min_stack.h" + +Stack *initialize() { + Stack *self = malloc(sizeof(Stack)); + self->head = NULL; + return self; +} + +int size(Stack *self) { + Node *current = self->head; + int i; + for (i = 0; current != NULL; i++) + current = current->next; + return i; +} + +static Node *new(int data) { + Node *node = malloc(sizeof(Node)); + node->next = NULL; + node->data = data; + return node; +} + +static int compare(int x, int y) { + return x == y ? 0 : (x > y) ? 1 : -1; +} + +static void insert(Node **self, int data) { + int comparison = compare(data, (*self)->data); + Node *node = new(data); + + switch(comparison) { + case 1: + if ((*self)->next) + insert(&((*self)->next), data); + else + (*self)->next = node; + break; + default: + node->next = *self; + *self = node; + break; + } +} + +void push(Stack *self, int data) { + if (self->head) + insert(&self->head, data); + else + self->head = new(data); +} + +int min(Stack *self) { + if (self && self->head) + return self->head->data; + + return (int)NULL; +} + +int pop(Stack *self) { + if (!self->head) + return (int)NULL; + + Node *current = self->head; + int data = current->data; + self->head = current->next; + current->next = NULL; + free(current); + return data; +} diff --git a/src/01/06/min_stack.h b/src/01/06/min_stack.h new file mode 100644 index 0000000..567b0a4 --- /dev/null +++ b/src/01/06/min_stack.h @@ -0,0 +1,16 @@ +struct node { + int data; + struct node *next; +}; + +typedef struct node Node; + +typedef struct { + Node *head; +} Stack; + +Stack *initialize(); +void push(Stack *self, int data); +int pop(Stack *self); +int size(Stack *self); +int min(Stack *self); diff --git a/src/01/06/min_stack_test.c b/src/01/06/min_stack_test.c new file mode 100644 index 0000000..a02c163 --- /dev/null +++ b/src/01/06/min_stack_test.c @@ -0,0 +1,87 @@ +#include +#include "min_stack.h" + +Describe(MinStack); +BeforeEach(MinStack){ } +AfterEach(MinStack){ } + +Ensure(MinStack, when_empty) { + Stack *stack = initialize(); + + assert_that(size(stack), is_equal_to(0)); + assert_that(min(stack), is_equal_to(NULL)); + assert_that(pop(stack), is_equal_to(NULL)); + + free(stack); +} + +Ensure(MinStack, when_pushing_a_single_integer) { + Stack *stack = initialize(); + + push(stack, 1); + + assert_that(size(stack), is_equal_to(1)); + assert_that(min(stack), is_equal_to(1)); + assert_that(pop(stack), is_equal_to(1)); + assert_that(size(stack), is_equal_to(0)); + + free(stack); +} + +Ensure(MinStack, when_pushing_multiple_integers_out_of_order) { + Stack *stack = initialize(); + + push(stack, 2); + push(stack, 3); + push(stack, 1); + + assert_that(size(stack), is_equal_to(3)); + assert_that(min(stack), is_equal_to(1)); + + assert_that(pop(stack), is_equal_to(1)); + assert_that(size(stack), is_equal_to(2)); + + assert_that(pop(stack), is_equal_to(2)); + assert_that(size(stack), is_equal_to(1)); + + assert_that(pop(stack), is_equal_to(3)); + assert_that(size(stack), is_equal_to(0)); + + assert_that(pop(stack), is_equal_to(NULL)); + assert_that(size(stack), is_equal_to(0)); + + free(stack); +} + +Ensure(MinStack, when_pushing_duplicate_values_on_to_the_stack) { + Stack *stack = initialize(); + + push(stack, 2); + push(stack, 1); + push(stack, 2); + + assert_that(size(stack), is_equal_to(3)); + assert_that(min(stack), is_equal_to(1)); + + assert_that(pop(stack), is_equal_to(1)); + assert_that(pop(stack), is_equal_to(2)); + assert_that(pop(stack), is_equal_to(2)); + assert_that(pop(stack), is_equal_to(NULL)); + + free(stack); +} + +TestSuite *min_stack_tests() { + TestSuite *suite = create_test_suite(); + + add_test_with_context(suite, MinStack, when_empty); + add_test_with_context(suite, MinStack, when_pushing_a_single_integer); + add_test_with_context(suite, MinStack, when_pushing_multiple_integers_out_of_order); + return suite; +} + +int main(int argc, char **argv) { + TestSuite *suite = create_test_suite(); + add_suite(suite, min_stack_tests()); + return run_test_suite(suite, create_text_reporter()); +} diff --git a/src/01/06/stack_test.c b/src/01/06/stack_test.c deleted file mode 100644 index b34c191..0000000 --- a/src/01/06/stack_test.c +++ /dev/null @@ -1,168 +0,0 @@ -#include - -/* -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"); -} - -Describe(Stack); -BeforeEach(Stack){ } -AfterEach(Stack){ } - -Ensure(Stack, push_onto_stack) { - Stack *stack = initialize(); - - push(stack, 1); - assert_that(size(stack), is_equal_to(1)); - - push(stack, 2); - assert_that(size(stack), is_equal_to(2)); - - destroy(stack); -} - -Ensure(Stack, pop_single_item) { - Stack *stack = initialize(); - - push(stack, 1); - - assert_that(pop(stack), is_equal_to(1)); - destroy(stack); -} - -Ensure(Stack, pop_successive_items) { - Stack *stack = initialize(); - - push(stack, 1); - push(stack, 2); - - assert_that(pop(stack), is_equal_to(2)); - assert_that(pop(stack), is_equal_to(1)); - - destroy(stack); -} - -TestSuite *stack_tests() { - TestSuite *suite = create_test_suite(); - - add_test_with_context(suite, Stack, push_onto_stack); - add_test_with_context(suite, Stack, pop_single_item); - add_test_with_context(suite, Stack, pop_successive_items); - - return suite; -} -- cgit v1.2.3