力扣刷题：栈和队列OJ篇（下）

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

废话不多说，我们直接看题。

1.括号匹配问题

（1）题目描述

（2）解题思路

• 左括号入栈，右括号出栈，一一配对
• 我们先对字符串的每个元素进行判断------如果是左括号就让左括号入栈，如果是右括号就出栈顶元素进行匹配------如果是一一匹配就是true，不是就是false

代码实现：

#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）解题思路

• 在循环队列中，当队列为空，可知front=rear；而当所有队列空间全占满时，也有 front=rear。为了区别这两种情况，假设队列使用的数组有 capacity 个存储空间，则此时规定循环队列最多只能有capacity−1 个队列元素，当循环队列中只剩下一个空存储单元时，则表示队列已满。根据以上可知，队列判空的条件是 front=rear，而队列判满的条件是 front(rear+1)modcapacity。对于一个固定大小的数组，只要知道队尾 rear 与队首 front，即可计算出队列当前的长度(rear−front+capacity)modcapacity

循环队列的属性如下:

elements：一个固定大小的数组，用于保存循环队列的元素。
capacity：循环队列的容量，即队列中最多可以容纳的元素数量。
front：队列首元素对应的数组的索引。
rear：队列尾元素对应的索引的下一个索引。

循环队列的接口方法如下：

MyCircularQueue(int k): 初始化队列，同时base 数组的空间初始化大小为 k+1。front,rear 全部初始化为 0。
enQueue(int value)：在队列的尾部插入一个元素，并同时将队尾的索引 rear 更新为 (rear+1)modcapacity。
deQueue()：从队首取出一个元素，并同时将队首的索引 front 更新为 (front+1)modcapacity。
Front()：返回队首的元素，需要检测队列是否为空。
Rear()：返回队尾的元素，需要检测队列是否为空。
isEmpty()：检测队列是否为空，根据之前的定义只需判断 rear 是否等于 front。
isFull()：检测队列是否已满，根据之前的定义只需判断 front 是否等于 (rear+1)modcapacity。

代码实现：

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;
}

快乐的时光总是短暂，咱们下篇博文再见啦！！！如果小编的文章会对你有帮助的话不要忘了，记得给小编点赞、收藏支持一下，在此非常感谢！！！