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.
