剑指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