一、物理结构和逻辑结构
栈和队列都属于逻辑结构，它们既可以用数组实现也可以用链表实现。
二、栈
1、什么是栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出（Last In First Out，简称LIFO）的原则。
进栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2、栈中一些基本操作的实现
利用数组来实现栈的基本操作
代码结构设计：
- 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++; }
出栈
void STPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; }
获得栈顶元素
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：有效的括号
有效的括号
示例1：
输入：s=“( )”
输出：true
示例2：
输入：s=“( )[ ]{ }”
输出：true
示例3：
输入：s=“( ]”
输出：false
- 1 <= s.length <= 104
- s 仅由括号 ‘( )[ ]{ }’ 组成
题目分析：
- 对于这个题我们需要将字符串内括号的左一半与右一半进行匹配，有"( { [ ] })“、”( ) [ ] { }“等多种情况都是符合情况的，也有像”( { ) }"这种不符合情况的都需要考虑。
- 如果是左括号则入栈
- 如果是右括号，取出栈顶元素与之匹配
- 如果右边括号匹配时栈内已经空了则数量不匹配
- 匹配结束后栈内不为空则数量不匹配
代码：
这里我们用上面实现的栈操作来完成
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; }
