链栈的基本操作C/C++代码实现

爱被打了一巴掌 2023-02-14 15:31 151阅读 0赞

## 链栈的结构： ##

![在这里插入图片描述][20200603120507609.png]  
由于栈的主要操作是在栈顶插入和删除， 显然以链表的头部作为栈顶是最方便的，且不需要附加一个头结点。

## 初始化： ##

栈顶指针S置空即可。

## 入栈： ##

链栈不需要判断栈是否满！  
![在这里插入图片描述][20200603120926505.png]

## 出栈： ##

栈顶指针S等于NULL表空栈，即链栈S==NULL时为空栈。  
![在这里插入图片描述][20200603121123981.png]

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 100
    typedef int SElemType;
    
    //链栈的存储结构
    typedef struct StackNode
    {
        
    	SElemType data;
    	struct StackNode *next;
    }StackNode,*LinkStack;
    
    //初始化
    void InitStack(LinkStack &S)
    {
        
    	S = NULL;	//构造一个空栈，栈顶指针置空即可
    }
    
    //入栈
    int Push(LinkStack &S, SElemType e)
    {
        
    	//链栈不需要判断栈满
    
    	StackNode *p = new StackNode;
    	p->data = e;
    	p->next = S;
    	S = p;
    	return 1;
    }
    
    //出栈
    int Pop(LinkStack &S, SElemType &e)
    {
        
    	if (S==NULL) return 0;    //栈空
    
    	StackNode *p = S;
    	e = S->data;
    	S = S->next;
    	delete p;
    	return 1;
    }
    
    //取栈顶元素
    SElemType GetTop(LinkStack S)
    {
        
    	if (S!=NULL)	 //非栈空时返回
    		return S->data;   
    }
    
    //遍历输出栈
    void printStack(LinkStack S)
    {
        
    	printf("栈顶->");
    	StackNode *p = S;
    	while (p!=NULL)
    	{
        
    		printf("%d ",p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
        
    	LinkStack S;
    	int e;
    	InitStack(S);
    	printf("请输入一个要入栈的元素（-1表示结束）：");
    	scanf("%d",&e);
    	while (e!=-1)
    	{
        
    		Push(S,e);
    		printf("请输入一个要入栈的元素（-1表示结束）：");
    		scanf("%d", &e);
    	}
    	printStack(S);
    	printf("出栈测试：");
    	Pop(S, e);
    	printStack(S);
    
    	printf("取栈顶元素测试：");
    	e=GetTop(S);
    	printf("取出的栈顶元素为：%d\n",e);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

[20200603120507609.png]: https://img-blog.csdnimg.cn/20200603120507609.png
[20200603120926505.png]: https://img-blog.csdnimg.cn/20200603120926505.png
[20200603121123981.png]: https://img-blog.csdnimg.cn/20200603121123981.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200603121417291.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70