栈和队列(一) 栈操作详解

川长思鸟来 2024-03-23 18:26 40阅读 0赞

#### 文章目录 ####

*  一、物理结构和逻辑结构
 *  二、栈
 *   *  1、什么是栈
     *  2、栈中一些基本操作的实现
     *   *  Stack.h
         *  Stack.c
         *   *  栈的初始化
             *  栈的销毁
             *  入栈
             *  出栈
             *  获得栈顶元素
             *  获得栈的元素数
             *  判断栈空
 *  三、利用栈解决问题

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

## 一、物理结构和逻辑结构 ##

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

栈和队列都属于逻辑结构，它们既可以用数组实现也可以用链表实现。

## 二、栈 ##

### 1、什么是栈 ###

> 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出（Last In First Out，简称LIFO）的原则。  
> 进栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。  
> 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

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

### 2、栈中一些基本操作的实现 ###

利用数组来实现栈的基本操作

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

**代码结构设计：**

*  Stack.h: 存放链表结构及需要用到的头文件，函数声明等
 *  Stack.c: 各种操作函数的具体实现

#### Stack.h ####

#pragma once
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include<stdbool.h>
    //方便修改类型
    typedef int STDataType;
    //栈
    typedef struct Stack
    {
        
    	STDataType* a;//实现栈的数组
    	int top;//栈顶
    	int capacity;//栈容量
    }ST;
    
    //栈的初始化
    void STInit(ST* ps);
    //栈的销毁
    void STDestroy(ST* ps);
    //入栈
    void STPush(ST* ps, STDataType x);
    //出栈
    void STPop(ST* ps);
    //获得栈顶元素
    STDataType STTop(ST* ps);
    //获得栈的元素数
    int STSize(ST* ps);
    //判断栈空
    bool STEmpty(ST* ps);

#### Stack.c ####

#include "Stack.h"

##### 栈的初始化 #####

void STInit(ST* ps)
    {
        
    	assert(ps);
    
    	ps->a = NULL;
    	//栈顶元素的下一个
    	ps->top = 0;
    	ps->capacity = 0;
    }

##### 栈的销毁 #####

void STDestroy(ST* ps)
    {
        
    	assert(ps);
    
    	free(ps->a);
    	ps->a = NULL;
    	ps->top = 0;
    	ps->capacity = 0;
    }

##### 入栈 #####

void STPush(ST* ps, STDataType x)
    {
        
    	assert(ps);
    	//空间不足，扩容
    	if (ps->capacity == ps->top)
    	{
        
    		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newCapacity);
    		if (tmp == NULL)
    		{
        
    			perror("realloc fail");
    			exit(-1);
    		}
    		ps->a = tmp;
    		ps->capacity = newCapacity;
    	}
    	//更新入栈后内容
    	ps->a[ps->top] = x;
    	ps->top++;
    }

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

##### 出栈 #####

void STPop(ST* ps)
    {
        
    	assert(ps);
    	assert(ps->top > 0);
    	ps->top--;
    }

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

##### 获得栈顶元素 #####

top初始化时是0，是栈顶元素的下一个位置，所以栈顶元素下标是top-1

STDataType STTop(ST* ps)
    {
        
    	assert(ps);
    	assert(ps->top > 0);
    	return ps->a[ps->top - 1];
    }

##### 获得栈的元素数 #####

top从0开始，栈内多一个元素它就加1，所以top与元素树大小一致

int STSize(ST* ps)
    {
        
    	assert(ps);
    	
    	return ps->top;
    }

##### 判断栈空 #####

top等于0时栈空

bool STEmpty(ST* ps)
    {
        
    	return ps->top ==0 ;
    }

## 三、利用栈解决问题 ##

本题来自LeetCode：[有效的括号][Link 1]

**有效的括号**

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

**示例1：**

> 输入：s=“( )”  
> 输出：true

**示例2：**

> 输入：s=“( )\[ \]\{ \}”  
> 输出：true

**示例3：**

> 输入：s=“( \]”  
> 输出：false

*  1 <= s.length <= 104
 *  s 仅由括号 ‘( )\[ \]\{ \}’ 组成

**题目分析：**

1.  对于这个题我们需要将字符串内括号的左一半与右一半进行匹配，有"( \{ \[ \] \})“、”( ) \[ \] \{ \}“等多种情况都是符合情况的，也有像”( \{ ) \}"这种不符合情况的都需要考虑。
2.  如果是左括号则入栈
3.  如果是右括号，取出栈顶元素与之匹配
4.  如果右边括号匹配时栈内已经空了则数量不匹配
5.  匹配结束后栈内不为空则数量不匹配

**代码：**

这里我们用上面实现的栈操作来完成

bool isValid(char * s){
        
        ST st;
        STInit(&st);
        char topval;
    
        while(*s)
        {
        
            if(*s=='('||*s=='{'||*s=='[')
            {
        
                STPush(&st,*s);
            }
            else
            {
        
                //如果栈内为空说明数量不匹配
                if(STEmpty(&st))
                {
        
                    STDestroy(&st);
                    return false;
                }
    
                //取出栈顶元素，然后栈顶元素出栈
                topval=STTop(&st);
    			STPop(&st);
    			//匹配不成功的情况
                if((*s==')'&&topval!='(')
                || (*s=='}'&&topval!='{')
                || (*s==']'&&topval!='['))
                {
        
                    STDestroy(&st);
                    return false;
                }
            }
            s++;
        }
    
        //匹配完后如果栈内不为空说明数量不匹配
    	bool ret=STEmpty(&st);
    	STDestroy(&st);
        return ret;
    }

[764c1512b8c84cca96fb11675e2d47be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f61ee94daf2e4d42b723ccfe98396fea.png
[5179b733f020449aa63cf7e05976d170.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7eb010db05d046d4aedffd8cdf1d256c.png
[3dfb6b11b5324539b58998b95a58d2ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/59a97e78e6d54d438833676d086e622a.png
[571d4bd033244ca4bcd48a96790c462c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e281e74fe17b4c29af67827f29b79bab.png
[7d0387ebf761427da96bd87eed74b132.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e1d5d4aeb57748a493dc240fc54db43c.png
[5a399c1507da42c4b39bbc643e2d3002.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/aeb6b925315e4c23b0df2a662e555658.png
[Link 1]: https://leetcode.cn/problems/valid-parentheses/
[4030d7ac13894ba3a153bfd0174d4907.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2a279fda1fb64ea3b207cd11a9aedde5.png