summaryrefslogtreecommitdiff
path: root/src/01/06
diff options
context:
space:
mode:
Diffstat (limited to 'src/01/06')
-rw-r--r--src/01/06/Makefile37
-rw-r--r--src/01/06/README.md7
-rw-r--r--src/01/06/main.c8
-rw-r--r--src/01/06/min_stack.c72
-rw-r--r--src/01/06/min_stack.h16
-rw-r--r--src/01/06/min_stack_test.c87
-rw-r--r--src/01/06/stack_test.c168
7 files changed, 224 insertions, 171 deletions
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 <stdio.h>
+#include <stdlib.h>
+
+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 <stdio.h>
+#include <stdlib.h>
+#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 <cgreen/cgreen.h>
+#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 <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");
-}
-
-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;
-}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 06:54:00 +0000