【数据结构---栈】一篇文章搞懂栈的设计及相关操作

ゝ一纸荒年。 2023-03-03 11:17 30阅读 0赞

### 文章目录 ###

*  栈
 *   *  顺序栈
     *   *  一、概念
         *  二、图解
         *  三、参考源码
     *  链栈
     *   *  一、概念
         *  二、图解
         *  三、参考源码

# 栈 #

> 栈(stack)是限定仅在**表尾**进行插入和删除操作的线性表。  
> 表尾被称为**栈顶（top）**，表头被称为**栈底（bottom）**  
> 栈有两种存储方式：①**顺序栈** ②链栈

栈示意图  
![在这里插入图片描述][20200731100503148.png]

> 进栈顺序与出栈顺序相反，后进先出（LIFO）

## 顺序栈 ##

### 一、概念 ###

> 顺序栈的存储空间是动态分配出来的一块空间，这块空间使用数组来表示

### 二、图解 ###

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

### 三、参考源码 ###

> 头文件

#include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>

> 栈结构定义

/*************************************************************/
    //定义常量
    #define DEFAULT_STACK_CAPACITY 8 //初始化容量
    #define DEFAULT_STACK_GROW_MULTIPLE 2 //扩容倍数
    typedef int ET;
    /*************************************************************/
    //顺序栈
    typedef struct SeqStack
    { 
    	ET* base;
    	size_t capacity;	//当前最大容量
    	int top;			//当前栈顶位置
    }SeqStack;

> 方法声明

void SeqStackInitial(SeqStack* p, size_t cap);	//初始化顺序栈结构
    bool IsEmpty(SeqStack* p);						//判断顺序栈是否为空
    bool IsFull(SeqStack* p);						//判断顺序栈是否为满
    void SeqStackGrow(SeqStack* p);					//栈满之后扩容栈结构
    void SeqStackAddTop(SeqStack* p, ET val);		//入栈
    void SeqStackShowData(SeqStack* p);				//展示栈中的数据
    void SeqStackDeleteTop(SeqStack* p);			//出栈
    ET SeqStackGetTop(SeqStack* p);					//获取栈顶元素
    int SeqStackGetSize(SeqStack* p);				//获取顺序栈当前大小
    int SeqStackGetCapacity(SeqStack* p);			//获取顺序栈当前最大容量大小
    void SeqStackDestroy(SeqStack* p);				//摧毁顺序栈结构
    void SeqStackClear(SeqStack* p);				//清空栈中的数据

> 方法实现

void SeqStackInitial(SeqStack* p, size_t cap){ 
    	assert(p != NULL);
    	p->capacity = cap > DEFAULT_STACK_CAPACITY ? cap : DEFAULT_STACK_CAPACITY;
    	p->top = 0;
    	p->base = (ET*)malloc(sizeof(ET)* p->capacity);
    }
    bool IsEmpty(SeqStack* p){ 
    	assert(p != NULL);
    	return p->top == 0;
    }
    bool IsFull(SeqStack* p){ 
    	assert(p != NULL);
    	return p->top == p->capacity;
    }
    void SeqStackGrow(SeqStack* p){ 
    	assert(p != NULL);
    	p->capacity *= DEFAULT_STACK_GROW_MULTIPLE;
    	ET* new_base = (ET*)realloc(p->base, sizeof(ET)* p->capacity);
    	p->base = new_base;
    }
    void SeqStackAddTop(SeqStack* p, ET val){ 
    	assert(p != NULL);
    	if (IsFull(p)){ 
    		SeqStackGrow(p);
    	}
    	p->base[p->top++] = val;
    }
    void SeqStackShowData(SeqStack* p){ 
    	assert(p != NULL);
    	if (IsEmpty(p)){ 
    		printf("空表！\n");
    		return;
    	}
    	int index = p->top - 1;
    	while (index >= 0){ 
    		printf("%2d|%2d|\n", index, p->base[index]);
    		index--;
    	}
    	printf(" |__|\n");
    }
    void SeqStackDeleteTop(SeqStack* p){ 
    	assert(p != NULL);
    	if (IsEmpty(p)){ 
    		printf("空表！\n");
    		return;
    	}
    	p->top--;
    }
    ET SeqStackGetTop(SeqStack* p){ 
    	assert(p != NULL);
    	if (IsEmpty(p)){ 
    		printf("空表！\n");
    		return;
    	}
    	return 	p->base[p->top - 1];
    }
    int SeqStackGetSize(SeqStack* p){ 
    	assert(p != NULL);
    	if (IsEmpty(p)){ 
    		printf("空表！\n");
    		return;
    	}
    	return p->top;
    }
    int SeqStackGetCapacity(SeqStack* p){ 
    	assert(p != NULL);
    	if (IsEmpty(p)){ 
    		printf("空表！\n");
    		return;
    	}
    	return p->capacity;
    }
    void SeqStackDestroy(SeqStack* p){ 
    	assert(p != NULL);
    	p->capacity = DEFAULT_STACK_CAPACITY;
    	p->top = 0;
    	free(p->base);
    	p->base = NULL;
    }
    void SeqStackClear(SeqStack* p){ 
    	p->capacity = DEFAULT_STACK_CAPACITY;
    	p->top = 0;
    }

