【数据结构——栈篇】

刺骨的言语ヽ痛彻心扉 2022-12-13 04:47 63阅读 0赞

# 【数据结构——栈篇】 #

### 目录 ###

*  【数据结构——栈篇】
 *  一、栈的顺序存储——顺序栈
 *   *   *  1、顺序栈的表示和实现
         *  2、顺序栈的定义
         *  2、顺序栈初始化
         *  3、顺序栈入栈
         *  4、顺序栈出栈
         *  5、取顺序栈栈顶元素
         *  6、输出栈内容
 *  二、栈的链式存储——链栈
 *   *   *  1、链栈的存储结构
         *  2、栈链的初始化
         *  3、链栈的入栈
         *  4、链栈的出栈
         *  5、取链栈栈顶元素
         *  6、输出链栈的内容

# 一、栈的顺序存储——顺序栈 #

### 1、顺序栈的表示和实现 ###

**因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需要一个变量top来指示当前栈顶的位置，通常称top为栈顶指针。**

### 2、顺序栈的定义 ###

#define MAXSIZE 100
    typedef struct
    {
        
    	SElemType* base;//栈底指针
    	SElemType* top;//栈顶指针
    	int stacksize;//可使用的最大容量
    }SqStack;
    
    SqStack S;//定义顺序栈
    S.stacksize = s;//栈的大小
    S.base == S.top;//空栈
    S.top - S.base == stacksize;//满栈

### 2、顺序栈初始化 ###

> 算法思想：  
> 1、分配空间并检查空间是否分配成功，否则返回错误  
> 2、栈顶指针top初始化为栈底指针base  
> 3、stacksize = 栈的最大容量

Status IniStack(SqStack& S)
    {
        
    	S.base = new SElemType[MAXSIZE];//分配空间
    	if (!S.base) exit(OVERFLOW);//分配失败，返回错误
    	S.top = S.base;//栈顶指针初始化为栈底指针
    	S.stacksize = MAXSIZE;//初始化栈的最大容量
    	return OK;
    }

### 3、顺序栈入栈 ###

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

> 算法思想  
> 1、判断是否栈满，若满则出错  
> 2、新元素e压入栈顶  
> 3、栈顶指针+1

Status Push(SqStack& S, SElemType e)
    {
        
    	if (S.top - S.base == S.stacksize)
    		return ERROR;//栈满
    	*S.top = e;//新元素e压入栈顶
    	S.top++;//栈顶指针+1
    	return OK;
    }

### 4、顺序栈出栈 ###

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

> 算法思想  
> 1、判断是否栈空，若空则出错  
> 2、栈顶指针-1  
> 3、获取栈顶元素e

Status Pop(SqStack& S, SElemType& e)
    {
        
    	if (S.top == S.base)
    		return ERROR;//栈空报错
    	--S.top;//栈顶指针-1
    	e = *S.top;//获取栈顶元素e
    	return OK;
    }

### 5、取顺序栈栈顶元素 ###

SElemType GetTop(SqStack S)
    {
        
    	if (S.top != S.base)//栈非空
    		return *(S.top - 1);//返回栈顶元素的值
    	                        //栈顶指针不变
    }

### 6、输出栈内容 ###

void OutPut_SqS(SqStack S)
    {
        
    	SElemType* p;
    	if (S.top == S.base)
    		printf("空栈！\n");
    	else
    		for (p = S.top - 1;p >= S.base;p--)
    			printf("%d\n", *p);
    }

# 二、栈的链式存储——链栈 #

> 1、链式存储方式表示的栈称链栈  
> 2、运算受限的单链表  
> 3、链表的头指针就是栈顶  
> 4、不需要头结点  
> 5、插入与删除仅在栈顶执行

### 1、链栈的存储结构 ###

![在这里插入图片描述][2020101017055660.png_pic_center]

typedef struct StackNode
    {
        
    	SElemType data;
    	struct StackNode* next;
    }StackNode,*LinkStack;
    
    LinkStack S;

### 2、栈链的初始化 ###

![在这里插入图片描述][20201010170608223.png_pic_center]

> 算法思想：  
> 1、不需要头结点  
> 2、链栈的头指针就是栈顶  
> 3、栈链无栈满问题，空间可扩充  
> 4、空栈相当于头指针指向NULL

Status IniStack(LinkStack& S)
    {
        //构造一个空栈，栈顶指针置空
    	S = NULL;
    	return OK;
    }

### 3、链栈的入栈 ###

![在这里插入图片描述][20201010172144825.png_pic_center]

> 算法思想：  
> 1、为入栈元素e分配空间，用指针p指向  
> 2、将新结点指针域置为e  
> 3、将新结点插入栈顶  
> 4、修改栈顶指针为p

Status Push(LinkStack& S, SElemType e)
    {
        
    	p = new StackNode;//生成新结点
    	p->data = e;//将新结点数据域置为e
    	p->next = S;//将新结点插入栈顶
    	S = p;//修改栈顶指针为p
    	return OK;
    }

### 4、链栈的出栈 ###

![在这里插入图片描述][20201010172240764.png_pic_center]

> 算法思想：  
> 1、判断是否是空栈，若是空栈，返回错误  
> 2、将栈顶元素赋值给e  
> 3、临时保存栈顶元素的空间，以备释放  
> 4、修改栈顶指针，指向新的栈顶元素  
> 5、释放原栈顶元素的空间

Status Pop(LinkStack& S, SElemType& e)
    {
        
    	if (S == NULL)
    		return ERROR;//栈空
    	e = S->data;//将栈顶元素存储到e中
    	p = S;//用p临时保存栈顶元素的空间，以备释放
    	S = S->next;//修改栈顶指针
    	delete p;//释放原栈顶元素的空间
    	return OK;
    }

### 5、取链栈栈顶元素 ###

![在这里插入图片描述][20201010173538899.png_pic_center]

SElemType GetTop(LinkStack S)
    {
        
    	if (S != NULL)
    		return S->data;
    }

### 6、输出链栈的内容 ###

![在这里插入图片描述][20201010174410254.png_pic_center]

void OutPut(LinkStack S)
    {
        
    	p = S;
    	if (!p)
    		printf("空栈！");
    	else
    		while (p)
    		{
        
    			printf("%d", p->data);
    			p = p->next;
    		}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e3f281c597e54254980ddfb5b4d66164.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/20109d62f77042f2921f59129dd61eda.png
[2020101017055660.png_pic_center]: /images/20221123/aa367fee0f0e46ea99c637e6fb4e3487.png
[20201010170608223.png_pic_center]: /images/20221123/4e21323aab3b4f91964c6e4e8ea32c2a.png
[20201010172144825.png_pic_center]: /images/20221123/2772fef81d174df7b5bf6fbe5f66001c.png
[20201010172240764.png_pic_center]: /images/20221123/4d7b7d4d19904da9986dd4a644a22142.png
[20201010173538899.png_pic_center]: /images/20221123/fa21ef892f4a45d58fc7b153a7875006.png
[20201010174410254.png_pic_center]: /images/20221123/d58b95d489244c4ab9fd3f3ded251c7c.png