C语言数据结构004——堆栈

朱雀 2023-10-06 18:00 156阅读 0赞

## 一、堆栈的基本概念 ##

(1)定义:限定只能在固定一端进行插入和删除操作的线性表。  
(2)允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。  
标示栈顶当前位置的变量称为栈顶指示器（栈顶指针）  
堆栈的插入元素操作称为进栈或入栈，删除元素操作称为出栈或退栈  
特点：后进先出。  
作用：可以完成从输入数据序列到某些输出数据序列的转换。

## 二、顺序堆栈 ##

### 2.1、顺序堆栈存储结构 ###

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，其结构如图所示：  
![在这里插入图片描述][20210622114941764.png]

typedef struct
    {
        	
    	DataType stack[MaxStackSize];			
    	int top;
    } SeqStack;

### 2.2、顺序堆栈的操作实现： ###

//结点结构体定义如下：
    typedef struct
    {
        	
    	DataType stack[MaxStackSize];			
    	int top;
    } SeqStack;
    
    //（1）初始化    StackInitiate(S)
    void StackInitiate(SeqStack *S)	
    {
        
    	S->top = 0;		
    }
    //（2）非空否   StackNotEmpty(S)
    int StackNotEmpty(SeqStack S)
    {
        
    	if(S.top <= 0)	return 0;
    	else return 1;
    }
    //（3）入栈  StackPush(S, x)
    //把数据元素值x存入顺序堆栈S中，入栈成功则返回1，否则返回0
    int StackPush(SeqStack *S, DataType x)
    {
        
    	if(S->top >= MaxStackSize)
    	{
        	
    		printf("堆栈已满无法插入! \n");
    		return 0;
    	}
    	else
    	{
        	
    		S->stack[S->top] = x;
    		S->top ++;
    		return 1;
    	}
    }
    
    //（4）出栈   StackPop(S, d)
    int StackPop(SeqStack *S, DataType *d)
    {
        
    	if(S->top <= 0)
    	{
        	
    		printf("堆栈已空无数据元素出栈! \n");
    		return 0;
    	}
    	else
    	{
        	
    		S->top --;
    		*d = S->stack[S->top];
    		return 1;
    	}
    }
    
    //（5）取栈顶数据元素 StackTop(SeqStack S, DataType *d)
    int StackTop(SeqStack S, DataType *d)
    {
        
    	if(S.top <= 0)
    	{
        	
    		printf("堆栈已空! \n");
    		return 0;
    	}
    	else
    	{
        	
    		*d = S.stack[S.top-1 ];
    		return 1;
    	}
    }

## 三、链式堆栈 ##

(1)链式堆栈：链式存储结构的堆栈。  
(2)链式栈的存储结构：它是以头指针为栈顶，在头指针处插入或删除，带头结点的单链式堆栈结构：  
![在这里插入图片描述][20210622115548961.png]

### 3.1、链式堆栈的操作实现： ###

//结点结构体定义如下：
    typedef struct snode
    {
        
    	DataType data;
    	struct snode *next;
    } LSNode;
    
    //（1）初始化  StackInitiate(head)
    void StackInitiate(LSNode **head)
    {
        
    	*head = (LSNode *)malloc(sizeof(LSNode)) ;  
    	(*head)->next = NULL;
    }
    //（2）非空否 StackNotEmpty(head)
    int StackNotEmpty(LSNode *head)
    {
        
    	if(head->next == NULL) return 0;
    	else return 1;
    }
    
    //（3）入栈   StackPush(head, x)
    //把数据元素x插入链式堆栈head的栈顶作为新的栈顶
    int StackPush(LSNode *head, DataType x) 
    {
        
    	LSNode *p;
     	p = (LSNode *)malloc(sizeof(LSNode)) ;  
    	p->data = x;
    	p->next = head->next;
    	head->next = p; 
    	return 1;
    }
    
    //（4）出栈  StackPop(head, *d)
    //出栈并把栈顶元素由参数d带回，出栈成功返回1，否则返回0
    int StackPop(LSNode *head, DataType *d)
    {
        	
    	LSNode *p = head->next;
    	if(p == NULL) 
    	{
        	printf("堆栈已空出错！");
    		return 0;
    	}
     	head->next = p->next;
    	*d = p->data; 	
    	free(p); 
    	return 1;
    }
    
    //（5）取栈顶数据元素   StackTop(head, d)
    int StackTop(LSNode *head, DataType *d)
    {
        
    	LSNode *p = head->next;
    	if(p == NULL)    // head- >next == NULL
    	{
        
    		printf("堆栈已空出错！");
    		return 0;
    	}
    	*d = p->data;  	//*d= head->next->data;
    	return 1;
    }
    
    //（6）撤消动态申请空间  Destroy(*head)
    void Destroy(LSNode *head)
    {
        
    	LSNode *p, *p1;
     
    	p = head;
    	while(p != NULL)
    	{
        
    		p1 = p;
    		p = p->next;
    		free(p1);
    	}
    }

> 说明：  
> （1）链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。  
> （2）一般不会出现栈满情况；除非没有空间导致malloc分配失败。  
> （3）堆栈所有操作的时间复杂度均为O(1)。

## 四、堆栈的应用 ##

1、数制转换

2、括号匹配的检验

3、迷宫求解

4、表达式求值  
对于表达式A x B + (C - D / E) x F，有一下结论：

> 前缀式：+x AB x- C / DEF  
> 中缀式：A x B + (C - D / E) x F  
> 后缀式：AB x CDE /- F x+

5、实现递归

[20210622114941764.png]: https://img-blog.csdnimg.cn/20210622114941764.png
[20210622115548961.png]: https://img-blog.csdnimg.cn/20210622115548961.png