在 C 中创建一个字符串堆栈

Question

我想要一个接受字符串的堆栈。我希望能够插入和弹出字符串，以及清除整个堆栈。我认为 C++ 对此有一些方法。 C呢？

Answer 1

快速和肮脏的未经测试的例子。使用单链表结构；元素被插入列表的头部并从列表的头部弹出。

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

编辑

有一个如何使用它的例子会很有帮助:

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

您可以将堆栈声明为自动变量，而不是使用 newStack() 和 destroyStack()，您只需要确保它们已正确初始化，如

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

我只是习惯于为所有东西创建伪构造函数/析构函数。