Data Structure--栈的接口实现(详细)

刺骨的言语ヽ痛彻心扉 2022-10-30 14:30 113阅读 0赞

## 栈 ##

栈就是简单地用容器的方式来理解这一种方式,主要就是**后进先出**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

### 栈的基本结构 ###

typedef int STDataType;
    
    typedef struct stack{ 
    
    	STDataType* _data;	//存放数据
    	int _size;			//存放数量
    	int _capacity;		//最大容量
    }stack;

### 接口声明 ###

栈这里的部分接口就是我们之前讲过的,我挑重点的进行讲解,其他的直接贴代码

//1.初始化
    void stackInit(stack* st);
    //2.检查容量
    void checkCapacity(stack* st);
    //3.入栈
    void stackPush(stack* st, STDataType val);
    //4.出栈
    void stackPop(stack* st);
    //5.获取栈顶元素
    STDataType stackTop(stack* st);
    //6.判空
    int stackEmpty(stack* st);
    //7.栈大小
    int stackSize(stack* st);

### 接口实现 ###

##### 1.初始化 #####

void stackInit(stack* st){ 
    	
    	if (st == NULL)		//判空
    		return;
    
    	st->_data = NULL;	//将空间变为空
    	st->_size = st->_capacity = 0;	//大小变为0
    
    }

##### 2.检查容量 #####

void checkCapacity(stack* st){ 
    
    	if (st->_size == st->_capacity){ 	//在存储的元素和最大内存量相等的时候就要开辟空间
    		//判断是开辟一个还是直接扩大一倍
    		int newCapacity = st->_capacity == 0 ? 1 : 2 * st->_capacity;
    		//直接用realloc直接初始化为0
    		st->_data = (STDataType*)realloc(st->_data, sizeof(STDataType)*newCapacity);
    		//将原来的指向为新开辟的空间
    		st->_capacity = newCapacity;
    	
    	}
    }

##### 3.入栈 #####

void stackPush(stack* st, STDataType val){ 
    
    	if (st == NULL)		//判空
    		return;
    		
    	checkCapacity(st);	//检查
    
    	st->_data[st->_size++] = val;	//size++直接赋值就可以,简单
    
    }

##### 4.出栈 #####

void stackPop(stack* st){ 
    
    	if (st == NULL)		//判空
    		return;
    
    	if (st->_size > 0){ 	
    		
    		st->_size--;	//直接让size-1就可以删掉顶部的一个元素
    	}
    }

##### 5.获取栈顶元素 #####

STDataType stackTop(stack* st){ 
    	
    	return st->_data[st->_size - 1];	//直接输出size-1在data里面对应的数据即可
    }

##### 6.判空 #####

int stackEmpty(stack* st){ 
    	
    	if (st == NULL || st->_size == 0)
    		return 1;		//为空返回1
    	else
    		return 0;
    }

##### 7.栈大小 #####

int stackSize(stack* st){ 
    	
    	if (st == NULL)
    		return 0;
    		//判空没问题直接输出size即可
    	return st->_size;
    }

对于栈这里的接口比较简单,主要就是对水瓶式的样子的理解,主要理解下后进先出,其他的都比较简单,一起加油!!!多敲代码 !!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/be0ed1de3a12422ca3a9c572872f2787.png