Учитывая ваши структуры данных, представляющие узел в стеке, и сам фактический стек:
typedef struct node {
void *dataptr;
struct node *link;
} NODE;
typedef struct {
int count;
NODE *top;
} STACK;
вы бы инициализировали стек следующим образом:
STACK myStack;
myStack.count = 0;
myStack.top = NULL;
Это в основном дает вам пустой стек. Я собираюсь использовать top, чтобы решить, пуст ли стек - вы можете использовать либо count, либо top (как 0 или NULL соответственно), чтобы выполнить эту работу, но это хорошая идея, чтобы выбрать один и придерживайтесь его на случай, если вы когда-нибудь напишите какой-нибудь ошибочный код, когда количество кэшированных и фактических счетчиков выйдет из строя: -)
Чтобы поместить узел в стек, это простая операция:
- выделить новый узел и установить полезную нагрузку (1).
- указывает ссылку нового узла на текущий заголовок.
- направьте голову на этот новый узел (3).
- увеличить счетчик (4).
Следующий код показывает, как вы можете это сделать:
/* 1 */ NODE *newNode = malloc (sizeof (NODE)); // should check for failure.
newNode->dataptr = NULL;
/* 2 */ newNode->link = myStack.top;
/* 3 */ myStack.top = newNode;
/* 4 */ myStack.count++;
Это приведет к пустому стеку или заполненному. В случае края пустого стека newNode.link будет установлено на NULL, затем myStack.top будет установлено на newNode, что является правильным поведением.
Чтобы вытолкнуть узел из стека:
- сохранить текущую голову (1).
- если текущий заголовок не равен NULL, перейдите к его ссылке (и уменьшите счетчик).
- вернуть сохраненную текущую головку (3).
что в переводе на код:
/* 1 */ NODE *popNode = myStack.top;
/* 2 */ if (myStack.top != NULL) {
myStack.top = myStack.top->link;
myStack.count--;
}
/* 3 */ return popNode;
Возвращает адрес извлеченного узла или NULL, если стек был пуст.
Весь набор операций можно инкапсулировать следующим образом. Надеемся, что комментарии сделают это самоочевидным в сочетании с комментариями выше, но не стесняйтесь поднимать любые проблемы, и я рассмотрю их с правкой.
// Error codes (probably should be enums).
#define STACK_ERR_OKAY 0
#define STACK_ERR_NOTEMPTY 1
#define STACK_ERR_NOPAYLOAD 2
#define STACK_ERR_NOMEMORY 3
// Structures.
typedef struct sNode {
void *data; // Payload pointer.
struct sNode *next; // Link to next node.
} tNode;
typedef struct {
int count; // Count for fast sizing.
NODE *top; // First node.
} tStack;
// Make a new stack returning its pointer or NULL on failure.
tStack *stackNew (void) {
tStack stack = malloc (sizeof (tStack));
if (stack != NULL) {
stack->count = 0;
stack->top = NULL;
}
return stack;
}
// Delete a current stack, must be empty first.
int stackDel (tStack *stack) {
if (stack->top != NULL)
return STACK_ERR_NOT_EMPTY;
free (stack);
return STACK_ERR_OK;
}
// Push a pointer payload (no NULLs allowed) onto the stack.
int stackPush (tStack *stack, void *payload) {
if (payload == NULL)
return STACK_ERR_NOPAYLOAD;
tNode *node = malloc (sizeof (tNode));
if (node == NULL)
return STACK_ERR_NOMEMORY;
node->data = payload;
node->next = stack->top;
stack->top = node;
stack->count++;
return STACK_ERR_OK;
}
// Pop a pointer payload from the stack. Returns NULL if stack was empty.
int stackPop (tStack *stack) {
tNode *node = stack->top;
if (node == NULL) {
return NULL;
stack->top = node->next;
stack->count--;
return node->data;
}
// Get stack size.
int stackSize (tStack *stack) {
return stack->count;
}
Причина, по которой я настаивал на том, что стек должен быть пустым перед удалением, заключается в том, что код не знает наверняка, что такое полезная нагрузка. Это может быть простой указатель на блок памяти (мелкий), в этом случае вы можете просто использовать:
void stackDel (tStack *stack) {
tNode *node = stackPop (stack);
while (node != NULL) {
free (node);
node = stackPop (stack);
}
free (stack);
}
но, если это указатель на память, удерживающий другие указатели на память, более проблематично автоматически освободить память, на которую он ссылается (это, вероятно, лучше всего сделать как обратный вызов вызывающей стороне API, поскольку это будет единственный зверь) что точно знал, как правильно освободить память). Гораздо проще сделать это предварительным условием для вызывающего абонента.