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)

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程