线性表—栈的实现

目录

栈的概念及结构

栈的实现

创建栈

栈的初始化

入栈

出栈

取出栈顶数据

判断栈是否为空

有效数据个数

栈的销毁

全代码

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/

示例

解题思路

     这题根据栈的后进先出和边入边出的特性可以解决。

     创建一个栈，只让左括号入栈，让右括号与栈里的数据匹配。如果匹配成功让左括号出栈，继续该操作直至字符串遍历完。如果匹配不成功则直接退出。

有几个要注意的点

1. 字符串只有右括号
2. 字符串只有左括号或只剩左或右括号
3. 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;
}

---