用鏈表實現棧

一、頭文件：  

#ifndef _STACK_LINK_H_  
#define _STACK_LINK_H_  
  
struct stack_record;  
typedef struct stack_record* stack;  
typedef int elementType;  
struct link_node;  
typedef struct link_node node;  
  
int IsEmpty(stack s);  
int IsFull(stack s);  
stack creatStack(int maxElement);  
void disposeStack(stack s);  
void makeEmpty(stack s);  
void pushElement(elementType x,stack s);  
elementType Top(stack s);  
void popElement(stack s);  
elementType topAndpop(stack s);  
  
#define EMPTY 0  
#define MINISIZE (5)  
  
struct stack_record  
{  
    int capacity;  
    int size;  
    node *item;   
};  
  
struct link_node  
{  
    elementType data;  
    node *next;  
};  
  
#endif  

#include <stdio.h>  
#include <stdlib.h>  
#include "stack_link.h"  
  
  
#define MAXSIZE 100  
  
int IsEmpty(stack s)  
{  
    return s->size == 0;  
}  
  
int IsFull(stack s)  
{  
    return s->size == s->capacity;   
}  
  
stack creatStack(int maxElement)  
{  
    stack s;  
    s = (stack)malloc(sizeof(struct stack_record));  
    if(s == NULL)  
    {  
    printf("the stack alloca error\n");  
    exit(-1);  
    }  
  
    s->capacity = MAXSIZE;  
    s->item = NULL;  
    s->size = 0;  
      
    return s;  
}  
  
  
void disposeStack(stack s)  
{  
    if(s)  
    {  
    if(s->size)  
        makeEmpty(s);  
      
    free(s);  
    }  
}  
  
void makeEmpty(stack s)  
{  
    if(s)  
    {  
    while(s->size)  
    {  
        popElement(s);  
    }  
    }  
}  
  
void pushElement(elementType x,stack s)  
{  
    if(s)  
    {  
    if(IsFull(s))  
        return;  
      
        node *ptr = (node *)malloc(sizeof(node));  
    if(NULL == ptr)  
    {  
        printf("the node alloc is error\n");  
        exit(-2);  
    }  
      
    ptr->data = x;  
    ptr->next = s->item;  
    s->item = ptr;  
    s->size++;  
    }  
}  
  
elementType Top(stack s)  
{  
    if(s)  
    {  
    if(IsEmpty(s))  
    {  
        printf("the stack is empty\n");  
        exit(-3);  
    }      
        return s->item->data;  
    }  
}  
  
void popElement(stack s)  
{  
    if(IsEmpty(s) )  
    {  
    printf("the stack is empty\n");  
    exit(-4);  
    }  
  
    node *ptr = NULL;  
    ptr = s->item->next;  
    free(s->item);  
    s->item = ptr;  
    s->size--;  
}  
  
elementType topAndpop(stack s)  
{  
    if(s)  
    {  
    if(IsEmpty(s))  
    {  
        printf("the stack is empty\n");  
        exit(-5);  
    }  
  
    elementType x;  
    x = Top(s);  
    popElement(s);  
    return x;  
    }  
}  
  
  
  
int main(int argc,char *argv[])  
{  
    stack s;  
      
    s = creatStack(10);  
    int i = 0;  
    elementType x;  
    while(++i <= 10)  
    {  
    pushElement(i,s);  
    printf("the stack size is %d\n",s->size);  
    x = Top(s);  
    printf("the stack top is %d\n",x);  
    }  
  
    while(s->size)  
    {  
    x = topAndpop(s);  
    printf("the top stack is %d\n",x);  
    sleep(1);  
    }  
  
    disposeStack(s);  
  
    return 0;  
}  

the stack size is 1  
the stack top is 1  
the stack size is 2  
the stack top is 2  
the stack size is 3  
the stack top is 3  
the stack size is 4  
the stack top is 4  
the stack size is 5  
the stack top is 5  
the stack size is 6  
the stack top is 6  
the stack size is 7  
the stack top is 7  
the stack size is 8  
the stack top is 8  
the stack size is 9  
the stack top is 9  
the stack size is 10  
the stack top is 10  
the top stack is 10  
the top stack is 9  
the top stack is 8  
the top stack is 7  
the top stack is 6  
the top stack is 5  
the top stack is 4  
the top stack is 3  
the top stack is 2  
the top stack is 1