漳州市建设网站,南沙滩做网站公司,桂林市风尚网络科技有限公司,网站举报有奖平台目录 有效的括号
有效的括号【代码】
用队列实现栈
用队列实现栈【代码】
用栈实现队列
用栈实现队列【代码】
设计循环队列 有效的括号 https://leetcode.cn/problems/valid-parentheses/submissions/551394950/
思路#xff1a;把左括号放到栈里#xff0c;取出来栈… 目录 有效的括号
有效的括号【代码】
用队列实现栈
用队列实现栈【代码】
用栈实现队列
用栈实现队列【代码】
设计循环队列 有效的括号 https://leetcode.cn/problems/valid-parentheses/submissions/551394950/
思路把左括号放到栈里取出来栈顶和右括号匹配匹配上了就出栈然后在取出栈顶和下一个右括号匹配一直匹配下去 创建一个栈用来存放左括号然后把字符串的首地址s给ps让ps遍历到\0。 来看看循环里面
第一步判断把左括号全部放进栈里。
第二步判断栈里是不是空是空就没必要匹配了没有左括号直接返回false。
第三步走到第三步说明左括号全部放进栈里了然后取出栈顶给ch
然后左括号和右括号进行匹配匹配成功就出栈匹配不成功就销毁然后返回false。 解决只有一个左括号的情况。
布尔判断栈里是不是空,是空把true给tab不是空返回false给tab。
销毁空间后返回tab。 有效的括号【代码】
typedef char data;
typedef struct stack
{data* arr;int koj;//空间大小int top;//栈顶
}SL;//初始化
void csh(SL* r)
{r-arr NULL;r-koj r-top 0;
}//入栈
void push(SL* r, data x)
{//判断空间够不够if (r-koj r-top){int koj1 r-koj 0 ? 4 : 2 * r-koj;SL* tab (SL*)realloc(r-arr, koj1 * sizeof(SL));if (tab NULL){perror(realloc);exit(1);}r-arr tab;r-koj koj1;}r-arr[r-top] x;r-top;
}bool buer(SL* r)
{assert(r);return r-top 0;
}//出栈
void pop(SL* r)
{assert(r);assert(!buer(r));--r-top;
}
//取栈顶
data qzd(SL* r)
{assert(r);assert(!buer(r));return r-arr[r-top-1];
}
//取有效个数
data size(SL* r)
{assert(r);return r-top;
}//销毁
void xiaoh(SL* r)
{assert(r);if (r-arr ! NULL){free(r-arr);}r-arr NULL;r-koj r-top 0;
}
//上面是栈需要的函数//下面是实现代码
bool isValid(char* s) {//创建一个栈SL add;//把s给pschar*pss;//循环让ps往后走while(*ps!\0){//判断把左括号放进栈里if(*ps( || *ps[ || *ps{){push(add,*ps);}else{//判断栈顶是不是空是空返回false。if(buer(add)){return false;}//取出左括号放进ch来char ch qzd(add);//判断左括号和右括号匹不匹配if((*ps)ch()||( *ps]ch[)|| (*ps} ch{)){//匹配出栈pop(add);}else{//不匹配直接销毁返回falsexiaoh(add);return false;}}ps;}//布尔判断栈里是不是为空是空把true赋值给tab。char tab buer(add) true;xiaoh(add);return tab;
} 用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/description/
实现前先导入队列的函数 思路创建2个队列
入栈不为空的队列Q1。
出栈的话把Q1的size-1的数据1和2插入Q2的队列我们就可以把3出栈了。
https://leetcode.cn/problems/implement-stack-using-queues/ 第一步先创建2个队列来实现栈。
第二步创建ps指向栈然后初始化这2个队列。 入栈为不为空的队列入数据到队列。
if用布尔判断Q1队列是不是空是空往Q2队列入数据调用入队列函数。 第一步把Q1给空队列把Q2给不为空的队列。
第二步判断Q1如果不为空2个交换把Q1给buko把Q2给ko。
第三步循环把有效个数-1的数据给到为空的队列。
取出队头数据给tab,然后入队到空队列再把不为空的队列出队。
第四步把队列的最后一个数据保存到pop然后出队列返回pop。 布尔判断找不为空的队列取出队尾数据返回队尾。 布尔判断2个队列是不是空2个都为真返回true,有1个或2个为假返回false。 销毁直接调用销毁队列的函数就行了然后把obj销毁,把obj置为NULL。 用队列实现栈【代码】
typedef int data;
typedef struct queuedata//单链表
{data arr;//存放的数据struct queuedata* p;//指向下一个节点
}queuedata;typedef struct Queue
{queuedata* to; //队头——单链表的 头节点queuedata* wei;//队尾——单链表的 尾节点int size; //有效个数
}Queue;//初始化
void csh(Queue* r)
{assert(r);r-to r-wei NULL;r-size 0;
}//入队尾
void dui_wei(Queue* r,data x)
{assert(r);//申请单链表空间queuedata* tab (queuedata*)malloc(sizeof(queuedata));if (tab NULL){perror(malloc);exit(1);}//把x赋值给新申请空间的arrtab-arr x;tab-p NULL;//入队//判断队尾是不是空if (r-wei NULL){//是空队头队尾指向新申请的空间r-to r-wei tab;}else//不是空{//队尾p指向新申请的空间r-wei-p tab;//队尾走到新申请的空间r-wei r-wei-p;}//有效个数加1r-size;
}
//布尔类型
bool buer(Queue* r)
{assert(r);return r-to NULL;
}//出队,头
void dui_to(Queue* r)
{assert(r);//布尔类型把真变假把假变真assert(!buer(r));//判断队头等于队尾就说明只有一个节点if (r-to r-wei){//直接释放空间free(r-to);//把队头和队尾置为空r-to r-wei NULL;}else{//把队头的下一个节点给tabqueuedata* tab r-to-p;//释放当前队头节点free(r-to);//把tab节点给队头r-to tab;}//有效个数减1--r-size;
}//取队头数据
data qto(Queue* r)
{assert(r);assert(!buer(r));return r-to-arr;
}//取尾
data qwei(Queue* r)
{assert(r);assert(!buer(r));return r-wei-arr;
}//有效个数
data size(Queue* r)
{assert(r);return r-size;
}//销毁
void xiaoh(Queue* r)
{assert(r);//assert(!buer(r));//把队头给tabqueuedata* tab r-to;//循环销毁单链表while (tab ! NULL){//add保存头节点的下一个节点queuedata* add tab-p;//释放头节点free(tab);//把add给tabtab add;}//把队头和队尾置为空r-to r-wei NULL;//有效个数赋值为0r-size 0;
}
//上面是队列的函数///下面是实现代码
typedef struct {//创建2个队列来实现栈Queue Q1;Queue Q2;} MyStack;//栈初始化
MyStack* myStackCreate()
{//创建ps指向栈MyStack*ps(MyStack*)malloc(sizeof(MyStack));//初始化这2个队列csh(ps-Q1);csh(ps-Q2);return ps;
}//入栈
void myStackPush(MyStack* obj, int x) {//往不为空的队列插入数据if(!buer(obj-Q1)){dui_wei(obj-Q1, x);}else{dui_wei(obj-Q2, x);}
}//出栈
int myStackPop(MyStack* obj) {//空Queue* ko obj-Q1;//不为空Queue* buko obj-Q2;//找不为空的队列if(!buer(obj-Q1)){buko obj - Q1;ko obj - Q2;}//把有数据的队列中size-1个数据导入到空队列中while(size(buko) 1){//取队头给tabint tab qto(buko);//把tab的数据给 ko空队列dui_wei(ko , tab);//出队头dui_to(buko);}//不为空的队列还剩下一个数据给popint pop qto(buko);//最后一个数据出栈dui_to(buko);//返回popreturn pop;
}//取栈顶元素
int myStackTop(MyStack* obj) {//找不为空的队列取出队尾数据if(!buer(obj-Q1)){return qwei(obj-Q1);}else{return qwei(obj-Q2);}
}bool myStackEmpty(MyStack* obj) {//用布尔判断2个队列是不是空return buer(obj-Q1) buer(obj-Q2);
}//销毁
void myStackFree(MyStack* obj) {//直接调用销毁队列的函数就行了xiaoh(obj-Q1);xiaoh(obj-Q2);//把我们申请的ps销毁obj就是ps返回了ps然后obj接收。free(obj);//置为空objNULL;
}/*** 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);
*/
用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/description/
实现前先导入栈的函数 思路用2个栈Q1,Q2
入队列往Q1导入数值
出队列头判断Q2是不是空是就循环取出Q1栈顶导入到Q2Q2再出栈出的就是队头了对了还要先保存队头再返回队头的数据。
取队头数据判断Q2是不是空不是空就说明数据已经导入到Q2了直接取栈顶。
myQueueEmpty判断队列是不是空。
销毁调用销毁函数销毁2个栈再把申请的obj空间释放然后置为空。 第一步创建2个栈。
第二步创建ps空间指向Q1和Q2
然后初始化这2个栈返回ps。 直接调用入栈函数为Q1导入数据就行了。 判断Q2栈是不是空是空的话循环把Q1的全部数值导入到Q2
取出Q2栈顶给tabQ2出栈返回tab。 判断Q2栈是不是空是空的话循环把Q1的全部数值导入到Q2
返回Q2栈顶的元素就行了。 判断队列是不是空是空返回false不是空返回true。 把Q1和Q2的栈销毁然后销毁obj把obj置为空。 用栈实现队列【代码】
typedef int data;
typedef struct stack
{data* arr;//存放数值int koj; //空间int top; //栈顶
}stack;//初始化
void stack_csh(SL* r)
{assert(r);r-arr NULL;r-koj r-top 0;
}//入栈
void stack_push(stack* r, data x)
{assert(r);//空间大小等于栈顶就说明空间不够if (r-koj r-top){int koj1 r-koj 0 ? 4 : 2 * r-koj;stack* tab (stack*)realloc(r-arr, sizeof(stack));if (tab NULL){perror(realloc);exit(1);}//把新申请的空间给rr-arr tab;r-koj koj1;}//空间够直接入栈r-arr[r-top] x;r-top;
}//布尔类型
bool buer(stack* r)
{assert(r);return r-top 0;
}//出栈
void stack_pop(stack* r)
{assert(r);//布尔类型assert(!buer(r));r-top--;
}//取出栈顶
data stack_top(stack* r)
{assert(r);assert(!buer(r));return r-arr[r-top - 1];
}//有效个数
data stack_size(stack* r)
{assert(r);return r-top;
}//销毁
void xiaoh(stack* r)
{assert(r);if (r-arr ! NULL){free(r-arr);}r-arr NULL;r-koj r-top 0;
}
//上面是栈的函数///下面是实现代码
typedef struct {//创建2个栈stack Q1;stack Q2;
} MyQueue;//初始化
MyQueue* myQueueCreate() {//创建指针指向Q1和Q2MyQueue* ps (MyQueue*)malloc(sizeof(MyQueue));//初始化2个栈stack_csh(ps-Q1);stack_csh(ps-Q2);//返回psreturn ps;
}//入栈入队列
void myQueuePush(MyQueue* obj, int x) {//调用入栈函数为Q1入栈stack_push(obj-Q1 , x);
}//出栈出队列头
int myQueuePop(MyQueue* obj) {//判断Q2是不是空不是空说明Q2栈里有数据if( buer(obj-Q2) ){//是空循环取出Q1的数值导入Q2栈里while(!buer(obj-Q1)){//入栈到Q2 取出Q1栈顶stack_push(obj-Q2,stack_top(obj-Q1));//Q1出栈stack_pop(obj-Q1);}}//取出Q2的栈顶给tab取队头int tab stack_top(obj-Q2);//Q2出栈stack_pop(obj-Q2);return tab;
}//取栈顶队头
int myQueuePeek(MyQueue* obj) {//判断Q2是不是空不是空说明Q2栈里有数据if( buer(obj-Q2) ){//是空循环取出Q1的数值导入Q2栈里while(!buer(obj-Q1)){//入栈到Q2 取出Q1栈顶stack_push(obj-Q2,stack_top(obj-Q1));//Q1出栈stack_pop(obj-Q1);}}//返回Q2的栈顶返回队头return stack_top(obj-Q2);
}bool myQueueEmpty(MyQueue* obj) {//判断这2个栈是不是都为空判断队列是不是空return buer(obj-Q1) buer(obj-Q2);
}void myQueueFree(MyQueue* obj) {//销毁xiaoh(obj-Q1);xiaoh(obj-Q2);//也把obj销毁free(obj);objNULL;
}/*** 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);
*/ 设计循环队列
https://leetcode.cn/problems/design-circular-queue/description/
这个队列底层使用数组比较好实现。 结构体的参数数组头尾空间大小。 申请ps的一个结构体
给arr申请一个数值的空间我们申请的数值空间必须多一块空间方便5%5等于0。
初始化把头尾初始化为0空间大小初始化为kk就是4。 第一步先判断队列是不是满了满了直接返回false没有满插入数据。
第二步为arr数组wei下标位置插入数据然后参考【1%51, 2%52 3%53, 4%54, 5%50】。
当wei走到下标为55%50,所以就会回到0返回true。 第一步判断队列是不是空是空直接返回false。
第二步头直接就好了1%51, 2%52 3%53, 4%54, 5%50
当to走到下标为55%50,所以就会回到0返回true。 先判断是不是空不是空返回头是空返回-1。 第一步判断队列是不是空。
第二步把wei-1的数据赋值tab为什么是wei-1呢 上面这一张图我们可以看到插入数据后就了所以我们取队尾wei-1。
第三步判断尾下标是不是0这里是一种特殊情况0-1-1,-1没有下标 我们直接把空间大小给tab就是下标为4这个元素了。
返回arr下标为tab的数值。 设计循环队列代码
typedef struct {int *arr;int to;//头int wei;//尾int kojdax;//空间大小
} MyCircularQueue;//初始化
MyCircularQueue* myCircularQueueCreate(int k) {//申请空间MyCircularQueue* ps (MyCircularQueue*)malloc(sizeof(MyCircularQueue));// 4 * 5 20,就是5个空间ps-arr (int*)malloc(sizeof(int) * (k 1));//初始化ps-to ps-wei 0;ps-kojdax k;return ps;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//判断队列是不是满了等于头就说明满了return (obj-wei1) % (obj-kojdax1) obj-to;
}//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了不能插入数据if(myCircularQueueIsFull(obj)){return false;}//在wei位置插入数据然后obj-arr[obj-wei] value;//5 % 5 0rear走到5下标的时候回到下标为0的位置。obj-wei % obj-kojdax 1;return true;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//等于就说明队列是空return obj-to obj-wei;
}//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空if(myCircularQueueIsEmpty(obj)){return false;}//队列不为空//头往后走就行obj-to;//会越界所以:5 % 5 0to走到5下标的时候回到下标为0的位置。obj-to % obj-kojdax 1;return true;
}//取队头
int myCircularQueueFront(MyCircularQueue* obj) {//判断队列是不是空if(myCircularQueueIsEmpty(obj)){return -1;}//返回头return obj-arr[obj-to];}//取队尾
int myCircularQueueRear(MyCircularQueue* obj) {//判断队列是不是空if(myCircularQueueIsEmpty(obj)){return -1;}//把wei-1的数据给tabint tab obj-wei - 1;//尾等于下标0if(obj-wei 0){//把有效个数4给tabtab obj - kojdax;}//返回tabreturn obj-arr[tab];
}//销毁
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-arr);free(obj);objNULL;
}
