C语言用指针支持栈

栈数据结构也是一种链表。对于栈，元素被推入栈顶，然后被弹出。当多个元素被推入和弹出时，栈的行为是先进后出（FILO）。第一个推入栈的元素最后一个弹出。

就像队列的实现，我们可以用链表来支持栈操作。最常见的两种操作是入栈和出栈。我们用addHead函数实现入栈操作，出栈操作需要增加一个新函数来删除头节点。我们先定义栈：

typedef LinkedList Stack;

要初始化栈，需要添加initializeStack函数，这个函数调用initializeList函数：

void initializeStack(Stack *stack) {
    initializeList(stack);
}

入栈操作调用addHead函数，如下所示：

void push(Stack *stack, void* data) {
    addHead(stack, data);
}

下面是出栈操作的实现，我们先把栈的头节点赋给一个节点指针，这里涉及三种情况。

• 栈为空
  函数返回NULL。
• 栈中有一个元素
  如果节点指向尾节点，那么头节点和尾节点是同一个元素。将头节点和尾节点置为NULL，然后返回数据。
• 栈中有多个元素
  在这种情况下，我们将头节点赋值为链表中的下一个元素，然后返回数据。

在后两种情况下，节点会被释放：

void *pop(Stack *stack) {
    Node *node = stack->head;
    if (node == NULL) {
        return NULL;
    } else if (node == stack->tail) {
        stack->head = stack->tail = NULL;
        void *data = node->data;
        free(node);
        return data;
    } else {
        stack->head = stack->head->next;
        void *data = node->data;
        free(node);
        return data;
    }
}

我们会重复利用6.4.1节中创建的雇员实例来说明栈的用法。下面的代码片段会把三个雇员入栈再出栈：

Stack stack;
initializeStack(&stack);

push(&stack, samuel);
push(&stack, sally);
push(&stack, susan);

Employee *employee;

for(int i=0; i<4; i++) {
    employee = (Employee*) pop(&stack);
    printf("Popped %s\n", employee->name);
}

执行后得到如下输出。因为我们调用了四次出栈函数，最后一次会返回NULL：

Popped Susan
Popped Sally
Popped Samuel
Popped (null)

有时候还有其他的栈操作，如查看栈顶元素，它会返回栈顶的元素，但不会将其弹出。