《数据结构》课程教学课件（讲稿，C语言描述）第3章 栈和队列

3.1.5链栈1链栈结构及数据类型栈的链式存贮结构，也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图3-5。topan栈顶栈底图3-5链栈结构示意图

3.1.5 链栈 1．链栈结构及数据类型 栈的链式存贮结构,也称为链栈，它是一种限制运算 的链表，即规定链表中的插入和删除运算只能在链表 开头进行。链栈结构见图3-5。 头 a1 a2 top 栈顶 栈底 . an ^ 图 3-5 链栈结构示意图

2．链栈的五种栈运算（1）栈初始化void inistack(link *top)( top->next-NULL;}（2）进栈运算void push(link *top,int x)( link *s;,s= (elemtype *)malloc(maxsize*sizeof(elemtype)) ;s->data=x;s->next=top->next,top->next=s;

2．链栈的五种栈运算 （1）栈初始化 void inistack(link *top) { top->next=NULL;} （2）进栈运算 void push(link *top,int x) { link *s; s= (elemtype *)malloc(maxsize*sizeof(elemtype)) ; s->data=x; s->next=top->next; top->next=s; }

（3）退栈运算void pop(link *top)link *s,s-top->next,if(s!=NULL)top->next=s->nextfree(s);

（3）退栈运算 void pop(link *top) { link *s; s=top->next; if(s!=NULL) { top->next=s->next; free(s); } }

（4）取栈顶元素elemtype gettop(link *top)if(top->next!-NULL)return(top->next->data);elsereturn(NULL);子

（4）取栈顶元素 elemtype gettop(link *top) { if(top->next!=NULL) return(top->next->data); else return(NULL); }

（5）判栈空int empty(link *top)if(top->next--NULL)return(1);elsereturn(0)

（5）判栈空 int empty(link *top) { if(top->next==NULL) return(1); else return(0); }