• OJ题目【栈和队列】

    题目导入

    栈：

    队列

    栈

    题目一 有效的括号

    题目要求

    给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：

    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。
    3. 每个右括号都有一个对应的相同类型的左括号。

    下图为力扣的示例
    在这里插入图片描述
    题目代码原型

    bool isValid(char* s) {
	//The code is written here
}

    这题就很适合用栈来实现，当是左括号的时候就入栈，如果是右括号就与栈顶的左括号进行对比，如果匹配成功就将栈顶的左括号给Pop掉
    创建栈

        Stack st;
    StackInit(&st);

    入栈函数：

     if (*s == '(' || *s == '[' || *s == '{')
 {
     StackPush(&st, *s);
 }

    但是匹配了没有意义，因为栈内可能还有多个元素，所以我们要判断不匹配的情况（不匹配可以直接出结果）
    代码如下：

     else
 {
     STDataType tmp = StackTop(&st);
     StackPop(&st);
     if ((tmp == '(' && *s != ')') ||
         (tmp == '[' && *s != ']') ||
         (tmp == '{' && *s != '}'))
     {
         StackDestroy(&st);
         return false;
     }
 }

    这是判断一次，题目的s不可能就这这么点字符，所以我们要使用循环

        while (*s)
    {
        if (*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st, *s);
        }
        else
        {
            STDataType tmp = StackTop(&st);
            StackPop(&st);
            if ((tmp == '(' && *s != ')') ||
                (tmp == '[' && *s != ']') ||
                (tmp == '{' && *s != '}'))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }

    循环走出来了，就代表s已经走到\0了，这时候我们就需要判断栈内是否还有元素，如果还有就代表s并不是一个有效的字符串（有效字符串需满足：每个右括号都有一个对应的相同类型的左括号。）
    代码如下

        if (!StackEmpty(&st))//栈为非空，还有元素
    {
        StackDestroy(&st);
        return false;
    }
    StackDestroy(&st);
    return true;

    这样大体就写完了，但是这还有个问题：当s的第一个元素就是右括号该怎么办？
    其实很简单，当s的第一个元素就是右括号的时候，就代表s并不是一个有效的字符串，并且这时候的栈是空的，所以我们只需要对栈进行判空操作就好了。

        while (*s)
    {
        if (*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st, *s);
        }
        else
        {
            if (StackEmpty(&st))//当s的第一个元素就是右括号
            {
                StackDestroy(&st);
                return false;
            }
            STDataType tmp = StackTop(&st);
            StackPop(&st);
            if ((tmp == '(' && *s != ')') ||
                (tmp == '[' && *s != ']') ||
                (tmp == '{' && *s != '}'))
            {
                StackDestroy(&st);
                return false;
            }
        }

    完整代码：

    bool isValid(char* s) {
    Stack st;//创建栈
    StackInit(&st);
    while (*s)
    {
        if (*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st, *s);
        }
        else
        {
            if (StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            //方法一
            STDataType tmp = StackTop(&st);
            StackPop(&st);
            if ((tmp == '(' && *s != ')') ||
                (tmp == '[' && *s != ']') ||
                (tmp == '{' && *s != '}'))
            {
                StackDestroy(&st);
                return false;
            }
            
            //方法二(任选其一)
            if ((StackTop(&st) == '(' && *s != ')') ||
                (StackTop(&st) == '[' && *s != ']') ||
                (StackTop(&st) == '{' && *s != '}'))
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
            	StackPop(&st);
            }
        }
        s++;
    }
    if (!StackEmpty(&st))
    {
        StackDestroy(&st);
        return false;
    }
    StackDestroy(&st);
    return true;
}

    在函数结束先，将自己在该函数开辟的空间个释放掉，这是一个好习惯。

    题目二 用栈实现队列

    在这里插入图片描述
    队列是先进先出，栈是先进后出，这题我们就需要使用两个栈来实现了。
    先入栈的元素是在栈底，而先出的元素是在栈顶，所以我们把有元素的栈里面的元素入到没有元素的栈里面，就能完成队列的出队操作，类似下图
    在这里插入图片描述

    我们入队列（用栈实现的）是入到有元素的栈里面，因为我将数据入到非空栈的时候是入到栈顶的，当我要进行出队列的时候，是将栈下标一及以后的元素入到空栈，再将非空栈的栈底元素Pop掉
    在这里插入图片描述

    peek的要求是返回队列开头的元素，这样我们直接返回非空栈中下标为0的元素。

    完整代码

    // 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_top = 0;
	ps->_capacity = 0;
}


// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	if (ps->_top == ps->_capacity)
	{
		int _NewCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		STDataType* _tmp = (STDataType*)realloc(ps->_a, _NewCapacity * sizeof(STDataType));
		ps->_a = _tmp;
		ps->_capacity = _NewCapacity;
	}
	ps->_a[ps->_top++] = data;
}


// 出栈 
void StackPop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	ps->_top--;
}


// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	return ps->_a[ps->_top - 1];
}


// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps && ps->_top > 0);
	return ps->_top;
}


// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	return (ps->_top == 0);
}


// 销毁栈 
void StackDestroy(Stack* ps)
{
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}

typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&(obj->s1));
    StackInit(&(obj->s2));

    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    if(!StackEmpty(&obj->s1))
    {
        StackPush(&obj->s1,x);
    }
    else
    {
        StackPush(&obj->s2,x);
    }
    
}

int myQueuePop(MyQueue* obj) {
	//假设法
    Stack* Empty = &obj->s1;
    Stack* NotEmpty = &obj->s2;
    if(!StackEmpty(Empty))
    {
        Empty = &obj->s2;
        NotEmpty = &obj->s1;
    }
    
    int top = StackSize(NotEmpty);
    int tmp = 1;
    while(tmp != top)
    {
        StackPush(Empty,NotEmpty->_a[tmp++]);
        StackPop(NotEmpty);
    }
    int val = StackTop(NotEmpty);
    StackPop(NotEmpty);
    return val;
}

int myQueuePeek(MyQueue* obj)
{
    if(!StackEmpty(&obj->s1))
    {
        return obj->s1._a[0];
    }
    else
    {
        return obj->s2._a[0];
    }

}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);

    obj = NULL;
}

    队列

    题目：实现循环队列

    在这里插入图片描述
    循环队列可以用数组和链表来实现，本文是用数组实现。
    可能有很多人看到题目就设计一个数组，定一个head和tail当head或者tail到了数组结尾的时候，就绕回到数组开头。
    在这里插入图片描述

    但是这里有个问题：我的判空和判满该这么区分呢？
    判空很简单，判断head是否等于tail，是的话就是空。但是，在这个数组中，判满的逻辑也是判断head是否等于tail。
    这种情况也别称为假溢出。

    这时候我们就有两种方法来解决。

    • 第一种：使用一个size来记录，数组元素的个数，如果等于数组长度就是满，如果等于零就是空
    • 第二种：在开辟数组的时候多开一个空间，这个空间在逻辑上是不存放数组的，这里的不存放是说在存放数据的时候，就是有某块空间不存放数据，并不是多开的那个空间不存放数据。如下图在这里插入图片描述

    如图所示，当判满成立的时候，就是有某块空间不存放数据，上图tail所指向的空间，那里面的元素已经被我Pop掉了，已经不认为是队列内的元素了
    所以方法二也可以将判满和判空给区分开来

    判满：看tail+1是否等于head（当然要解决回绕的问题）
    判空就还是看tail是否等于head。

    本文使用的是第二种方法。

    循环队列的创建(myCircularQueueCreate)

    假设队列的长度为k

    typedef struct {
    int * _a;
    int _head;
    int _tail;
    int _k; //该队列的长度
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
	//先开辟队列
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //再开辟队列的数组部分
    obj->_a = (int*)malloc(sizeof(int)* (k+1));//多开一个空间
    obj->_head = obj->_tail = 0;
    obj->_k = k;//将队列长度k赋值给我的_k
    return obj;
}

    注：因为力扣上的动态开辟基本不会报错，所以可以省略判断开辟成功的步骤（在日常敲代码的时候还是判断比较好）

    解决回绕问题：

    当我的tail等于k+1的时候，直接取模就好了
    当然也可以暴力一点，不管tail的值，直接取模

    obj->_tail %= obj->_k+1;

    所以我们就可以直接写判空和判满的代码了：

    //判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->_head == obj->_tail;
}

