OJ题目【栈和队列】
逆向-落叶 2024-08-16 13:05:02 阅读 96
目录
有效的括号
有效的括号【代码】
用队列实现栈
用队列实现栈【代码】
用栈实现队列
用栈实现队列【代码】
设计循环队列
有效的括号
https://leetcode.cn/problems/valid-parentheses/submissions/551394950/
思路：把左括号放到栈里，取出来栈顶和右括号匹配，匹配上了就出栈，然后在取出栈顶和下一个右括号匹配，一直匹配下去，
创建一个栈用来存放左括号，然后把字符串的首地址s给ps，让ps遍历到\0。
来看看循环里面，
第一步：判断把左括号全部放进栈里。
第二步：判断栈里是不是空，是空就没必要匹配了，没有左括号，直接返回false。
第三步：走到第三步，说明左括号全部放进栈里了，然后取出栈顶给ch，
然后左括号和右括号进行匹配，匹配成功就出栈，匹配不成功就销毁，然后返回false。
解决只有一个左括号的情况。
布尔判断栈里是不是空,是空把true给tab，不是空返回false给tab。
销毁空间后，返回tab。
有效的括号【代码】
<code>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给ps
char*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
{//不匹配直接销毁返回false
xiaoh(&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。
用队列实现栈【代码】
<code>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赋值给新申请空间的arr
tab->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;
}
//有效个数加1
r->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
{
//把队头的下一个节点给tab
queuedata* 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));
//把队头给tab
queuedata* tab = r->to;
//循环销毁单链表
while (tab != NULL)
{
//add保存头节点的下一个节点
queuedata* add = tab->p;
//释放头节点
free(tab);
//把add给tab
tab = add;
}
//把队头和队尾置为空
r->to = r->wei = NULL;
//有效个数赋值为0
r->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)
{
//取队头给tab
int tab = qto(buko);
//把tab的数据给 ko空队列
dui_wei(ko , tab);
//出队，头
dui_to(buko);
}
//不为空的队列还剩下一个数据，给pop
int pop = qto(buko);
//最后一个数据出栈
dui_to(buko);
//返回pop
return 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置为空。
用栈实现队列【代码】
<code>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);
}
//把新申请的空间给r
r->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和Q2
MyQueue* ps = (MyQueue*)malloc(sizeof(MyQueue));
//初始化2个栈
stack_csh(&ps->Q1);
stack_csh(&ps->Q2);
//返回ps
return 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的数值。
设计循环队列代码
<code>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的数据给tab
int tab = obj->wei - 1;
//尾等于下标0
if(obj->wei == 0)
{
//把有效个数4给tab
tab = obj -> kojdax;
}
//返回tab
return obj->arr[tab];
}
//销毁
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
obj=NULL;
}
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。