算法:C语言实现 (4)下推栈的链表实现

一  通用数据类型的定义

不依赖于对象类型的代码，其中我们使用typedef来制定项的类型.

typedef int Item;

#define eq(A,B) (A == B)

二  接口的定义

接口中并不包含如何实现函数的信息，甚至也没有关于任何关于任何运行的信息。p79页重点讲解“接口”，还有就是接口的作用..在接口中明确定义了算法在通用对象上执行所需的操作。这种机制允许我们无需向客户程序提供关于数据表示的任何信息，也就真正给了我们一个真实的ADT。

void STACKinit(int);
int STACKempty(void);
void STACKpush(Item);
Item STACKpop();

三  接口的实现

#include <stdlib.h>
#include "item.h"

typedef struct STACKnode * link;
struct STACKnode {Item item; link next;};

/************************************************************************/
/* 设置一个指向头结点地址不变的   头指针head                                 */
/************************************************************************/
static link head;

link NEW(Item item, link next)
{
    link x = (link) malloc(sizeof(*x));
    x->item = item;
    x->next = next;
    return x;
}

void STACKinit(int maxN)
{
    head = NULL;
}

int STACKempty()
{
    return head == NULL;
}

/************************************************************************/
/* 压入栈的时候, 设定了一个不变的头指针, 然后每次都会依次让这个头指针指向新插入的节点  */
/************************************************************************/
void STACKpush(Item item)
{
    head = NEW(item,head);
}

/************************************************************************/
/* 弹出栈的时候, 就把head所指的节点数据弹出    */
/************************************************************************/
Item STACKpop()
{
    Item item = head->item;
    link t = head->next;
    free(head);
    head = t;
    return item;
}