## 链栈 ##

### 一、概念 ###

> 链栈的存储空间是动态分配的结点，这个结点由**数据域**和**指针域**组成，并且只能在栈顶处增加或删除结点

### 二、图解 ###

![在这里插入图片描述][20200731105245996.png]

### 三、参考源码 ###

> 头文件

#include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>

> 定义链栈结构

/*************************************************************/
    //定义常量
    typedef int ET;
    /*************************************************************/
    //链栈
    typedef struct StackNode{ 
    	ET data;
    	struct StackNode* next;
    }StackNode;
    typedef StackNode* LinkStack;

> 方法声明

void LinkedStackInitial(LinkStack *pst);			//初始化链栈结构
    StackNode* GetNode(ET val);							//创建并返回一个栈结点
    void LinkedStackAddTop(LinkStack *pst, ET val);		//入栈
    void LinkedStackDeletePop(LinkStack *pst);			//出栈
    ET LinkedStackGetTop(LinkStack *pst);				//获取栈顶结点 
    void LinkedStackShowData(LinkStack *pst);			//展示链栈中数据
    int LinkedStackGetLength(LinkStack *pst);			//获取栈的大小
    void LinkedStackDestroy(LinkStack *pst);			//摧毁栈结构

> 方法实现

void LinkedStackInitial(LinkStack *pst){ 
    	assert(pst != NULL);
    	*pst = NULL;
    }
    StackNode* GetNode(ET val){ 	//申请结点 
    	StackNode* s = (StackNode*)malloc(sizeof(StackNode));
    	assert(s != NULL);
    	s->data = val;
    	s->next = NULL;
    	return s;
    }
    void LinkedStackAddTop(LinkStack *pst, ET val){ 
    	assert(pst != NULL);
    	StackNode* s = GetNode(val);
    	if (*pst == NULL){ 	//空栈 
    		*pst = s;
    	}
    	else{ 	//栈非空 
    		StackNode* temp = *pst;
    		while (temp->next != NULL){ 
    			temp = temp->next;
    		}
    		temp->next = s;
    	}
    }
    void LinkedStackDeletePop(LinkStack *pst){ 
    	assert(pst != NULL);
    	if (*pst == NULL){ 	//空栈 
    		printf("空栈！\n");
    		return;
    	}
    	else{ 	//栈非空 
    		StackNode* temp = *pst;
    		if (temp->next == NULL){ 		//栈只有一个元素 
    			free(temp);
    			*pst = NULL;
    		}
    		else{ 						//栈中有多个元素 
    			while (temp->next->next != NULL){ 
    				temp = temp->next;
    			}
    			StackNode* p = temp->next;
    			free(p);
    			temp->next = NULL;
    		}
    	}
    }
    ET LinkedStackGetTop(LinkStack *pst){ 
    	assert(pst != NULL);
    	if (*pst == NULL){ 	//空栈 
    		printf("空栈！\n");
    		return -1;
    	}
    	else{ 	//栈非空 
    		StackNode* temp = *pst;
    		if (temp->next == NULL){ 		//栈只有一个元素 
    			return temp->data;
    		}
    		else{ 						//栈中有多个元素 
    			while (temp->next->next != NULL){ 
    				temp = temp->next;
    			}
    			StackNode* p = temp->next;
    			return p->data;
    		}
    	}
    }
    void LinkedStackShowData(LinkStack *pst){ 
    	assert(pst != NULL);
    	if (*pst == NULL){ 		//空栈 
    		printf("空栈！\n");
    	}
    	else{ 					//栈非空 
    		StackNode* temp = *pst;
    		printf(" |==|\n");
    		int i = 0;
    		while (temp->next != NULL){ 
    			printf("%2d|%2d|\n", i, temp->data);
    			printf(" |↓|\n");
    			temp = temp->next;
    			i++;
    		}
    		printf("%2d|%2d|\n", i, temp->data);
    	}
    }
    int LinkedStackGetLength(LinkStack *pst){ 
    	assert(pst != NULL);
    	int len = 1;
    	if (*pst == NULL){ 
    		len = 0;
    	}
    	else{ 
    		StackNode* p = *pst;
    		while (p->next != NULL){ 
    			p = p->next;
    			len++;
    		}
    	}
    	return len;
    }
    void LinkedStackDestroy(LinkStack *pst){ 
    	assert(pst != NULL);
    	if (*pst == NULL){ 
    		return;
    	}
    	else{ 
    		StackNode* p = *pst;
    		StackNode* q = *pst;
    		while (q != NULL){ 
    			q = q->next;
    			free(p);
    			p = q;
    		}
    	}
    	*pst = NULL;
    }

[20200731100503148.png]: /images/20230208/bbfbc367064d439ea193a9bf4e25959f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: /images/20230208/bba34eb9a8084b3394c5a1b820ed79a6.png
[20200731105245996.png]: /images/20230208/a10f9e758548424986e701f860bebfc8.png