用链表实现堆栈

堆栈数据一种后进先出的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。基本的堆栈操作是push和pop，push是把一个新值压入堆栈的顶部，pop是把堆栈的顶部的值移除并返回这个值。堆栈只提供对它的栈顶值的访问。
堆栈很容易实现，可以用静态数组、动态数组、链表实现堆栈。本文介绍的是链表实现的堆栈。

#include <stdio.h> 
#include <malloc.h> 

#define STACK_TYPE int

void push(STACK_TYPE value);
void pop(void);
STACK_TYPE top(void);
bool isEmpty(void);
int isFull(void);

typedef struct Node
{
    int data;
    struct Node * pNext;
}NODE, * PNODE;

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
}STACK, * PSTACK;
//全局变量栈顶指针 stack
static PNODE stack;

//堆栈是否为空 
bool isEmpty(void)
{
    //return (stack==NULL)? true : false;
    return stack==NULL;
}

//链式堆栈不会满 
int isFull(void)
{
    return false;
}

//压入堆栈 
void push(STACK_TYPE value)
{
    PNODE pNew = (PNODE)malloc(sizeof(Node));
    if(pNew == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    pNew->pNext = stack;
    pNew->data = value;
    stack = pNew;
} 

//移除栈顶元素 ，并获取元素的数据 
void pop(void)
{
    if(isEmpty())
    {
        printf("is empty\n");
    }
    else
    {
        PNODE pTmp = stack;
        stack = stack->pNext;
        free(pTmp);
        pTmp = NULL;
    }
}

//返回栈顶元素的数据 
STACK_TYPE top(void)
{
    if(isEmpty())
    {
        printf("top failed because is empty\n");
        return -1;
    }
    else
    {
        return stack->data;
    }
}

int main()
{
    int val = 0;
    printf("把数据1,2,3依次压入堆栈\n"); 
    push(1);
    push(2);
    push(3);
    val = top();
    printf("当前栈顶元素为：%d\n",val); 
    printf("移除栈顶元素\n");
    pop();
    val = top();
    printf("当前栈顶元素为：%d\n",val); 
    printf("移除栈顶元素\n");
    pop();
    val = top();
    printf("当前栈顶元素为：%d\n",val); 

    return 0;
}

实验结果：

程序很简单，执行push操作把数据1,2,3依次压入堆栈，这时发现最后进去的数据项是在栈顶。然后依次执行pop操作，发现后push进去的元素先移除。由于堆栈的链式结构比较简单，这里就不再详细叙述了，等以后有时间，再补充堆栈的具体应用和堆栈的数组实现。