算法－数据结构－堆栈

/****************************************************************
Title : stack.c
Author : 张龙
Time : 200508
*****************************************************************/




#include "stdio.h"




#define STACK_SIZE 100




typedef int ElementType;

typedef struct _stacknode
{
ElementType data;
struct _stacknode *next;
} stacknode;

typedef struct _stack
{
stacknode *top,*bottom;
int count;
} stack;




/*========================functions declaration===================*/
void init(stack *s);
int IsEmpty(stack *s);
int IsFull(stack *s);
int GetStackSize();
int length(stack *s);
ElementType top(stack *s);
int push(stack *s,ElementType x);
int pop(stack *s);




/*====================function implementation================*/
void init(stack *s)
{
s->top=s->bottom=0;
s->count=0;
}

int IsEmpty(stack *s)
{
if(!s->count)
return 1;
else
return 0;
}

int IsFull(stack *s)
{
if(s->count==STACK_SIZE)
return 1;
else
return 0;
}

int GetStackSize()
{
return STACK_SIZE;
}

int length(stack *s)
{
return s->count;
}

ElementType top(stack *s)
{
return s->top->data;
}

int push(stack *s,ElementType x)
{
stacknode *node;

if(IsFull(s)){
printf("the stack is full,no new data can be inserted.\n");
return 0;
}

if(!s->bottom){
node=s->bottom=s->top=(stacknode *)malloc(sizeof(stacknode));
node->data=x;

}
else{
node=(stacknode *)malloc(sizeof(stacknode));
node->data=x;
s->top->next=node;
s->top=node;
}

s->count++;

return;
}

ElementType pop(stack *s)
{
int i,j;

ElementType data;
stacknode *node;

if(IsEmpty(s)){
printf("the stack is empty,no data is popped up\n");
return 0;
}

data=s->top->data;
free(s->top);
s->count--;
j=s->count;


if(j==1){
s->top=s->bottom;
s->top->next=0;
}
else{
for(i=0;i if(i==0){
node=s->bottom;
}
else{
node=node->next;
}
}
s->top=node;
s->top->next=0;
}

return data;
}



/*========================main function========================*/
int main(int argc,char*argv[])
{
int i,j;
stack *mystack;

mystack=(stack *)malloc(sizeof(stack));

init(mystack);

for(i=0;i<100;i++){
j=i+3;
push(mystack,j);
printf("%d ",top(mystack));
}
printf("\n");
printf("the size of stack is %d\n",GetStackSize());
printf("the current length of stack is %d\n",length(mystack));


for(i=0;i<50;i++){
printf("%d ",pop(mystack));

}
printf("\n");
printf("the size of stack is %d\n",GetStackSize());
printf("the current length of stack is %d\n",length(mystack));

return 1;

}