работа со стеком и указателями в c

Question

Я работаю над довольно простыми функциями в c для управления стеком.Все работает нормально, но я хочу знать, как я могу создать функцию createtack (), которая устанавливает указатель (и) для создания пустого стека.И как я могу использовать эту функцию или структуру в моих функциях push и pop.Вот мой код:

typedef struct nodeRec
{
    int item;
    struct nodeRec* next;
} node;
typedef node* nodePtr;
nodePtr top;


int isempty(nodePtr mytop)
{
    return mytop == NULL;
}

void push(int value1, nodePtr* mytop)
{
    struct nodeRec *newNode;
    newNode = (struct nodeRec*)malloc(sizeof(struct nodeRec));
    newNode->item = value1;
    if (isempty(mytop))
        newNode->next = NULL;
    else
        newNode->next = mytop;
    top = newNode;
    printf("\nElement added!!!\n");
    count++;
}
void pop(nodePtr* mytop)
{
    if (isempty(mytop))
        printf("\nStack is Empty!!!\n");
else {
    struct nodeRec *temp = mytop;
    printf("\nDeleted element: %d", temp->item);
    top= temp->next;
    free(temp);
    count--;
}

}

Answer 1

Вы можете сделать что-то вроде:

typedef struct {
    node *head;
    size_t size;
} stack_t;

size_t stack_size(stack_t *stack) {
    return stack->size;
}

bool is_empty(stack_t *stack) {
    return stack_size(stack) == 0;
}

stack_t *stack_create(void) {
    stack_t *stack = malloc(sizeof(stack_t));
    stack->size = 0;
    stack->head = NULL;
    return stack;
}

void push(stack_t *stack, int data) {
    node *new_node = malloc(sizeof(struct nodeRec));
    new_node->item = data;
    new_node->next = stack->head;
    stack->head = new_node;
    stack->size++;
}

int pop(stack_t *stack) {
    assert(!is_empty(stack));
    node *old_head = stack->head;
    stack->head = stack->head->next;
    int ret = old_head->item;
    free(old_head);
    stack->size--;
    return ret;
}

Конечно, это не очень надежная реализация, так как она игнорирует некоторые случаи, например, когда недопустимые аргументы (например, указатели NULL) передаются в стекинтерфейсные функции и случаи ошибок, например, когда malloc дает сбой, но, надеюсь, это хорошее начало.

Основная идея состоит в том, что мы определяем тип stack_t, который хранит все метаданные, которые вы используете.в настоящее время хранится в глобальных переменных.Затем нашей stack_create функции просто нужно выделить память и инициализировать один из этих stack_t типов, и мы можем вернуть указатель на это.Таким образом, вы можете легко иметь несколько стеков, каждый из которых имеет собственный заголовок stack_t, который можно передавать во все функции интерфейса стека.

Надеюсь, это поможет!

Answer 2

Ваш пример - стек, подкрепленный связанным списком.Таким образом, в этом случае вам нужно только сохранить указатель на голову;

struct stack {
   node *head;
};

При каждой операции обновляйте head по мере необходимости.

void stack_push(stack *s, int val) {
    node *node = (node *) malloc(sizeof(node));
    node->item = val;
    node->next = s->head;
    s->head = node;
}

EDIT

@ Осирис спрашивает в комментариях:

стек * узел * будет работать нормально, или нет?

Причина, по которой это плохая идеяэто из-за псевдонимов указателей:

/* Declare the stack using Osiris' type */
node *stack1 = ...;
node *stack2 = stack1;

stack_pop(&stack1);
stack_push(&stack2, 0);  /* Crash accessing freed memory */

Очевидно, что эти ссылки могут быть многочисленными и разбросанными по разным модулям.Нет способа гарантировать отсутствие наложения указателя.Вы не сможете узнать, был ли ваш node * действительным в любой момент времени.Вот почему представление стека просто как node * как предложено не работает.

Однако, используя структуру, невозможно, чтобы операции, выполняемые с помощью одной ссылки, могли конфликтовать с операциями с другой ссылкой:

stack *stack1 = ...;
stack *stack2 = stack1;

stack_pop(stack1);
stack_push(stack2, 0); /* No crash */