目录
1.括号匹配问题
（1）题目描述
（2）解题思路
代码实现：
#define MAXCAPACITY 4
typedef char Datastyle;
typedef struct stack {
Datastyle* a;
int top;
int capacity;
}ST;
void STInit(ST* ps);
void STDestory(ST* ps);
void STPush(ST* ps, Datastyle x);
void STPop(ST* ps);
Datastyle STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
//初始化栈
void STInit(ST* ps) {
assert(ps);
Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));
if (temp == NULL) {
perror("malloc fail");
exit(-1);
}
ps->a = temp;
ps->capacity = MAXCAPACITY;
ps->top = 0;
}
//销毁栈
void STDestory(ST* ps){
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//插入数据（从栈顶）----（入栈，压栈）
void STPush(ST* ps, Datastyle x) {
assert(ps);
//判断是否满了
if (ps->top == ps->capacity) {
Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle)); //扩容为当前容量的两倍比较合理
if (temp == NULL) {
perror("realloc fail");
return;
}
ps->a = temp;
ps->capacity *= 2;
}
ps->a[ps->top] = x;
ps->top++;
}
//判空
bool STEmpty(ST* ps) {
return (ps->top == 0);
}
//删除数据（从栈顶）----（出栈）
void STPop(ST* ps) {
assert(ps && !STEmpty(ps));
--ps->top;
}
//访问栈顶元素
Datastyle STTop(ST* ps) {
return ps->a[ps->top - 1];
}
//得出栈的元素个数
int STSize(ST* ps) {
assert(ps);
return ps->top;
}
bool isValid(char* s) {
//求解这道题的思路是：我们先对字符串的每个元素进行判断------如果是左括号就让左括号入栈，如果是右括号就出栈顶元素进行匹配------如果是一一匹配就是true，不是就是false
//1、创建一个栈
ST st;
//2、初始化栈
STInit(&st);
//3、开始判断
while(*s){
if(*s == '[' || *s == '{' || *s == '('){
STPush(&st, *s); //入栈
}
else{
if(STEmpty(&st))
{
//4、销毁栈
STDestory(&st);
return false;
} //如果一开始就没有左括号进栈就说明括号不可能匹配的上（这里可以用判空函数进行判断也可以用计数函数是否为零进行判断）
char top = STTop(&st); //储存栈顶元素
STPop(&st); //出栈
if((*s == ']' && top != '[')
|| (*s == '}' && top != '{')
|| (*s == ')' && top != '('))
{
//4、销毁栈
STDestory(&st);
return false;
}
}
s++; //不管进入哪个语句都要使得s++以用来进行循环
}
if(!STEmpty(&st)){ //如果以上循环出来就只剩两种可能性--------（1）字符串中只有左括号，不匹配；（2）一一匹配,循环出来时栈为空
//4、销毁栈
STDestory(&st);
return false;
}
//4、销毁栈
STDestory(&st);
return true;
}
2.循环队列
（1）题目描述
（2）解题思路
循环队列的属性如下:
循环队列的接口方法如下：
代码实现：
typedef struct {
int* a;
int k;
int front;
int rear;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* ps = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (ps == NULL) {
perror("malloc fail");
return NULL;
}
int* ptr = (int*)malloc(sizeof(int) * (k + 1));
if (ptr == NULL) {
perror("malloc fail");
return NULL;
}
ps->a = ptr;
ps->front = ps->rear = 0;
ps->k = k;
return ps;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return ((obj->rear + 1) % (obj->k + 1)) == obj->front;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj)){
return -1;
}
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj)){
return -1;
}
return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->a = NULL;
free(obj);
obj = NULL;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (!myCircularQueueIsFull(obj)) {
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->k + 1);
return true;
}
return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (!myCircularQueueIsEmpty(obj)) {
obj->a[obj->front++] = 0;
obj->front %= (obj->k + 1);
return true;
}
return false;
}