Guff_9hys

这个屌丝很懒，什么也没留下！

热门标签

OJ题目【栈和队列】

作者：Guff_9hys | 2024-08-19 06:17:33

踩

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给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。

用队列实现栈【代码】


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置为空。

用栈实现队列【代码】


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的数值。

设计循环队列代码


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

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】