Switch 06 and 01b

7 files changed, 171 insertions, 224 deletions

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 <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/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 <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/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 <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/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 <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;
+}