数据结构系列－链栈的基本操作

╰半橙微兮° 2022-05-29 03:25 224阅读 0赞

栈的链式存储结构，可以称为链栈。

针对单链表的链栈，栈顶指针就是头指针。对于链栈来说，不存在栈满的情况，当然是内存足够的情况下。对于空栈来说就是top　＝ＮＵＬＬ。

相对的顺序栈要实现确定一个固定的长度，但是顺序栈存取时的定位很简洁。

链栈对于长度没有限制，但是每个元素要多个指针域，也就多了一些内存开销。

链栈的存储结构及操作：

#include "stdio.h"
    #include "stdlib.h"
    #include "io.h"
    #include "math.h"
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 20
    
    typedef int Status;
    typedef int SElemType;
    
    //存储结构,
    typedef struct StackNode{ //每个结点的类型
    	SElemType data;
    	struct StackNode *next;
    }StackNode,*LinkStackPtr;
    
    //链式栈的结构
    typedef struct{
    	LinkStackPtr top;
    	int count;
    }LinkStack;
    
    //访问元素
    Status visit(SElemType se){
    	printf(" %d ",se);
    	return OK;
    }
    
    //遍历栈元素
    Status StackTraverse(LinkStack lS){
    	LinkStackPtr p;
    	p = lS.top;
    	while(p){
    		visit(p->data);
    		p= p->next;
    	}
    	printf("\n");
    	return OK;
    }
    
    //初始化一个空栈
    Status InitStack(LinkStack *lS){
    	lS->top = (LinkStackPtr)malloc(sizeof(StackNode));
    	if(!lS->top)
    		return ERROR;
    	lS->top =NULL;
    	lS->count =0;
    	return OK;
    }
    
    //清空栈
    Status ClearStack(LinkStack *lS){
    	LinkStackPtr p,q;
    	p =lS->top;
    	while(p){
    		q=p;
    		p = p->next;
    		free(q);
    	}
    	lS->count =0;
    	return OK;
    }
    
    //判断是否为空栈
    Status StackEmpty(LinkStack lS){
    	if(lS.count == 0)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    //获取栈的长度
    int StackLength(LinkStack lS){
    	return lS.count;
    }
    
    //获取栈顶元素,用参数ｅ返回
    Status GetTop(LinkStack lS,SElemType *se){
    	if(lS.top == NULL)
    		return ERROR;
    	else
    		*se = lS.top->data;
    	return OK;	
    }	
    
    //入栈元素到栈顶
    Status Push(LinkStack *lS,SElemType se){
    	LinkStackPtr s= (LinkStackPtr)malloc(sizeof(StackNode));
    	s->data = se;
    	s->next =lS->top;//新元素的后继指针指向当前的栈顶元素
    	lS->top = s;//让栈顶指针指向新的结点元素
    	lS->count++;
    	return OK;
    }
    
    //栈顶元素出栈
    Status Pop(LinkStack *lS,SElemType *se){
    	LinkStackPtr p;
    	if(StackEmpty(*lS))
    		return ERROR;
    	*se = lS->top->data;
    	p = lS->top;//让ｐ指向栈顶结点
    	lS->top = lS->top->next;//让栈顶指针指向它的后继
    	free(p);
    	lS->count--;
    	return OK;
    }
    
    int main()
    {
            int j;
            LinkStack s;
            int e;
            if(InitStack(&s)==OK)
                    for(j=1;j<=10;j++)
                            Push(&s,j);
            printf("栈中的元素：");
            StackTraverse(s);
            Pop(&s,&e);
            printf("出栈的元素 e=%d\n",e);
    
            ClearStack(&s);
            printf("清空栈后的栈长度：%d \n",StackLength(s));
            return 0;
    }

运行结果：

![Image 1][]

[Image 1]: