Creating a stack of strings in C

Question

I want to have a stack that takes strings. I want to be able to push and pop strings off, as well as clear the whole stack. I think C++ has some methods for this. What about C?

Solution 1

Quick-and-dirty untested example. Uses a singly-linked list structure; elements are pushed onto and popped from the head of the list.

#include <stdlib.h>
#include <string.h>

/**
 * Type for individual stack entry
 */
struct stack_entry {
  char *data;
  struct stack_entry *next;
}

/**
 * Type for stack instance
 */
struct stack_t
{
  struct stack_entry *head;
  size_t stackSize;  // not strictly necessary, but
                     // useful for logging
}

/**
 * Create a new stack instance
 */
struct stack_t *newStack(void)
{
  struct stack_t *stack = malloc(sizeof *stack);
  if (stack)
  {
    stack->head = NULL;
    stack->stackSize = 0;
  }
  return stack;
}

/**
 * Make a copy of the string to be stored (assumes  
 * strdup() or similar functionality is not
 * available
 */
char *copyString(char *str)
{
  char *tmp = malloc(strlen(str) + 1);
  if (tmp)
    strcpy(tmp, str);
  return tmp;
}

/**
 * Push a value onto the stack
 */
void push(struct stack_t *theStack, char *value)
{
  struct stack_entry *entry = malloc(sizeof *entry); 
  if (entry)
  {
    entry->data = copyString(value);
    entry->next = theStack->head;
    theStack->head = entry;
    theStack->stackSize++;
  }
  else
  {
    // handle error here
  }
}

/**
 * Get the value at the top of the stack
 */
char *top(struct stack_t *theStack)
{
  if (theStack && theStack->head)
    return theStack->head->data;
  else
    return NULL;
}

/**
 * Pop the top element from the stack; this deletes both 
 * the stack entry and the string it points to
 */
void pop(struct stack_t *theStack)
{
  if (theStack->head != NULL)
  {
    struct stack_entry *tmp = theStack->head;
    theStack->head = theStack->head->next;
    free(tmp->data);
    free(tmp);
    theStack->stackSize--;
  }
}

/**
 * Clear all elements from the stack
 */
void clear (struct stack_t *theStack)
{
  while (theStack->head != NULL)
    pop(theStack);
}

/**
 * Destroy a stack instance
 */
void destroyStack(struct stack_t **theStack)
{
  clear(*theStack);
  free(*theStack);
  *theStack = NULL;
}

Edit

It would help to have an example of how to use it:

int main(void)
{
  struct stack_t *theStack = newStack();
  char *data;

  push(theStack, "foo");
  push(theStack, "bar");
  ...
  data = top(theStack);
  pop(theStack);
  ...
  clear(theStack);
  destroyStack(&theStack);
  ...
}

You can declare stacks as auto variables, rather than using newStack() and destroyStack(), you just need to make sure they're initialzed properly, as in

int main(void)
{
  struct stack_t myStack = {NULL, 0};
  push (&myStack, "this is a test");
  push (&myStack, "this is another test");
  ...
  clear(&myStack);
}

I'm just in the habit of creating pseudo constructors/destructors for everything.

Solution 2

Try GNU Obstacks.

From Wikipedia:

In the C programming language, Obstack is a memory-management GNU extension to the C standard library. An "obstack" is a "stack" of "objects" (data items) which is dynamically managed.

Code example from Wikipedia:

char *x;
void *(*funcp)();

x = (char *) obstack_alloc(obptr, size); /* Use the macro. */
x = (char *) (obstack_alloc) (obptr, size); /* Call the function. */
funcp = obstack_alloc; /* Take the address of the function. */

IMO what makes Obstacks special: It does not need malloc() nor free(), but the memory still can be allocated «dynamically». It is like alloca() on steroids. It is also available on many platforms, since it is a part of the GNU C Library. Especially on embedded systems it might make more sense to use Obstacks instead of malloc().