文章目录
- 1. 栈
- 2. 栈的初始化和栈的销毁
- 3. 入栈和出栈(压栈)
- 4. 取栈顶元素并打印
- 5. 栈的练习题
-
1. 栈
- 栈:也是一种线性表,其数据结构与动态顺序表的数据结构类似
- 栈分为栈顶和栈底,在栈中,插入数据和删除数据被称为入栈和出栈
- 栈的相关操作都是在栈顶实现的,而栈底通常不会改变
- 栈的底层结构可以通过数组和链表实现,但是链表在入栈和出栈操作上,会出现指针指向改变的问题,相对而言,数组反而只需要改变其size(在栈中被称为栈顶top)大小即可,因此用数组来实现栈的底层更佳
2. 栈的初始化和栈的销毁
void StackInit(Stack* ps)
{
assert(ps);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
3. 入栈和出栈(压栈)
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps && ps->top);
ps->top--;
}
4. 取栈顶元素并打印
STDataType StackTop(Stack* ps)
{
assert(ps && ps->arr);
return ps->arr[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
void StackPrint(Stack* ps)
{
assert(ps);
while (ps->top)
{
STDataType top = StackTop(ps);
printf("%d ", top);
ps->top--;
}
}
5. 栈的练习题
5.1 有效的括号
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;
int capacity;
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps && ps->top);
ps->top--;
}
STDataType StackTop(Stack* ps)
{
return ps->arr[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
bool isValid(char* s)
{
Stack st;
StackInit(&st);
char* pi = s;
while (*pi != '\0')
{
if (*pi == '(' || *pi == '[' || *pi == '{')
StackPush(&st, *pi);
else
{
char top = StackTop(&st);
if ((top == '(' && *pi == ')') || (top == '[' && *pi == ']') || (top == '{' && *pi == '}'))
StackPop(&st);
else
{
StackDestroy(&st);
return false;
}
}
pi++;
}
bool ret = StackEmpty(&st) ? true : false;
StackDestroy(&st);
return ret;
}