👩💻博客主页：风起 风落的博客主页
✨欢迎关注🖱点赞🎀收藏⭐留言✒
👕参考网站：牛客网
🎨你的收入跟你的不可替代成正比
🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦
💬给大家介绍一个求职刷题收割offer的地方👉点击网站
在这里插入图片描述
@TOC
一、20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
typedef char datatype; typedef struct stack { datatype* a; int top; int capacity; }ST; void stackinit(ST* p); void stackpush(ST* p,datatype x); datatype stacktop(ST* p); void stackpop(ST* p); int stacksize(ST* p); bool stackempty(ST* p); void stackdestroy(ST* p); void stackinit(ST* p)//栈的初始化 { assert(p); p->a = NULL; p->top = 0; p->capacity = 0; } void stackpush(ST* p, datatype x)//入栈 { assert(p); if (p->top == p->capacity) { int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity; datatype* tmp = (datatype*)realloc(p->a, sizeof(datatype)*newcapacity); if (tmp != NULL) { p->a = tmp; p->capacity = newcapacity; } } p->a[p->top] = x; p->top++; } void stackpop(ST* p)//移除栈顶元素 { assert(p); assert(p->top > 0); p->top--; } datatype stacktop(ST* p)//出栈 { assert(p); assert(p->top>0); return p->a[p->top - 1]; } bool stackempty(ST* p)//是否为空 { return p->top == 0; } int stacksize(ST* p)//栈中元素个数 { assert(p); return p->top; } void stackdestroy(ST* p)//内存销毁 { assert(p); free(p->a); p->a = NULL; p->top = 0; p->capacity = 0; } bool isValid(char * s){ ST p; stackinit(&p); while(*s) { if((*s=='(')||(*s=='{')||(*s=='[')) { stackpush(&p,*s); s++; } else { if(stackempty(&p))//当只有']'时，栈中没有数据存在 ，判断是否为空， { //为空则false stackdestroy(&p); return false; } datatype top=stacktop(&p); stackpop(&p); if((top=='[')&&(*s!=']')||(top=='{')&&(*s!='}')||(top=='(')&&(*s!=')')) { stackdestroy(&p); return false; } else { s++; } } } bool ret=stackempty(&p);//当只有'['进入判断栈是否为空 若不为空则false stackdestroy(&p); return ret; }
将左边的括号移入栈中,若碰到右括号 取出栈顶的元素，并将删除栈顶元素
比较 此时的栈顶元素是否与右括号匹配 ，若匹配则 s++,若不匹配就报错
当只有'['输入时 ,循环直接出来了, 栈中还有元素存在，判断栈是否为空
若不为空则返回fasle
当只有']'输入时，栈中无元素存在，判断栈是否为空，若为空则返回fasle
二、225. 用队列实现栈
：
>请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。 实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 >注意： 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。 >示例： 输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
c
typedef int datatype;
typedef struct queuenode
{
datatype data;
struct queuenode* next;
}queuenode;
typedef struct queue
{
queuenode* head;
queuenode* tail;
}queue;
void queueinit(queue* p);
void queuedestroy(queue* p);
void queuepush(queue* p, datatype x);
void queuepop(queue* p);
datatype queuefront(queue* p);
datatype queueback(queue* p);
int queuesize(queue* p);
bool queueempty(queue* p);
void queueinit(queue* p)//初始化队列
{
assert(p);
p->head = NULL;
p->tail = NULL;
}
void queuedestroy(queue* p)//内存销毁
{
assert(p);
queuenode* cur = p->head;
while (cur != NULL)
{
queuenode* next = cur->next;
free(cur);
cur = next;
}
p->head = NULL;
p->tail = NULL;
}
void queuepush(queue* p, datatype x)//入队列 (队尾入)
{
assert(p);
queuenode* newnode = (queuenode)malloc(sizeof(queuenode)); newnode->data = x; newnode->next = NULL; if (p->tail == NULL) { p->tail = newnode; p->head = newnode; } else { p->tail->next = newnode; p->tail = newnode; } } void queuepop(queue p)//删除数据
{
assert(p);
assert(!queueempty(p));//断言队列是否为空
queuenode* next = p->head->next;
free(p->head);
p->head = next;
if (p->head == NULL)//当删除只剩下最后一个节点时 head与tail都指向，free(head) ,tail就变成了野指针
{
p->tail = NULL;
}
}
datatype queuefront(queue* p)//取队头数据
{
assert(p->head);
assert(!queueempty(p));
return p->head->data;
}
datatype queueback(queue* p)//取队尾数据
{
assert(p->head);
assert(!queueempty(p));
return p->tail->data;
}
int queuesize(queue* p)//队的数量
{
assert(p);
int sum = 0;
queuenode* cur = p->head;
while (cur != NULL)
{
sum++;
cur = cur->next;
}
return sum;
}
bool queueempty(queue* p)//判断队列是否为空
{
assert(p);
return p->head == NULL;
}
typedef struct {
queue q1;
queue q2;
} MyStack;
MyStack* myStackCreate() {//初始化
MyStackobj=(MyStack)malloc(sizeof(MyStack));
queueinit(&obj->q1);
queueinit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {// 将元素 x 压入栈顶
if(!queueempty(&obj->q1))
{
queuepush(&obj->q1,x);
}
else
{
queuepush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {//移除并返回栈顶元素
queueempty=&obj->q1; queuenoempty=&obj->q2;
if(!queueempty(&obj->q1))
{
noempty=&obj->q1;
empty=&obj->q2;
}
while(queuesize(noempty)>1)
{
queuepush(empty,queuefront(noempty));
queuepop(noempty);
}
int top=queuefront(noempty);
queuepop(noempty);
return top;
}
int myStackTop(MyStack* obj) {// 返回栈顶元素
if(!queueempty(&obj->q1))
{
return queueback(&obj->q1);
}
else
{
return queueback(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {//当两个队列都为空时
return queueempty(&obj->q1)&&queueempty(&obj->q2);
}
void myStackFree(MyStack* obj) {
queuedestroy(&obj->q1);
queuedestroy(&obj->q2);
free(obj);
}
/**
- Your MyStack struct will be instantiated and called as such:
- MyStack* obj = myStackCreate();
- myStackPush(obj, x);
- int param_2 = myStackPop(obj);
- int param_3 = myStackTop(obj);
- bool param_4 = myStackEmpty(obj);
- myStackFree(obj);
*/
>主要思想为将数据传入不为空的队列中，想要找到栈顶元素时就将n-1个元素都转移到空的队列中， >返回不为空的队列的最后一个元素即栈顶元素并删除元素,若此时再返回栈顶元素即队列最后一个元素 > # 三、232. 用栈实现队列 >请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： >实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false 说明： 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。 >示例 1： 输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false >提示： 1 <= x <= 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
c
typedef int datatype;
typedef struct stack
{
datatype* a;
int top;
int capacity;
}ST;
void stackinit(ST* p);
void stackpush(ST* p,datatype x);
datatype stacktop(ST* p);
void stackpop(ST* p);
int stacksize(ST* p);
bool stackempty(ST* p);
void stackdestroy(ST* p);
void stackinit(ST* p)//栈的初始化
{
assert(p);
p->a = NULL;
p->top = 0;
p->capacity = 0;
}
void stackpush(ST* p, datatype x)//入栈
{
assert(p);
if (p->top == p->capacity)
{
int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
datatype* tmp = (datatype)realloc(p->a, sizeof(datatype)newcapacity);
if (tmp != NULL)
{
p->a = tmp;
p->capacity = newcapacity;
}
}
p->a[p->top] = x;
p->top++;
}
void stackpop(ST* p)//移除栈顶元素
{
assert(p);
assert(p->top > 0);
p->top--;
}
datatype stacktop(ST* p)//出栈
{
assert(p);
assert(p->top>0);
return p->a[p->top - 1];
}
bool stackempty(ST* p)//是否为空
{
return p->top == 0;
}
int stacksize(ST* p)//栈中元素个数
{
assert(p);
return p->top;
}
void stackdestroy(ST* p)//内存销毁
{
assert(p);
free(p->a);
p->a = NULL;
p->top = 0;
p->capacity = 0;
}
typedef struct {
ST pushST;
ST popST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueueobj=(MyQueue)malloc(sizeof(MyQueue));
stackinit( &obj->pushST);
stackinit(&obj->popST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
stackpush(&obj->pushST,x);//将数据都传入pushST中
}
int myQueuePop(MyQueue* obj) {//判断popST是否为空 若为空则将pushST的数据传入popST中，
//若不为空则直接返回队列开头
if(stackempty(&obj->popST))
{
while(stacksize(&obj->pushST))
{
stackpush(&obj->popST,stacktop(&obj->pushST));
stackpop(&obj->pushST);
}
}
int front=stacktop(&obj->popST);
stackpop(&obj->popST);
return front;
}
int myQueuePeek(MyQueue* obj) {//返回队列开头的元素
if(stackempty(&obj->popST))
{
while(stacksize(&obj->pushST))
{
stackpush(&obj->popST,stacktop(&obj->pushST));
stackpop(&obj->pushST);
}
}
return stacktop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj) {//两个栈都为空才为空
return stackempty(&obj->pushST)&&stackempty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
stackdestroy(&obj->pushST);
stackdestroy(&obj->popST);
free(obj);
}
/**
- Your MyQueue struct will be instantiated and called as such:
- MyQueue* obj = myQueueCreate();
- myQueuePush(obj, x);
- int param_2 = myQueuePop(obj);
- int param_3 = myQueuePeek(obj);
- bool param_4 = myQueueEmpty(obj);
- myQueueFree(obj);
*/
>本题与上个类似题不同的是，如果设置一个为空的栈，一个不为空的栈，则会发现将数据传给空的栈中时，因为栈时先进后出，所以顺序回颠倒。 >所以这道题采用一个只管入数据的pushST，一个只管出数据的popST > # 四、622. 设计循环队列 >设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你的实现应该支持如下操作： MyCircularQueue(k): 构造器，设置队列长度为 k 。 Front: 从队首获取元素。如果队列为空，返回 -1 。 Rear: 获取队尾元素。如果队列为空，返回 -1 。 enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 isEmpty(): 检查循环队列是否为空。 isFull(): 检查循环队列是否已满。 >示例： MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4
c
typedef struct {
int* a;
int front;
int tail;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueueobj=( MyCircularQueue)malloc(sizeof( MyCircularQueue));
obj->a=(int)malloc(sizeof(int)(k+1));
obj->front =0;
obj->tail=0;
obj->k=k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->tail]=value;
obj->tail++;
obj->tail%=(obj->k+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front++;
obj->front%=(obj->k+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
if(obj->tail==0)
{
return obj->a[obj->k];
}
else
{
return obj->a[obj->tail-1];
}
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->k+1)==obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
/**
- Your MyCircularQueue struct will be instantiated and called as such:
- MyCircularQueue* obj = myCircularQueueCreate(k);
- bool param_1 = myCircularQueueEnQueue(obj, value);
- bool param_2 = myCircularQueueDeQueue(obj);
- int param_3 = myCircularQueueFront(obj);
- int param_4 = myCircularQueueRear(obj);
- bool param_5 = myCircularQueueIsEmpty(obj);
- bool param_6 = myCircularQueueIsFull(obj);
- myCircularQueueFree(obj);
*/
```
本题采用用数组实现:
分为两种情况:
为空时：
若phead==tail时 为空
在这里插入图片描述为满时:此时需要考虑空间的问题, 1.若只取k个空间需要进入数据时，tail被赋值,tail向后移一个，当最后一块空间被赋值时，tail回到下标为0的数组中，此时tail ==front与判断空的条件相同 ，所以不成立。
在这里插入图片描述 2.若取k+1个空间
正常情况：
tail+1==front
在这里插入图片描述 特殊情况下
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
