栈
1.栈的定义
1.1 结构定义
在此构建的是顺序栈，也就是说开辟一块连续的内存空间当作栈，栈只有一个入口，先进先出是它的规则
- 一个完整的栈应该包括栈头，存放的元素和栈能够容纳元素的个数
- 因为存放的元素是一块连续的内存空间，所以将其开辟成数组即可
- 在此栈头存放的不是指向元素的指针，而是开辟连续内存空间的数组的索引
typedef struct Stack{
int *data;//数据类型是可以进行该变的，因为申请空间是用的是new所以返回的是指针 ,实际上是数组的头
int length;
int top; //为什么指向栈头的是int类型 ？？？ 因为这个是顺序栈，在这里是用索引来代表栈里的元素的
}Stack;
1.2 初始化操作
初始化简单来说就是为其开辟自己的空间,并对其内部的变量进行初始化操作
//2->初始化
Stack *init_stack(int n){
Stack *s = new Stack;
s->data = new int[n]; //开辟n个int类型空间的数组，并返回头部指针
s->length = n;
s->top = -1;//头指针指的是最上面元素,起始的元素为0所以是-1,当有1个元素时，指向的是s->data[0]
return s;
}
1.3 栈的清理
void clear(Stack *s){
if(s == NULL) return;
delete s->data; //先清理栈内存放的元素，data是数组的头部，只需传入头部其他的就被删除了
delete s;
}
1.4 判空操作
用于判断栈是否是空的，即只需判断top是否是-1
//4->判空操作
bool empty(Stack *s){
return s->top == -1;//因为如果栈为空，则栈头索引为-1 ，则返回true
}
1.5 结构操作
推入和弹出
//5.1 推入，栈操作不存在插入一说，只是模拟头进头出的动作
void push(Stack *s,int val){
//1->首先判断栈是否已经满了
if(s->top == s->length-1) return ;
//2->直接推入即可
s->top += 1;
s->data[s->top] = val;
}
//5.2 弹出
void pop(Stack *s){
//1->首先判空
if(empty(s)) return;
//2->弹出是头部弹出，即只需改变头部索引即可
s->top -= 1;
}
1.6 展示栈
从头部开始向下进行展示
//6->输出，从头部开始向下输出
void output(Stack *s){
cout<<"Stack["<<s->top+1<<"] =[";
for (int i = s->top ; i >= 0; i--) {
cout<<s->data[i]<<",";
}
cout<<"]"<<endl;
}
1.7 实际操作
通过实现推入与弹出来展示栈内数据
#define MAX_OP 20
int main(){
srand(time(0));
Stack* s = init_stack(MAX_OP);
for (int i = 0; i < MAX_OP; i++) {
int op = rand() % 4;
int val = rand() % 100;
switch (op) {
case 0: {
cout<<"push "<<val<<" to stack"<<endl;
push(s, val);
}break;
case 1: {
cout<<"push "<<val<<" to stack"<<endl;
push(s, val);
}break;
case 2: {
cout<<"push "<<val<<" to stack"<<endl;
push(s, val);
}break;
case 3: {
cout<<"pop "<<s->data[s->top]<<" from stack"<<endl;
pop(s);
}break;
}
output(s);
}
return 0;
}
2.用于匹配括号是否正确
就是使用自己写的栈来进行的操作
bool isValid(Stack *st ,string s) {
//2.对传来的字符串进行循环
for(int i=0;i<s.size();i++){
if(s[i] == '(') push(st, ')');
else if(s[i] == '[') push(st, ']');
else if(s[i] == '{') push(st, '}');
//这个要注意，当输入进来的s[i]不符合以上三种情况时就要考虑是否与栈顶元素相同，如果相同则说明匹配，如果不同说明此时的顺序是不对的所以就返回false，另一种情况则是如果此时栈是空的，说明s的第一个就是后面的符号肯定不对，直接返回false
else if(empty(st) || s[i] != top(st) ) return false; //要注意顺序
//意思是s[i]与栈顶元素进行了匹配即相同，直接将其弹出即可
else pop(st);
}
return empty(st); //最终返回的是看栈是否是空的，如果为空则正确有效，否则就false
}
