实现一个通用栈（类型是void *）

bob_zhang2004

• 
  
  文件:
  BST_operation.zip
  大小:
  3KB
  下载:
  下载
  stack_lib.h

/*
* 我也遵循GPL协议
* Copyright (C) 2008 Bob Zhang
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
/* ===================================================================================
* 用链式存储结构实现一个栈
* 我们的策略是用栈或者链表的时候， 都是先构造一个节点，
* 然后把节点插入链表或者入栈或者出栈
* 其实就用往header的后面不断的插入数据
* 其实，栈就是单链表的特例，为什么教科书搞的那么复杂呢？
* ==================================================================================*/
#include stdio.h>
#include stdlib.h>
#include string.h>
typedef struct node_t {
    void *data_p; //可以兼容所有的数据类型
    struct node_t *next;
}node_t;
//当top = header的时候，说明是空栈
typedef struct stack_t {
    node_t *top;    //栈顶    其实就是相当于链表的header
//    int size;    //元素个数
}stack_t;
//初始化一个节点
#define INIT_NODE(node,ptr) do { node->data_p = ptr; node->next = NULL; } while(0)
//声明一个节点
#define DECLARE_NODE(name,ptr) \
    node_t *name = (node_t *)malloc(sizeof(node_t));\
    INIT_NODE(name,ptr);
//初始化一个栈
#define INIT_STACK_TOP(stack)    \
    stack->top = (node_t *)malloc(sizeof(node_t));        \
    stack->top->next = NULL;
   
   
//声明一个栈
#define DECLARE_STACK(STACK_NAME) \
    stack_t *STACK_NAME = (stack_t *)malloc(sizeof(stack_t)); \
    INIT_STACK_TOP(STACK_NAME); \
/* 函数声明 */
extern int push(stack_t * stack,node_t *node);        //入栈
extern int pop(stack_t *stack,node_t **pop_node);    //出栈,返回值来判断是否成功，pop_node表示弹出的节点
extern int empty_stack(stack_t *stack);                //是否空栈
extern int free_stack(stack_t *stack);

• stack_lib.c

//我的这个栈是个通用栈
//因为node->data_p 是个void类型指针，你可以随意存放你想入栈的数据类型
//用法如下：for example
//        
//    DECLARE_NODE(stack_node,pointer); //pointer是要入栈的数据，但是我必须把赋值给一个节点的data_p
//    push(RCHILD_STACK,stack_node);
//            
#include "stack_lib.h"
/* 函数实现 */
//对于push来说比链表更简单， 直接更新top后面的第一个节点就好了
int push(stack_t * stack,node_t *node)   
{
    node->next = stack->top->next;
    stack->top->next = node;
   
    return 0;
   
}
//这里必须传二重指针，试想如果传 node_t *node_p肯定不行
int pop(stack_t *stack, node_t **node_p)
{
    node_t *top = stack->top;
   
    if(!top->next)
    {
        printf("this is empty stack \n");
        return -1;
    }
   
    *node_p = top->next;
    //只需删掉top后面节点即可，并返回给node_p
    top->next = top->next->next;
   
    //这时候已经是孤立的节点了
    (*node_p)->next = NULL;    //这里很关键， 一定要在这里，不能在上面一行，因为这是旧的头结点
   
    return 0;
}
int free_stack(stack_t *stack)
{
    free(stack->top);
    free(stack);
   
    return 0;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/22617/showart_1387160.html