栈的链式存储的基本操作

墨蓝 2022-03-25 14:30 253阅读 0赞

**1 :链式存储结构  
　　栈的链式存储结构，简称链栈。  
　　由于栈只是栈顶在做插入和删除操作，所以栈顶应该放在单链表的头部。另外，都有了栈顶在头部了，单链表中的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。  
　　对于链栈来说，基本不存在栈满的情况，除非内存已经没有使用空间了。  
　　对于空栈来说，链表原来的定义是头指针指向空，那么链栈的空其实就是top＝NULL。**

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    #define  ERROR 0
    #define  OK    1
    
    typedef int Status;
    typedef int Elemtype;
    /*链栈结构*/
    
    typedef struct StackNode {
    	Elemtype data;          //结点数据域 
    	struct StackNode *next; //结点指针域 
    }StackNode,*LinkStackPtr;
    
    typedef struct{
    	LinkStackPtr top;       //栈顶指针相当于头指针 
    	int count;              //栈的元素 
    }LinkStack; 
    
    void InitStack(LinkStack *S)
    {
    	S->top=NULL;         //初始化栈顶指针为空 
    	S->count=0;
    }
    
    void PushStack(LinkStack *S,Elemtype e)
    {
    	StackNode *q;
    	q=(LinkStackPtr)malloc(sizeof(StackNode));
    	assert( q != NULL);
    	q->data=e;
    	
    	q->next=S->top;     //头插法建栈 
    	S->top=q;
    	S->count++;        //栈长加一 
    }
    
    Status GetTop(LinkStack *S,Elemtype *e)
    {
    	if(S->top == NULL)
    	{
    		return ERROR;
    	}
    	*e = S->top->data;
    	return OK;
    }
    
    Status StackEmpty(LinkStack *S)
    {
    	if(S->top == NULL)
    	{
    		return OK;
    	}
    	return ERROR;
    }
    
    void StackTraverse(LinkStack S)
    {
    	LinkStackPtr p;
    	p = S.top;
    	while(p)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
    
    Status ClearStack(LinkStack *S)
    {
    	if(!S->top||!S->count)
    	{
    		return ERROR;
    	}
    	StackNode *q = S->top;
    	while(q)
    	{
    		S->top = q->next;
    		free(q);
    		q=S->top;
    		S->count--;
    	}
    	return OK;
    }
    
    Status PopStack(LinkStack *S,Elemtype *e)
    {
    	StackNode *q;
    	if(S->top == NULL)
    	{
    		return ERROR;
    	}
    	*e = S->top->data;
    	
    	q = S->top;
    	S->top = S->top->next;
    	free(q);
    	S->count--;
    	return OK;
    }
    
    int main()
    {
    	int i,value;
    	Elemtype e;
    	LinkStack S;
    	InitStack(&S);
    	for(i=2;i<20;i+=2)
    		PushStack(&S,i);
    	printf("遍历栈为："); 
    	StackTraverse(S);
    	printf("栈长为：%d",S.count); 
    	
    	
    	PopStack(&S,&e);
    	printf("\n弹出的栈顶元素为：%d",e);
    	printf("\n栈长为：%d",S.count);
    	printf("\n新的栈顶元素为：");
    	GetTop(&S,&e);
    	printf("%d",e);
    	
    	if(ClearStack(&S))
    		printf("\n清除栈后栈长为：%d",S.count);
    	else
    		printf("栈空！\n"); 
    	return 0;
    }

**运行效果截图如下：**  
![在这里插入图片描述][20190123235831660.png]

[20190123235831660.png]: /images/20220325/9798f1d077494ecda01770688e37be75.png