剑指offer之用链表实现栈(带头节点)

1 问题

用链表实现栈,栈先进后出.

 
2 代码实现

    #include <stdio.h>
    #include <stdlib.h>
     
    #define true 1
    #define false 0
     
    typedef struct Node
    {
        int value;
        struct Node *next;
    } Stack;
     
     
    /*
     *打印栈
     */
    void print(Stack *stack)
    {
        if (stack == NULL)
        {
            printf("stack is NULL\n");
            return;
        }
        struct Node *p = stack->next;
        while (p != NULL)
        {
            printf("value is: %d\n", p->value);
            p = p->next;
        }
        return;
    }
     
     
    /**
     *给栈添加一个节点
     */
    int add_node(Stack *stack, int value)
    {
        if (stack == NULL)
        {
            printf("stack is NULL\n");
            return false;
        }
        struct Node *node = NULL;
        node = (struct Node *)malloc(sizeof(struct Node));
        if (node == NULL)
        {
            printf("addNode malloc fail\n");
            return false;
        }
        node->value = value;
        node->next = stack->next;
        stack->next = node;
        return true;
    }
     
     
    /*
     *初始化栈
     */
    struct Node* init()
    {
        struct Node *head = NULL;
        head = (struct Node *)malloc(sizeof(struct Node));
        if (head == NULL)
        {
            return NULL;
        }
        head->next = NULL;
        head->value = 0;
        return head;
    }
     
     
    /*
     *打印栈的大小
     */
    int size_stack(Stack *stack)
    {
        if (stack == NULL)
        {
            return 0;
        }
        Stack *head = stack->next;
        int size = 0;
        while (head != NULL)
        {
            ++size;
            head = head->next;
        }
        return size;
    }
      
     
    /*
     *弹出栈顶元素
     */
    int pop_stack(Stack *stack)
    {
        if (stack == NULL)
        {
            printf("stack is NULL");
            return false;
        }
        struct Node *p = stack->next;
        if (p == NULL)
        {
            printf("stack->next is NULL");
            return false;
        }
        stack->next = p->next;
        free(p);
        return true;
    }
     
    /*
     *获取栈顶元素
     */
    struct Node* top_stack(Stack *stack)
    {
        /**if (stack == NULL);这里自己傻逼了,多加了一个分号导致程序走到里面
        {
            printf("stack1 is NULL\n");
            return NULL;
        }**/
        if (stack == NULL)
        {
            printf("stack is is is NULL\n");
            return NULL;
        }
        struct Node *p = stack->next;
        if (p == NULL)
        {
            printf("stack->next is NULL");
            return NULL;
        }
        return p;
    }
     
    void clear_stack(Stack *stack)
    {
        if (stack == NULL)
        {
            return;
        }
        struct Node *q, *p = stack->next;
        while(p != NULL)
        {
            q = p;
            p = p->next;
            free(q);
        }
        stack->next = NULL;
    }
     
     
    int main()
    {
     
        struct Node *head = init();
        if (head == NULL)
        {
            printf("init stack fail\n");
            return false;
        }
        printf("init success\n");
        add_node(head, 1);
        add_node(head, 2);
        add_node(head, 5);
        add_node(head, 4);
        add_node(head, 3);
        print(head);
        struct Node* top = top_stack(head);
        if (top != NULL)
        {
            printf("top value is %d\n", top->value);
        }
        printf("stack size is %d\n", size_stack(head));
        int result = pop_stack(head);
        if (result == true)
        {
            printf("pop_stack success\n");
        }
        else
        {
            printf("pop_stack fail\n");
        }
        print(head);
        printf("stack size is %d\n", size_stack(head));
        clear_stack(head);
        if (head == NULL)
        {
            printf("head is NULL\n");
        }
        printf("stack size is %d\n", size_stack(head));
        head = init();
        if (head == NULL)
        {
            printf("init stack fail\n");
            return false;
        }
        printf("init success\n");
        add_node(head, 6);
        add_node(head, 5);
        add_node(head, 2);
        add_node(head, 1);
        add_node(head, 9);
        print(head);
        printf("stack size is %d\n", size_stack(head));
        return true;
    }

 
3 运行结果

    init success
    value is: 3
    value is: 4
    value is: 5
    value is: 2
    value is: 1
    top value is 3
    stack size is 5
    pop_stack success
    value is: 4
    value is: 5
    value is: 2
    value is: 1
    stack size is 4
    stack size is 0
    init success
    value is: 9
    value is: 1
    value is: 2
    value is: 5
    value is: 6
    stack size is 5



 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)