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?

Answer 1

C hasn't got a standard library with the most common data structures like C++ does, you have to create the stack yourself.

Fortunately this is quite easy and doesn't need that many lines of code.

Answer 2

See Wikipedia's article about stacks.

Answer 3

Try GNU Obstacks.

Answer 4

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.