线性表—栈的实现
目录
栈的概念及结构
栈的实现
创建栈
栈的初始化
入栈
出栈
取出栈顶数据
判断栈是否为空
有效数据个数
栈的销毁
全代码
stack.h
stack.c
应用
题目
示例
解题思路
代码实现
栈的概念及结构
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。你也可以一边入一边出。
栈顶和栈底并不是固定的，这是人为决定的。
栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
以下的内容如果你对顺序表的实现熟悉的话就很简单。
创建栈
栈的创建需要有指向动态数组指针，栈顶数据下标和容量。
typedef int STDataType;typedef struct Stack
{STDataType* arr;//指向动态数组指针int top;//栈顶数据下标int capacity;//容量
}ST;
栈的初始化
将arr置为空指针，top置为-1，capacity置为0。
//初始化
void STInit(ST* pst)
{assert(pst);pst->arr = NULL;pst->top = -1;pst->capacity = 0;
}这里的top为什么要是-1呢？
一般来说top应该也是0，这里是-1是为了确保top是栈顶数据的下标。当然了你要是想写0也是可以的。
入栈
入栈又称压栈，进栈。
首先要判断容量是否够用，如果不够用的话就扩容。然后再把数据塞入即可。
//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top + 1 == pst->capacity){pst->capacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* p = (STDataType*)realloc(pst->arr, sizeof(STDataType) * pst->capacity);if (p == NULL){perror("realloc");return;}pst->arr = p;}pst->arr[++pst->top] = x;
}注意：这里要前置++，如果后置就会造成非法访问。如果top是0，就要后置了。
出栈
这里要另外判断一下栈是否为空。然后只要让top--即可。
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > -1);pst->top--;
}取出栈顶数据
这里也要判断一下栈是否为空。然后返回下标top对应的数据即可。
//取出出栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > -1);return pst->arr[pst->top];
}判断栈是否为空
直接返回pst->top==-1即可。
//判断栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == -1;
}该函数类型要是布尔类型。
如果top=-1则返回true，否则返回false。
有效数据个数
直接返回top+1即可。
//有效数据个数
int STSize(ST* pst)
{assert(pst);return pst->top + 1;
}栈的销毁
用free销毁arr，并将它置为空指针。其它的置为初始化值即可。
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst->arr);pst->arr = NULL;pst->top = -1;pst->capacity = 0;
}全代码
stack.h
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int STDataType;typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;//初始化
void STInit(ST* pst);//销毁
void STDestroy(ST* pst);//入栈
void STPush(ST* pst, STDataType x);//出栈
void STPop(ST* pst);//取出出栈顶数据
STDataType STTop(ST* pst);//判空
bool STEmpty(ST* pst);//获取数据个数
int STSize(ST* pst);stack.c
#include "stack.h"//初始化
void STInit(ST* pst)
{assert(pst);pst->arr = NULL;pst->top = -1;pst->capacity = 0;
}//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top + 1 == pst->capacity){pst->capacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* p = (STDataType*)realloc(pst->arr, sizeof(STDataType) * pst->capacity);if (p == NULL){perror("realloc");return;}pst->arr = p;}pst->arr[++pst->top] = x;
}//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > -1);pst->top--;
}//取出栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > -1);return pst->arr[pst->top];
}//判断栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == -1;
}//有效数据个数
int STSize(ST* pst)
{assert(pst);return pst->top + 1;
}//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst->arr);pst->arr = NULL;pst->top = -1;pst->capacity = 0;
}应用
题目
该题链接： https://leetcode.cn/problems/valid-parentheses/description/
示例
解题思路
这题根据栈的后进先出和边入边出的特性可以解决。
创建一个栈，只让左括号入栈，让右括号与栈里的数据匹配。如果匹配成功让左括号出栈，继续该操作直至字符串遍历完。如果匹配不成功则直接退出。
有几个要注意的点
- 字符串只有右括号
- 字符串只有左括号或只剩左或右括号
- arr是int的类型，要把它改成char类型
代码实现
bool isValid(char* s)
{ST st;STInit(&st);while(*s){if(*s == '(' || *s == '[' || *s == '{'){STPush(&st, *s);}else{if(st.top == -1)//字符串只有右括号{STDestroy(&st);return false;}STDataType top = STTop(&st);if(*s == ')' && top != '(' || *s == ']' && top != '[' || *s == '}' && top != '{'){STDestroy(&st);return false;}STPop(&st);}s++;}bool ret = STEmpty(&st);//字符串只有左括号或只剩左或右括号STDestroy(&st);return ret;
}