Создание стека строк в 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);
}

У меня просто привычка создавать псевдо-конструкторы / деструкторы для всего.

Answer 2

Попробуйте GNU Obstacks .

Из Википедии:

В языке программирования C Obstack является расширением GNU для управления памятью в стандартной библиотеке C. «Препятствием» является «стек» «объектов» (элементов данных), который управляется динамически.

Пример кода из Википедии:

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. */

ИМО, что делает Obstacks особенными: Ему не нужны ни malloc(), ни free(), но память все равно можно распределять «динамически». Это похоже на alloca() на стероидах. Он также доступен на многих платформах, так как он является частью библиотеки GNU C. Особенно во встроенных системах может иметь смысл использовать Obstacks вместо malloc().

Answer 3

См. Статья Википедии о стеках .