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


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

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注