#include #include #include #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) /* * A dynamic stack that can shrink and grow (but won't overflow). * At some point we could change this to make the stack-size lockable * and then we'd have to check against underflow/overflow. * Right now we don't care about fixed-size stacks and just keep it simple * by letting the stack grow/shrink when needed. * * If you like this implementation or have ideas of your own, you're free to * copy, share, and modify it. */ struct stack { unsigned int capacity; unsigned int top; void **data; }; /* * A stack iterator is useful for dumping the contents to stdout * or freeing any heap-allocated data that was pushed. */ struct stack_iter { struct stack *stack; unsigned int pos; void *entry; }; /* Creates and initializes a stack - returns 1 on success and 0 on allocation failure. */ static int stack_create(struct stack *stack, unsigned int initial_capacity) { stack->top = 0; stack->capacity = initial_capacity; stack->data = malloc(initial_capacity * sizeof(*stack->data)); return !!stack->data; } /* Grow or shrinks the stack by the 'new_capacity'. */ static int stack_resize(struct stack *stack, unsigned int new_capacity) { /* * realloc() can return NULL on failure, which is why we should never assign * the return of realloc() directly to the memory block we want resized. * Instead we create a temp variable to hold the new memory block * and we assign it on success - that way we avoid accidentally leaking memory. */ void **resized = realloc(stack->data, new_capacity * sizeof(*stack->data)); if (resized) { stack->data = resized; stack->capacity = new_capacity; return 1; } return 0; } /* Reverses the order of the stack elements. */ static int stack_reverse(struct stack *stack) { unsigned int i, size = stack->top; if (size < 2) return 0; for (i = 0; i < size >> 1; i++) { void *tmp = stack->data[i]; stack->data[i] = stack->data[size-i-1]; stack->data[size-i-1] = tmp; } return 1; } /* Pushes an element onto the stack and if it fails to grow we return 0, otherwise 1. */ static int stack_push(struct stack *stack, const void *data) { if (stack->top >= stack->capacity) if (!stack_resize(stack, stack->capacity << 1)) return 0; stack->data[stack->top++] = (void *)data; return 1; } /* Pop an element off the stack and return it, shrink the stack if necessary. */ static void *stack_pop(struct stack *stack) { if (--stack->top < stack->capacity >> 2) stack_resize(stack, stack->capacity >> 1); return stack->data[stack->top]; } /* * Allow us to peek at an element in the stack without removing it. * The position of the element cannot be greater than the stack's * top position. */ static void *stack_peek(struct stack *stack, unsigned int pos) { return pos < stack->top ? stack->data[pos] : NULL; } /* * Free the memory reserved by the stack and zero initialize it. * NOTE: This function doesn't free heap-allocated data you pushed * onto the stack. */ static void stack_free(struct stack *stack) { free(stack->data); memset(stack, 0, sizeof(*stack)); } static unsigned int stack_get_top(const struct stack *stack) { return stack->top; } static unsigned int stack_get_capacity(const struct stack *stack) { return stack->capacity; } /* * Maybe the point of stacks is not to iterate over them, but it can be of use * when you need to dump it to stdout or free heap-allocated memory. * This function initializes the stack iterator and accepts any stack we want to * traverse. */ static void stack_iter_init(struct stack_iter *iter, struct stack *stack) { iter->stack = stack; iter->pos = 0; iter->entry = NULL; } /* Returns the current stack element and goes to the next. */ static void *stack_iter_next(struct stack_iter *iter) { while (iter->pos < iter->stack->top) { iter->entry = iter->stack->data[iter->pos++]; return iter->entry ? iter->entry : NULL; } iter->pos = 0; /* Reset the position when we reach the last element. */ return NULL; } /* -------------------- End of Stack Implementation ----------------------- */ /* * The following are function-like macros that simplifies formatting of * the stack output and helps with visualization. */ #define print_separator(w, c) \ do { \ int i_ = 0; \ for (i_ = 0; i_ < (w) && putchar(c); i_++); \ putchar('\n'); \ } while (0) #define stack_show_size_formatted(s) \ do { \ print_separator(45, '_'); \ printf("\tCapacity: %u\n\tTop: %u\n", \ stack_get_capacity(&s), stack_get_top(&s)); \ print_separator(45, '~'); \ } while (0) /* A quick function-like macro that nicely formats the output */ #define stack_dump_formatted(s, iter, fmt) \ do { \ puts("Stack Content:"); \ print_separator(45, '_'); \ while (stack_iter_next(&iter)) \ printf("\t"fmt": %d\n", *(const int *)iter.entry); \ stack_show_size_formatted(s); \ putchar('\n'); \ } while (0) /* Main entry point */ int main(void) { /* * There's no reason why I chose integers over any other data type. * It's just easier to exemplify and I'm really bad at dreaming up * interesting things to put inside strings. * Anyway, strings, chars, floats, structs, or anything else should * work as well. */ int i, *n, numbers[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256 }; struct stack stack; struct stack_iter iter; /* Initialize the stack with an initial capacity of 4 elements. */ if (!stack_create(&stack, 4)) { fputs("Error: Stack allocation failure.", stderr); return 1; } /* Push our numbers onto the stack */ for (i = 0; i < ARRAY_SIZE(numbers); i++) stack_push(&stack, &numbers[i]); stack_iter_init(&iter, &stack); stack_dump_formatted(stack, iter, "Stacked"); /* Peek at the 4th element in the stack */ if ((n = stack_peek(&stack, 3))) printf(">> Peeking at stack element 3 -> found value: %d\n\n\n", *n); stack_reverse(&stack); stack_dump_formatted(stack, iter, "Reversed"); /* * Pop some elements off the stack and then display what's left. * (Because the stack is dynamic, it will shrink when the number * of elements is less than 1/4th of the capacity). So the capacity * will have shrunk after the following 6 elements are removed. */ puts("\n>> Popping 6 elements to shrink the stack!"); fputs(">> Popped: ", stdout); for (i = 0; i < 6; i++) { const int *popped = stack_pop(&stack); printf("%d, ", *popped); } printf("\n\n"); stack_dump_formatted(stack, iter, "Stacked"); /* Free the stack */ stack_free(&stack); return 0; } /* * This file is part of dynamic-stack.c * Created by Komodo64. * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, version 2 of the License. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see . */

[Data Structures] : Generic Stack