OJ题目【栈和队列】

目录

有效的括号

有效的括号【代码】

用队列实现栈

用队列实现栈【代码】

用栈实现队列

用栈实现队列【代码】

设计循环队列

---

有效的括号

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*ps=s;//循环让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);//置为空obj=NULL;
}/*** 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栈顶，导入到Q2，Q2再出栈，出的就是队头了，对了还要先保存队头，再返回队头的数据。

取队头数据：判断Q2是不是空，不是空就说明数据已经导入到Q2了，直接取栈顶。

myQueueEmpty：判断队列是不是空。

销毁：调用销毁函数，销毁2个栈，再把申请的obj空间释放，然后置为空。

---

第一步：创建2个栈。

第二步：创建ps空间指向Q1和Q2，

然后初始化这2个栈，返回ps。

---

直接调用，入栈函数，为Q1导入数据就行了。

---

判断Q2栈是不是空，是空的话循环把Q1的全部数值，导入到Q2，

取出Q2栈顶给tab，Q2出栈，返回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);obj=NULL;
}/*** 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，空间大小初始化为k，k就是4。

---

第一步：先判断队列是不是满了，满了直接返回false，没有满插入数据。

第二步：为arr数组wei下标位置插入数据，然后++，参考【1%5=1, 2%5=2 ，3%5=3, 4%5=4, 5%5=0】。

当wei走到下标为5，5%5=0,所以就会回到0，返回true。

---

第一步：判断队列是不是空，是空直接返回false。

第二步：头直接++就好了，1%5=1, 2%5=2 ，3%5=3, 4%5=4, 5%5=0

当to走到下标为5，5%5=0,所以就会回到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->wei+1) % (obj->kojdax+1) == obj->to;
}//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了不能插入数据if(myCircularQueueIsFull(obj)){return false;}//在wei位置插入数据，然后++obj->arr[obj->wei++] = value;//5 % 5 = 0，rear走到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 = 0，to走到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);obj=NULL;
}