有趣的数据结构算法8——栈的初始化、入栈与出栈

Dear 丶 2021-11-26 08:32 365阅读 0赞

### 有趣的数据结构算法8——栈的初始化、入栈与出栈 ###

*  什么是栈
 *   *  栈的初始化
     *  入栈
     *  出栈
 *  实现代码
 *  GITHUB下载连接

新的结构又要出现了。我心里有点害怕，但是！  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 什么是栈 #

栈（stack）又名堆栈，它是一种运算受限的线性表。它的限定只可以在**表尾进行插入和删除**。进行操作的这一端被称为栈顶，另一端是栈底。向一个栈插入新元素又称作入栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈，它是把栈顶元素取出，使其相邻下方的元素成为新的栈顶元素。  
它的实际情况如图所示（图片取自百度百科）：  
![栈的示意图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70]  
图片的上方三个为入栈示意图，下方三个为出栈示意图。

## 栈的初始化 ##

对栈进行操作前要定义栈的结构体。

struct stack{
        		//stacksize是整型。
    	int stacksize;  //指的是这个栈的最大size
    	EleType* top;	//top指的指针是最后一位数据的后一个
    	EleType* base;  //base指的指针是最低位的指针。
    };

top指向栈顶的后一位（这样可以便于操作），base指向栈底，stacksize表示当前栈允许的最大栈数。  
在完成栈的定义后要进行栈的初始化。  
初始化的过程可以分为三步，分别为：  
**1、栈申请空间**  
**2、修改stacksize的大小**  
**3、栈顶指向栈底**。

void init(struct stack* STA){
        
    	STA->base = (EleType *)malloc(maxsize * sizeof(EleType));	//为base申请内存空间。
    	if (!STA->base){
        											//如果没有申请上，则推出
    		exit(1);
    	}
    	STA->stacksize = maxsize;	//更改stacksize的大小；
    	STA->top = STA->base;		//初始化的时候顶端指向尾端
    }

## 入栈 ##

如何进行入栈呢？从入栈函数出发，入栈函数需要输入一个栈和一个入栈的元素。

void insert(struct stack* STA, EleType e);

元素入栈的过程也可以分为三步，分别为：  
**判断栈是否满，满则动态申请空间**  
**将元素压入栈( \*(STA->top) = e; )**  
**栈顶指针加1( (STA->top)++ );**

void insert(struct stack* STA, EleType e){
        	//插入数据
    	int len;
    	EleType* m;
    	len = STA->top - STA->base;				//计算总体长度
    	if (len >= STA->stacksize){
         //如果
    
    		m = (EleType *)realloc(STA->base, (STA->stacksize + maxsize)*sizeof(EleType));
    		if (!m){
        
    			exit(1);
    		}
    		STA->stacksize = STA->stacksize + maxsize;//更新stacksize的值
    		STA->base = m; //更新base的值
    		STA->top = m + len; //更新top的值
    	}
    	*(STA->top) = e; //STA->top的值更新，更新后top++
    	(STA->top)++;
    }

## 出栈 ##

如何进行出栈呢？从出栈函数出发，出栈函数需要输入一个栈。

EleType pop(struct stack* STA);

返回值为一个元素。  
元素入栈的过程也可以分为三步，分别为：  
**判断是否到达栈底，是则报错**  
**栈顶指针减1( (STA->top)-- );**  
**取出栈顶元素**

EleType pop(struct stack* STA){
        
    	char c;
    	if (STA->top == STA->base){
        
    		exit(1);	//非法访问，异常退出
    	}
    	STA->top--;		//应当先将top--，再进行取值
    	c = *(STA->top);	//top为指针
    	return c;
    }

# 实现代码 #

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    
    
    #define maxsize 100 //最大size为100
    typedef char EleType; //这个地方要用typedef，不可以用define
    struct stack{
        		//stacksize是整型。
    	int stacksize;  //指的是这个栈的最大size
    	EleType* top;	//top指的指针是最后一位数据的后一个
    	EleType* base;  //base指的指针是最低位的指针。
    };
    
    void init(struct stack* STA){
        
    	STA->base = (EleType *)malloc(maxsize * sizeof(EleType));	//为base申请内存空间。
    	if (!STA->base){
        											//如果没有申请上，则推出
    		exit(1);
    	}
    	STA->stacksize = maxsize;	//更改stacksize的大小；
    	STA->top = STA->base;		//初始化的时候顶端指向尾端
    }
    
    void insert(struct stack* STA, EleType e){
        	//插入数据
    	int len;
    	EleType* m;
    	len = STA->top - STA->base;				//计算总体长度
    	if (len >= STA->stacksize){
         //如果
    
    		m = (EleType *)realloc(STA->base, (STA->stacksize + maxsize)*sizeof(EleType));
    		if (!m){
        
    			exit(1);
    		}
    		STA->stacksize = STA->stacksize + maxsize;//更新stacksize的值
    		STA->base = m; //更新base的值
    		STA->top = m + len; //更新top的值
    	}
    	*(STA->top) = e; //STA->top的值更新，更新后top++
    	(STA->top)++;
    }
    
    EleType pop(struct stack* STA){
        
    	char c;
    	if (STA->top == STA->base){
        
    		exit(1);	//非法访问，异常退出
    	}
    	STA->top--;		//应当先将top--，再进行取值
    	c = *(STA->top);	//top为指针
    	return c;
    
    }
    
    int main(void){
        
    
    	struct stack STA, STA_8; //这个地方不能直接定义指针，指针要要指向。
    	EleType a;
    
    	init(&STA); //使用地址
    	init(&STA_8);
    
    	printf("请输入一段字符串：");
    	scanf("%c", &a); //不要使用字符串，效果不好。
    	while (a != '#'){
        
    		insert(&STA, a);
    		scanf("%c", &a);
    	}
    	while (STA.top != STA.base){
        
    		a = pop(&STA);
    		printf("%c", a);
    	}
    	printf("\n");
    	return 0;
    }

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[20190723170158884.jpg_pic_center]: /images/20211126/325ad947cf9a4da78fbc3af35d44372a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70]: /images/20211126/fcfc2846c23145ddbada0d33815509ce.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm