Saturday, November 6, 2010

three implimentations of a stack in C

I decided to write up three implementations of the basic stack data structure in C, complete with tests.

#include <stdio.h>
#include <stdlib.h>

void check(char *message, int success) {
 printf("%s %s\n", success ? "pass" : "FAIL", message);
}

/*
 * array fixed stack. create an array of length one greater than the maximum
 * stack depth, and call aInit on it to set it up.
 */
void aInit(int *stack) {
 stack[0] = 0;
}

void aPush(int *stack, int value) {
 stack[++stack[0]] = value;
}

int aPeek(int *stack) {
 if(stack[0] == 0) {
  return 0;
 }

 return stack[stack[0]];
}

int aPop(int *stack) {
 if(stack[0] == 0) {
  return 0;
 }

 return stack[stack[0]--];
}

int aSize(int *stack) {
 return stack[0];
}

void aPrint(int *stack) {
 int i;

 /* print the stack from top to bottom */
 for(i = stack[0]; i > 0; i--) {
  printf("%d ", stack[i]);
 }
 printf("\n");
}

void test_a() {
 int stack[10];
 aInit(stack);
 check("a size", aSize(stack) == 0);

 aPush(stack, 1);
 aPush(stack, 2);
 check("a size", aSize(stack) == 2);

 check("a peek", aPeek(stack) == 2);
 check("a peek", aPeek(stack) == 2);

 check("a pop", aPop(stack) == 2);
 check("a size", aSize(stack) == 1);

 aPush(stack, 3);
 check("a size", aSize(stack) == 2);
 check("a peek", aPeek(stack) == 3);
}

/*
 * struct fixed stack
 */
struct sStack {
 int size;
 int data[10];
};

void sInit(struct sStack *stack) {
 stack->size = 0;
}

int sSize(struct sStack *stack) {
 return stack->size;
}

void sPush(struct sStack *stack, int value) {
 stack->data[stack->size] = value;
 stack->size += 1;
}

int sPeek(struct sStack *stack) {
 if(stack->size == 0) {
  return 0;
 }

 return stack->data[stack->size - 1];
}

int sPop(struct sStack *stack) {
 if(stack->size == 0) {
  return 0;
 }

 stack->size -= 1;
 return stack->data[stack->size];
}

void sPrint(struct sStack *stack) {
 int i;

 /* print the stack from top to bottom */
 for(i = stack->size; i > 0; i--) {
  printf("%d ", stack->data[i - 1]);
 }
 printf("\n");
}

void test_s() {
 struct sStack stack;
 sInit(&stack);
 check("s size", sSize(&stack) == 0);

 sPush(&stack, 1);
 sPush(&stack, 2);
 check("s size", sSize(&stack) == 2);

 check("s peek", sPeek(&stack) == 2);
 check("s peek", sPeek(&stack) == 2);

 check("s pop", sPop(&stack) == 2);
 check("s size", sSize(&stack) == 1);

 sPush(&stack, 3);
 check("s size", sSize(&stack) == 2);
 check("s peek", sPeek(&stack) == 3);
}

/*
 * linked dynamic stack
 */
struct lNode {
 struct lNode *next;
 int data;
};

struct lStack {
 struct lNode *head;
};

void lInit(struct lStack *stack) {
 stack->head = NULL;
}

int lSize(struct lStack *stack) {
 int size = 0;
 struct lNode *i;

 i = stack->head;
 while(i != NULL) {
  size += 1;
  i = i->next;
 }
 return size;
}

void lPush(struct lStack *stack, int value) {
 struct lNode *head;

 head = (struct lNode*)calloc(1, sizeof(struct lNode));
 head->data = value;
 head->next = stack->head;

 stack->head = head;
}

int lPeek(struct lStack *stack) {
 if(stack->head == NULL) {
  return 0;
 }

 return stack->head->data;
}

int lPop(struct lStack *stack) {
 struct lNode *head;
 int out;

 head = stack->head;

 if(head == NULL) {
  return 0;
 }

 stack->head = head->next;

 out = head->data;

 free(head);

 return out;
}

void lPrint(struct lStack *stack) {
 struct lNode *i;

 for(i = stack->head; i != NULL; i = i->next) {
  printf("%d ", i->data);
 }
 printf("\n");
}

void lDestroy(struct lStack *stack) {
 struct lNode *head;
 struct lNode *next;

 head = stack->head;
 while(head != NULL) {
  next = head->next;
  free(head);
  head = next;
 }
 stack->head = NULL;
}

void test_l() {
 struct lStack stack;
 lInit(&stack);
 check("l size", lSize(&stack) == 0);

 lPush(&stack, 1);
 lPush(&stack, 2);
 check("l size", lSize(&stack) == 2);

 check("l peek", lPeek(&stack) == 2);
 check("l peek", lPeek(&stack) == 2);

 check("l pop", lPop(&stack) == 2);
 check("l size", lSize(&stack) == 1);

 lPush(&stack, 3);
 check("l size", lSize(&stack) == 2);
 check("l peek", lPeek(&stack) == 3);

 lDestroy(&stack);
}

int main() {
 test_a();
 test_s();
 test_l();
 return 0;
}

I hope the code is clean and clear, but there is a good chance that is is not.

No comments:

Post a Comment