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