栈（链表实现）

fw_stack.h：

/* 栈先进后出，队列是先进先出，其它没什么区别了，可以认为都是线性表 */
#ifndef _FW_STACK_H_
#define _FW_STACK_H_
#include <stdio.h>

#define SUCC     1
#define FAIL    0

typedef struct fw_node_s {
    struct fw_node_s *prev;
    struct fw_node_s *next;
    int n;
}fw_node_t;

typedef struct fw_stack_s {
    fw_node_t *top;
    fw_node_t *bottom;
}fw_stack_t;

#define INIT_STACK(stack) do {\
    (stack)->top = NULL;\
    (stack)->bottom = NULL;\
} while(0)

int push_stack(fw_stack_t *stack, fw_node_t *new_node);

int pop_stack(fw_stack_t *stack, int *n);

void destroy_stack(fw_stack_t *stack);

void display_stack(fw_stack_t *stack);

int get_stack_top(fw_stack_t *stack, int *top_n);

#endif

 

fw_stack.c:

#include <memory.h>
#include

#include "fw_stack.h"

int push_stack(fw_stack_t *stack, fw_node_t *new_node)
{
    if (stack == NULL || new_node == NULL) {
        printf("%s:bad paras\n", __FUNCTION__);
        return FAIL;
    }

    if (stack->bottom == NULL) {
        stack->bottom = new_node;
        stack->top = new_node;
        return SUCC;
    }

    new_node->prev = stack->top;
    stack->top->next = new_node;
    stack->top = new_node;

    return SUCC;
}

int pop_stack(fw_stack_t *stack, int *n)
{
    fw_node_t *tmp;

    if (stack == NULL || n == NULL) {
        printf("%s:bad paras\n", __FUNCTION__);
        return FAIL;
    }

    if (stack->bottom == NULL) {
        return FAIL;
    }

    /* 如果只有一个元素 */
    if (stack->top == stack->bottom) {
        *n = stack->top->n;
        free(stack->top);
        stack->top = NULL;
        stack->bottom = NULL;
        return SUCC;
    }

    *n = stack->top->n;
    stack->top->prev->next = NULL;
    tmp = stack->top;
    stack->top = stack->top->prev;
    free(tmp);

    return SUCC;
}

void destroy_stack(fw_stack_t *stack)
{
    int n;

    if (stack == NULL) {
        printf("%s:bad paras\n", __FUNCTION__);
        return;
    }

    while (stack->bottom) {
        pop_stack(stack, &n);
    }

    return;
}

void display_stack(fw_stack_t *stack)
{
    fw_node_t *index;

    if (stack == NULL) {
        printf("%s:bad paras\n", __FUNCTION__);
        return;
    }

    printf("\nstack:\n");
    if (stack->bottom == NULL) {
        printf("NULL stack!\n");
        return;
    }

    printf(" == ");
    index = stack->top;
    while (index) {
        printf("%d<-", index->n);
        index = index->prev;
    }
    printf("\n");

    return;
}

int get_stack_top(fw_stack_t *stack, int *top_n)
{
    if (stack == NULL || top_n == NULL) {
        printf("%s:bad paras\n", __FUNCTION__);
        return FAIL;
    }

    if (stack->top == NULL) {
        printf("%s:top is NULL\n", __FUNCTION__);
        return FAIL;
    }

    *top_n = stack->top->n;

    return SUCC;
}

int main()
{
    fw_stack_t my_stack;
    fw_node_t *new_node;
    int op, n;

    INIT_STACK((&my_stack));
    while (1) {
        printf("====================================\n");
        printf("\n1:push 2:pop 3:get top node 4:quit\n");
        scanf("%d", &op);
        switch(op) {
        case 1:
            printf("input the number:\n");
            if (scanf("%d", &n) != 1) {
                while (getchar() != '\n') {
                }
                printf("input error!\n");
                break;
            }
            new_node = (fw_node_t *)malloc(sizeof(fw_node_t));
            if (new_node == NULL) {
                printf("malloc failed!\n");
                goto _quit;
            }
            memset(new_node, 0, sizeof(fw_node_t));
            new_node->n = n;
            if (push_stack(&my_stack, new_node) == FAIL) {
                printf("push failed!\n");
                free(new_node);
            }
            display_stack(&my_stack);
            break;
        case 2:
            if (pop_stack(&my_stack, &n) == FAIL) {
                printf("pop failed!\n");
            } else {
                printf("pop %d\n", n);
            }
            display_stack(&my_stack);
            break;
        case 3:
            if (get_stack_top(&my_stack, &n) == FAIL) {
                break;
            }
            printf("Get top %d\n", n);
            display_stack(&my_stack);
            break;
        case 4:
            display_stack(&my_stack);
            goto _quit;
        default:
            printf("error code!\n\n");
            while (getchar() != '\n');
            break;
        }
    }

_quit:
    destroy_stack(&my_stack);

    return 0;
}