A stack is a simple abstract data type with a small number of operations:
- Push: put a new element on the top of the stack.
- Pop: remove the top-most element on the stack.
- Peek: take a look at the element on the top of the stack without removing it.
The key principle behind the stack is that there should be no means of accessing data at a lower level in the stack without first sequentially “pop”ing the elements above it in the stack. It has uses in numerous fields, including logic flow, image processing, and so on. A general purpose implementation is provided below. It is also referred to as a LIFO (Last In, First Out) structure, since the first element to be pushed onto the stack will be the last one popped off of it in normal circumstances.
#ifndef STACK_H // Prevent multiple inclusions #define STACK_H /******************************************************************************* * Preprocessor Directives ******************************************************************************/ /******************************************************************************* * Macros and Constants ******************************************************************************/ /******************************************************************************* * Abstract Data Types ******************************************************************************/ /* Generic node in a stack */ typedef struct snode_t { struct snode_t* next; void* data; size_t width; } snode_t; /* Generic stack */ typedef struct stack_t { snode_t* top; size_t length; } stack_t; /******************************************************************************* * Public Function Prototypes *******************************************************************************/ /* Handle compiling C code as part of a C++ project */ #ifdef __cplusplus extern "C" { #endif /* @functionName: stackInit * @brief: Initializes an empty stack. * @param: stk: A pointer to the stack. */ int stackInit(stack_t* stk); /* @functionName: stackDestroy * @brief: Destroys and cleans up an entire stack. * @param: stk: A pointer to the stack. */ int stackDestroy(stack_t* stk); /* @functionName: stackPop * @brief: Pop an item from the top of the stack. * @param: stk: A pointer to the stack. * @param: node: A pointer to where to store the contents of the * "popped" element. */ int stackPop(stack_t* stk, snode_t* node); /* @functionName: stackPush * @brief: Push an item on top of the stack. * @param: stk: A pointer to the stack. * @param: node: A pointer to the element to "push". */ int stackPush(stack_t* stk, snode_t* node); /* @functionName: stackPeek * @brief: Peek at the item on top of the stack without deleting it. * @param: stk: A pointer to the stack. * @param: node: A pointer to where to store a copy of the data * (not including stack pointer contents) of the data * a the top of the stack. */ int stackPeek(stack_t* stk, snode_t* node); #ifdef __cplusplus } #endif #endif // STACK_H
/******************************************************************************* * @file: stack.c * @author: Matthew Giassa * @email: matthew@giassa.net * @copyright: Matthew Giassa, 2008 * @brief: Simple stack (FILO) implementation as part of Mmath library for * current research projects in biomedical engineering. */ /******************************************************************************* * Preprocessor Directives ******************************************************************************/ /* System Includes */ #include <stdio.h> #include <errno.h> #include <stdlib.h> #include <string.h> #include <time.h> /* Project Includes */ #include "inc/stack.h" /******************************************************************************* * Macros and Constants ******************************************************************************/ #define EOK (0) /******************************************************************************* * Abstract Data Types ******************************************************************************/ /******************************************************************************* * Private Function Prototypes ******************************************************************************/ snode_t* stackCloneNode(snode_t* node); snode_t* stackFreeNode(snode_t* node); /******************************************************************************* * Function Definitions ******************************************************************************/ #if 0 /*----------------------------------------------------------------------------*/ int main(void) { stack_t stk = { 0 }; /* Need to zero out contents prior to calling init */ snode_t* cur; snode_t* tmp; snode_t peekStore; int i, ret; /* Initialize random seed */ srand(time(NULL)); /* Initialize stack and populate with a single zeroed out entry */ if ((ret = stackInit(&stk)) != EOK) { return ret; } /* Create template entry for populating simple stack */ const int nEntries = 10; cur = calloc(1, sizeof(snode_t)); cur->width = sizeof(int); cur->data = calloc(1, cur->width); /* Add items to the stack */ for (i=0; i<20; i++) { *(int*)cur->data = rand() % 100; stackPush(&stk, cur); } /* Print stack contents */ tmp = stk.top; for (i=0; tmp != NULL; tmp = tmp->next, i++) { printf("i:%02d - Value:%d\n", i, *(int*)tmp->data); } /* Take a peek at the top */ (void)stackPeek(&stk, &peekStore); printf("Peeked Value:%d\n", *(int*)peekStore.data); /* Clean up */ stackDestroy(&stk); stackFreeNode(cur); return EOK; } #endif /*----------------------------------------------------------------------------*/ snode_t* stackCloneNode(snode_t* node) { if (!node) { return NULL; } snode_t* tmp; if ((tmp = malloc(1*sizeof(snode_t))) == NULL) { return NULL; } if ((tmp->data = malloc(1*tmp->width)) == NULL) { free(tmp); return NULL; } /* Copy contents of node, accounting for dynamically allocated contents */ tmp->width = node->width; tmp->next = node->next; memcpy(tmp->data, node->data, node->width); return tmp; } /*----------------------------------------------------------------------------*/ snode_t* stackFreeNode(snode_t* node) { if (!node) { return NULL; } free(node->data); memset(node, 0, sizeof(snode_t)); free(node); return NULL; } /*----------------------------------------------------------------------------*/ int stackInit(stack_t* stk) { if (!stk) { return (-EINVAL); } int ret = EOK; /* Just make sure the provided "top" node pointer points to NULL, so that * we aren't erroneously calling init on an already-populated stack. */ if (stk->top != NULL) { ret = (-EIO); } else { stk->length = 0; } return ret; } /*----------------------------------------------------------------------------*/ int stackDestroy(stack_t* stk) { if (!stk) { return (-EINVAL); } snode_t* cur = stk->top; /* Delete first entry in stack until empty */ while (cur) { stackPop(stk, NULL); cur = cur->next; } stk->length = 0; return EOK; } /*----------------------------------------------------------------------------*/ int stackPush(stack_t* stk, snode_t* node) { if (!stk || !node) { return (-EINVAL); } snode_t* tmp; if ((tmp = stackCloneNode(node)) == NULL) { return (-ENOMEM); } if (stk->top == NULL) { /* Account for empty stack */ stk->top = tmp; stk->top->next = NULL; } else { /* Add to the top of the stack */ tmp->next = stk->top; stk->top = tmp; } stk->length++; return EOK; } /*----------------------------------------------------------------------------*/ int stackPop(stack_t* stk, snode_t* node) { if (!stk || !stk->top) { return (-EINVAL); } /* Just delete the top node if an invalid target pointer is provided */ if (node) { snode_t* tmp; if ((tmp = stackCloneNode(stk->top)) == NULL) { return (-ENOMEM); } memcpy(node, tmp, sizeof(snode_t)); free(tmp); } if (stk->top->next == NULL) { /* Account for last item in stack */ stackFreeNode(stk->top); stk->top = NULL; } else { /* Add to the top of the stack */ stk->top = stk->top->next; } stk->length--; return EOK; } /*----------------------------------------------------------------------------*/ int stackPeek(stack_t* stk, snode_t* node) { if (!stk || !stk->top || !node) { return (-EINVAL); } /* Provide a deep copy like with the pop operation */ snode_t* tmp; if ((tmp = stackCloneNode(stk->top)) == NULL) { return (-ENOMEM); } memcpy(node, tmp, sizeof(snode_t)); node->next = NULL; /* Hide internal pointer data */ return EOK; }