//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->_tail+1) % (obj->k+1) == obj->_head;
}

    入队列(myCircularQueueEnQueue)

    题目代码：

    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    
}

    题目对这段代码的要求： 向循环队列插入一个元素。如果成功插入则返回真。

    那么插入不成功就返回假（队列满了就不能插入了）
    所以可以直接调用判满函数

    if(myCircularQueueIsFull(obj))
{
	return false;
}

    如果没满，就继续插入，然后解决回绕问题，也可以使用暴力方法（不管tail的大小，直接%上k+1）

    //插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }

    obj->_a[obj->_tail++] = value;
    //方法一（暴力）
    obj->_tail %= (obj->_k+1);
	
	//方法二（判断）
	if(obj->_tail == obj->_k+1)
    {
        obj->_tail = 0;
    }
    return true;
}

    出队列(myCircularQueueDeQueue)

    题目代码：

    //删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {

}

    题目对这段代码的要求：从循环队列中删除一个元素。如果成功删除则返回真。

    那么删除不成功就返回假（队列空了就不能插入了）
    所以可以直接调用判空函数

        if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }

    因为队列是先进先出(FIFO)，所以我们继续出队列的时候并不是对tail操作，而是对head操作。
    出队列的时候直接++head就好了（当然也要解决回绕问题）。
    解决回绕问题和入队列的操作是一样的。

    //删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->_head++;
    obj->_head %= (obj->_k + 1);
    return true;
    
}

    取队头元素(myCircularQueueFront)

    题目对这个函数的要求：从队首获取元素。如果队列为空，返回 -1 。
    直接返回head位置的元素就好了

    //取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->_a[obj->_head];
}

    取队尾元素(myCircularQueueRear)

    题目对这个函数的要求：获取队尾元素。如果队列为空，返回 -1 。

    注意：我这里的tail其实是指向待插入数据的空间，也就是最后一个元素的下一个空间。
    所以我们返回尾元素，其实是返回tail的前一个空间。
    一般情况下只需要返回tail - 1就可以了，但是，有一种特殊情况，就是当入完队列后我的tail进行了回绕，这时候tail是0，我这时返回tail - 1的元素就会造成越界。在这里插入图片描述
    有两种方法处理

    • 第一种：判断tail是否等于0，是的话返回下标为 k 个元素。
    • 第二种：先tail-1然后加上k+1再%k+1，这种方法不需要判断tail，可以直接返回值。
    //第一种
return obj->_a[obj->_tail == 0 ? k ; obj->_tail-1];

//第二种
return obj->_a[(obj->_tail-1 + obj->_k+1) %  (obj->_k+1)]

    第二种方法解决正常情况
    将tail=3带入，k=5带入

    ((3-1) + (5+1)) % (5+1)
    = (2+6) % 6
    = 8 % 6
    = 2

    第二种方法解决特殊情况
    将tail=0带入，k=5带入

    ((0-1) + (5+1)) % (5+1)
    = (-1+6) % 6
    = 5 % 6
    = 5

    所以第二种也可以写成这样

    return obj->_a[(obj->_tail + obj->_k) %  (obj->_k+1)]// -1 和 1 抵消了

    函数代码如下

    //取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->_a[(obj->_tail - 1 + obj->_k + 1) % (obj->_k + 1)];
}

    销毁循环队列(myCircularQueueFree)

    从内到外释放，先释放内部，再释放外部。

    //销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->_a);
    obj->_a = NULL;
    obj->_head = obj->_tail = obj->_k = 0;
    free(obj);
}

    完整代码

    typedef struct {
    int * _a;
    int _head;
    int _tail;
    int _k; 
} MyCircularQueue;

//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->_a = (int*)malloc(sizeof(int)* (k+1));
    obj->_head = obj->_tail = 0;
    obj->_k = k;
    return obj;
}

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->_head == obj->_tail;
}

//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->_tail+1) % (obj->_k + 1) == obj->_head;
}


//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }

    obj->_a[obj->_tail++] = value;
    //obj->_tail %= (obj->_k+1);
    if(obj->_tail == obj->_k+1)
    {
        obj->_tail = 0;
    }
    return true;
}

//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->_head++;
    obj->_head %= (obj->_k + 1);
    return true;
    
}

//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->_a[obj->_head];
}

//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->_a[(obj->_tail - 1 + obj->_k + 1) % (obj->_k + 1)];
}


//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->_a);
    obj->_a = NULL;
    obj->_head = obj->_tail = obj->_k = 0;
    free(obj);
}

    结语

    最后感谢您能阅读完此片文章，如果有任何建议或纠正欢迎在评论区留言，也可以前往我的主页看更多好文哦(点击此处跳转到主页)。
    如果您认为这篇文章对您有所收获，点一个小小的赞就是我创作的巨大动力，谢谢！！！

  • 相关阅读:
    C#把一片非托管内存 拷贝到 另一片非托管内存
    C++信息学奥赛1191：流感传染
    MacBook安装gym
    C++模板初阶
    计算机网络实验六 OSPF
    HTTP与HTTPS
    【Java开发】 Spring 07 ：Spring AOP 实践详解（通过 AOP 打印数据访问层）
    聊聊自然语言处理NLP
    uniapp----微信小程序 日历组件（周日历&& 月日历）【Vue3+ts+uView】
    仿IOS滑动屏幕关闭界面实现
  • 原文地址：https://blog.csdn.net/2301_80216111/article/details/139390642