标签： 栈

C基于链表实现栈

本篇内容中的链表是之前的文章中实现的，请参阅文章 C-单链表的实现 。

栈的特性

先进后出（First-In-Last-Out, FILO）.

像队列实现一样，有2个主要的操作：

一）push 操作将元素入栈。

二）pop 操作将元素出栈。

栈的实现

基于单链表实现，push 入栈操作就是往链表的头部添加数据元素，pop 出栈操作就是从链表的头部删除数据元素。

以下是栈的定义以及主要操作：

// 定义栈
typedef LinkedList Stack;
// 初始化栈
void initStack(Stack *stack)
{
    init_linkedlist(stack);
}
// 入栈，在链表头部添加元素
void push(Stack *stack, void *data)
{
    addHead(stack, data);
}
// 出栈，从链表头部删除元素
void* pop(Stack *stack)
{
    pNode node = stack->head;
    void* data;
    if (stack->head == NULL) {
        data = NULL;
    } else if (stack->head == stack->tail) {
        stack->head = stack->tail = NULL;
        data = node->data;
        free(node);
    } else {
        stack->head = node->next;
        data = node->data;
        free(node);
    }

    return data;
}

示例说明

    Stack stack;
    // 初始化
    initStack(&stack);
    int a = 20;
    int b = 30;
    int c = 40;
    int *ptr_1 = &a;
    int *ptr_2 = &b;
    int *ptr_3 = &c;

    push(&stack, ptr_1);
    push(&stack, ptr_2);
    push(&stack, ptr_3);

    int *ptr = NULL;
    for (int i = 0; i < 3; i++)
    {
        ptr = (int *)pop(&stack);
        printf("Popped %d\n", *ptr);
    }

运行结果：

Popped 40
Popped 30
Popped 20

以上内容如有错误，欢迎留言指出交流或者关注公众号交流。